HashMap原理(二):链表+红黑树解决哈希冲突

实际开发中经常用到 {key , value} 结构的数据。本文为了语义清晰，业务数据中的key称之为buz_key，buz_key转换成哈希函数所需的整数key称之为hash_key，通常由buz_key.hashCode()方法得到。hash_key经过哈希函数转换成哈希索引hash_index，然后便将 {key , value} 存储在 hash_table[hash_index] 处。 我们通过哈希函数的转换，将hash_key限制在一定范围内， 即hash_fun(hash_key) = hash_index，hash_index ∈ [0,hash_table.length)，从而降低哈希表内存的分配。不过无论哈希函数设计的多么优秀，总会有多个hash_key计算的hash_index相同，也就产生了冲突，因为逻辑上 hash_table[hash_index] 只能存储一个元素，这种冲突称之为哈希冲突。

解决哈希冲突最常见的两种方法：链表法和开放寻址法。

链表法是把hash_key映射到同一位置的所有数据用链表串起来，只将链表头存储在 hash_table[hash_index] 处。

如图，hash_key = 54，28，41时，hash_index都为2，产生了哈希冲突。将三者用链表链起来，然后将头指针存储在 hash_table[2] 的位置。

hash_table的每一个存储位置hash_table[hash_index]，称之为slot，即槽位。链表法是将映射到同一槽位的元素用链表链接起来，然后将头元素存储在槽位里。而开放寻址法一个槽位永远只存储一个元素，当发生哈希冲突时，以发生冲突的位置为基准，按照某种偏移量，依次查看后续的槽位，直到找到空闲的槽位，然后将该元素放置在这个位置。

如图，key = 26时，hash_index = 4，所以将26存储在hash_table[4]处，key = 15时，hash_index也为4，产生哈希冲突，此时以slot 4为基础，偏移量设为1，依次往后检测，直到找到空闲位置slot 8，将其存储在该位置。 这种偏移量为1的开放寻址法称之为线性探测法，是开放寻址法最简单的实现方案。

HashMap采用链表法解决冲突。HashMap将{key , value}封装成下面的复合数据结构：

每个元素都包含链接下一个元素的成员变量next。

理想状况下，通过哈希表查找一个元素，时间复杂度为O(1)，当某个槽位发生哈希冲突时，查找这个槽位上的某个元素，时间复杂度退化为O(n)。当这个槽位哈希冲突严重，导致链表长度较长时，时间开销将加大。 java 8开始，HashMap哈希冲突的解决采用链表 + 红黑树的方案。当某个槽位的链表长度达到8，这个槽位的链表会转化为红黑树，红黑树中查找元素，时间复杂度为log(h)，h为树的高度。 注意，如果某个槽位的链表长度达到8，但整个哈希表的长度小于64，那么并不会转化红黑树，而是直接扩容哈希表，来降低哈希碰撞的几率。 如果某个槽位已经是红黑树了，那么这个槽位的元素个数减少为6个时，又会重新转化为链表。 源码中定义了这些临界值，并注明了其含义：