由于散列映射使用模数/除法操作来选择适当的桶来放置值,因此碰撞的可能性似乎取决于桶的数量,而不是“哈希函数有多好”。函数函数的好坏决定了发生相同哈希返回冲突的可能性。然而,哈希映射中的“冲突”指的是其他东西,它指的是模数运算后的相同值。假设键值是整数(例如64位),如果散列映射的哈希函数只是键值本身,那么还能期望什么呢?我敢说,检索速度要快得多,因为不需要遍历大量字节并执行哈希操作,最终结果与哈希表冲突完全相同。我的意思是,最终与一个已经被占用的桶相撞的确切值是不同的值,但是如果这些值分散在整个地方,那么总体上结果应该是非常相似的。
发布于 2022-09-13 04:37:39
由于散列映射使用模数/除法操作来选择适当的桶来放置值,因此碰撞的可能性似乎取决于桶的数量,而不是“哈希函数有多好”。函数函数的好坏决定了发生相同哈希返回冲突的可能性。
不完全是。糟糕的哈希函数可以对键进行聚类,或者使特定位比其他位更有可能被设置。这反过来会导致一些桶更有可能被模数运算符所选择。
假设键值是整数(例如64位),如果散列映射的哈希函数只是键值本身,那么还能期望什么呢?
一般来说,你不能说。如果你只使用模数运算符,键中很可能会有模式,它会使一些桶比其他的桶更满。一个好的散列函数本质上将比特随机化,所以您更有可能在桶中均匀地分配密钥。
发布于 2022-09-13 03:42:51
碰撞的可能性似乎取决于桶的数量,而不是“哈希函数有多好”。
不,那不对。键通常不会均匀地分布在桶索引中。哈希键倾向于比原始键更均匀地分配桶索引。
index = key%bucket_n;
// vs
index = hash(key)%bucket_n;此外:一个好的散列函数在任何bucket_n中都能很好地工作。当bucket_n是素数时,弱哈希函数会得到改进。
需要平衡表中的条目数和表的大小。如果entires_n比table_size少得多,则OP断言是有意义的。但这却浪费了很多记忆
如果entires_n比table_size大得多,碰撞是常见的。如果没有散列函数,通常情况会更糟。
IMO,哈希表的大小应随输入计数呈指数增长,以保持低于某个阈值的密度,例如1/3。可能需要重新散列表,以适应大小的更改。
https://stackoverflow.com/questions/73697048
复制相似问题