微信搜寻????「码农田小齐」，关注这个在纽约的程序媛，回复「01-05」能够获取计算机精选书籍、集体刷题笔记、大厂面经、面试材料等资源，么么哒～
哈希抵触详解
一般来说哈希抵触有两大类解决形式
- 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…