哈希冲突详解
source link: http://www.cnblogs.com/nycsde/p/13962696.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
微信搜索:mag:「码农田小齐」，关注这个在纽约的程序媛，回复「01-05」可以获取计算机精选书籍、个人刷题笔记、大厂面经、面试资料等资源，么么哒～
哈希冲突详解
一般来说哈希冲突有两大类 解决方式 [1]
-
Separate chaining
-
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
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK