乐趣区

关于java:哈希冲突详解

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

哈希抵触详解

一般来说哈希抵触有两大类解决形式

  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…

退出移动版