首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如果在选择散列映射桶之前没有散列值,会发生什么情况?

问如果在选择散列映射桶之前没有散列值,会发生什么情况?
EN

Stack Overflow用户
提问于 2022-09-13 02:47:30
回答 3查看 65关注 0票数 0

由于散列映射使用模数/除法操作来选择适当的桶来放置值,因此碰撞的可能性似乎取决于桶的数量,而不是“哈希函数有多好”。函数函数的好坏决定了发生相同哈希返回冲突的可能性。然而,哈希映射中的“冲突”指的是其他东西,它指的是模数运算后的相同值。假设键值是整数(例如64位),如果散列映射的哈希函数只是键值本身,那么还能期望什么呢?我敢说,检索速度要快得多,因为不需要遍历大量字节并执行哈希操作,最终结果与哈希表冲突完全相同。我的意思是,最终与一个已经被占用的桶相撞的确切值是不同的值,但是如果这些值分散在整个地方,那么总体上结果应该是非常相似的。

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2022-09-13 04:37:39

由于散列映射使用模数/除法操作来选择适当的桶来放置值,因此碰撞的可能性似乎取决于桶的数量,而不是“哈希函数有多好”。函数函数的好坏决定了发生相同哈希返回冲突的可能性。

不完全是。糟糕的哈希函数可以对键进行聚类,或者使特定位比其他位更有可能被设置。这反过来会导致一些桶更有可能被模数运算符所选择。

假设键值是整数(例如64位),如果散列映射的哈希函数只是键值本身,那么还能期望什么呢?

一般来说,你不能说。如果你只使用模数运算符,键中很可能会有模式,它会使一些桶比其他的桶更满。一个好的散列函数本质上将比特随机化,所以您更有可能在桶中均匀地分配密钥。

票数 1
EN

Stack Overflow用户

发布于 2022-09-13 03:42:51

碰撞的可能性似乎取决于桶的数量,而不是“哈希函数有多好”。

不,那不对。键通常不会均匀地分布在桶索引中。哈希键倾向于比原始键更均匀地分配桶索引。

代码语言:javascript
复制
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。可能需要重新散列表,以适应大小的更改。

票数 2
EN

Stack Overflow用户

发布于 2022-09-13 03:16:44

假设键值是整数(例如64位),如果散列映射的哈希函数只是键值本身,那么还能期望什么呢?

许多语言就是这么做的。例如Java。

但是您必须小心,如果您的哈希函数太琐碎,攻击者利用哈希冲突在您的服务中造成DoS也是很容易的。这就是所谓的碰撞攻击。不同的图书馆以不同的方式处理这一问题。

每当在单个桶中检测到太多冲突时,Java HashMap 落回一棵红黑的树就会这样做。其他语言在散列函数中引入了随机化,因此攻击将更难利用它。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/73697048

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档