哈希冲突详解

微信扫一扫,分享到朋友圈

哈希冲突详解

微信搜索:mag:「码农田小齐」,关注这个在纽约的程序媛,回复「01-05」可以获取计算机精选书籍、个人刷题笔记、大厂面经、面试资料等资源,么么哒~

哈希冲突详解

一般来说哈希冲突有两大类 解决方式 [1]

  1. Separate chaining

  2. Open addressing

Java 中采用的是第一种 Separate chaining ,即在发生碰撞的那个桶后面再加一条“链”来存储,那么这个“链”使用的具体是什么数据结构,不同的版本稍有不同:

在 JDK1.6 和 1.7 中,是用 链表 存储的,这样如果碰撞很多的话,就变成了在链表上的查找,worst case 就是 O(n);

在 JDK 1.8 进行了优化,当链表长度较大时(超过 8),会采用 红黑树 来存储,这样大大提高了查找效率。

(话说,这个还真的喜欢考,已经在多次面试中被问过了,还有面试官问为什么是超过“8”才用红黑树 )

第二种方法 open addressing 也是非常重要的思想,因为在真实的分布式系统里,有很多地方会用到 hash 的思想但又不适合用 seprate chaining

这种方法是顺序查找,如果这个桶里已经被占了,那就按照“ 某种方式 ”继续找下一个没有被占的桶,直到找到第一个空的。

如图所示,John Smith 和 Sandra Dee 发生了哈希冲突,都被计算到 152 号桶,于是 Sandra 就去了下一个空位 – 153 号桶,当然也会对之后的 key 发生影响:Ted Baker 计算结果本应是放在 153 号的,但鉴于已经被 Sandra 占了,就只能再去下一个空位了,所以到了 154 号。

这种方式叫做 Linear probing 线性探查,就像上图所示,一个个的顺着找下一个空位。当然还有其他的方式,比如去找平方数,或者 Double hashing.

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666/NYCSDE

微信扫一扫,分享到朋友圈

哈希冲突详解

CU Boulder打造出具有延展性、自愈能力的“电子皮肤”

上一篇

Canalys:iPhone 11登顶三季度全球销量冠军 库克笑了

下一篇

你也可能喜欢

哈希冲突详解

长按储存图像,分享给朋友