1. HashMap介绍

HashMap是基于哈希表Map接口实现,用于存放键值对(K-V)的非线程安全的集合,可接受null作为键值。

2. 哈希表

也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表。

我们知道,数据结构的物理存储结构只有两种:顺序存储结构链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组,数组中存放的是链表。

比如我们要新增或查找某个元素,我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。这个函数可以简单描述为:存储位置 = f(关键字) ,这个函数f一般称为哈希函数,这个函数的设计好坏会直接影响到哈希表的优劣。举个例子,比如我们要在哈希表中执行插入操作,插入过程如下图所示

哈希表

查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。

哈希冲突

然而万事无完美,如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。前面我们提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式。

3. HashMap 底层结构

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对(其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合)

 //HashMap的主干数组,可以看到就是一个Entry数组,初始值为空数组{},主干数组的长度一定是2的次幂。
 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

Entry对象是HashMap类中的一个静态内部类

     static class Entry<K,V> implements Map.Entry<K,V> {
         final K key;
         V value;
         Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构
         int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算
 
         /**
          * Creates new entry.
          */
         Entry(int h, K k, V v, Entry<K,V> n) {
             value = v;
             next = n;
             key = k;
             hash = h;
         } 
 

HashMap总体结构

HashMap结构图

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值,然后通过 (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key 是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

简单来说,HashMap由数组+链表组成的(1.8之后加入了红黑树),数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

4. HashMap put过程

4.1 初始化

HashMap有4个构造器,其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数,会使用默认值一般如果new HashMap() 不传值, 默认大小是16,负载因子是0.75, 如果自己传入初始大小k,初始化大小为 大于k的 2的整数次方,例如如果传10,大小为16。

4.2 put()过程

判断数组是否为空,为空进行初始化;
不为空,计算 key的 hash 值,通过(n - 1) & hash(哈希算法)计算应当存放在数组中的下标 index;
查看 table[index] 是否存在数据,没有数据就构造一个Node节点存放在 table[index] 中;
存在数据,说明发生了hash冲突(存在两个节点key的hash值一样), 继续判断key是否相等,相等,用新的value替换原数据(onlyIfAbsent为false);
如果不相等,判断当前节点类型是不是树型节点,如果是树型节点,创造树型节点插入红黑树中;(如果当前节点是树型节点证明当前已经是红黑树了)
如果不是树型节点,创建普通Node加入链表中;判断链表长度是否大于 8并且数组长度大于64, 大于的话链表转换为红黑树;

插入完成之后判断当前节点数是否大于阈值,如果大于开始扩容为原数组的二倍。

HashMap put过程

 // put源码
 public V put(K key, V value) {
         //如果table数组为空数组{},进行数组填充(为table分配实际内存空间),入参为threshold,
         //此时threshold为initialCapacity 默认是1<<4(2^4=16)
         if (table == EMPTY_TABLE) {
             inflateTable(threshold);
         }
        //如果key为null,存储位置为table[0]或table[0]的冲突链上
         if (key == null)
             return putForNullKey(value);
         int hash = hash(key);//对key的hashcode进一步计算,确保散列均匀
         int i = indexFor(hash, table.length);//获取在table中的实际位置
         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
         //如果该对应数据已存在,执行覆盖操作。用新value替换旧value,并返回旧value
             Object k;
             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                 V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
             }
         }
         modCount++;//保证并发访问时,若HashMap内部结构发生变化,快速响应失败
         addEntry(hash, key, value, i);//新增一个entry
         return null;
     }

inflateTable这个方法用于为主干数组table在内存中分配存储空间,通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂,比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.

 void addEntry(int hash, K key, V value, int bucketIndex) {
         if ((size >= threshold) && (null != table[bucketIndex])) {
             resize(2 * table.length);//当size超过临界阈值threshold,并且即将发生哈希冲突时进行扩容
             hash = (null != key) ? hash(key) : 0;
             bucketIndex = indexFor(hash, table.length);
         }
         createEntry(hash, key, value, bucketIndex);
     }

通过以上代码能够得知,当发生哈希冲突并且size大于阈值的时候,需要进行数组扩容,扩容时,需要新建一个长度为之前数组2倍的新的数组,然后将当前的Entry数组中的元素全部传输过去,扩容后的新数组长度为之前的2倍,所以扩容相对来说是个耗资源的操作。

总结:

put方法大致的思路是:
1、对key的hashCode()做hash,然后再计算存到数组里的下标;
2、如果没发生冲突直接放到数组里;
3、如果冲突了,以链表的形式存在对应的数组[ i ]中 ;
4、如果冲突导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树;
5、如果节点已经存在就替换old value(保证key的唯一性)
6、如果数组满了(超过load factor*current capacity),就要resize(扩容)。

4.3 有关面试题

为什么HashMap数组长度一定要是2的n次幂

计算索引位置的公式为:(n - 1) & hash,当 n 为 2 的 N 次方时,n - 1 为低位全是 1 的值,此时任何值跟 n - 1 进行 & 运算的结果为该值的低 N 位,达到了和取模同样的效果,实现了均匀分布。实际上,这个设计就是基于公式:x mod 2^n = x & (2^n - 1),因为 & 运算比 mod 具有更高的效率
总的来说原因是2^n-1的低位是1,在进行与运算时更加高效,同时还可以降低hash冲突

什么时候转红黑树

因为当桶中元素到达8个的时候,概率已经变得非常小,也就是说用0.75作为负载因子,每个碰撞位置的链表长度超过8个是几乎不可能的(概率极小)。(也就是超过8 可以转化为红黑树)

  • 并且如果 链表的长度 大于 8 会尝试调用 treeifyBin 方法
  • 在此判断 表的长度是否大于64

在链表长度大于 8 并且 表的长度大于 64 的时候会转化红黑树!!!!

 if ((e = p.next) == null) {
 p.next = newNode(hash, key, value, null);
 // 并且如果 链表的长度 大于 8 会尝试调用  treeifyBin 方法
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 treeifyBin(tab, hash);
 break;
 }
 // treeifyBin 方法
     final void treeifyBin(Node<K,V>[] tab, int hash) {
         int n, index; Node<K,V> e;
         // 如果表的长度小于 64 会先扩容!!! 否则 扩容
         // MIN_TREEIFY_CAPACITY = 64;
         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
             resize();
         else if ((e = tab[index = (n - 1) & hash]) != null) {
             TreeNode<K,V> hd = null, tl = null;
             do {
                 TreeNode<K,V> p = replacementTreeNode(e, null);
                 if (tl == null)
                     hd = p;
                 else {
                     p.prev = tl;
                     tl.next = p;
                 }
                 tl = p;
             } while ((e = e.next) != null);
             if ((tab[index] = hd) != null)
                 hd.treeify(tab);
         }
     }
 

为什么链表阈值是8

我们平时在进行方案设计时,必须考虑的两个很重要的因素是:时间和空间。对于 HashMap 也是同样的道理,简单来说,阈值为8是在时间和空间上权衡的结果。(就是作者设计的,没什么为什么)

科学解释

理想情况下,使用随机的哈希码,节点分布在 hash 桶中的频率遵循泊松分布,按照泊松分布的公式计算,链表中节点个数为8时的概率为 0.00000006(跟大乐透一等奖差不多),这个概率足够低了,并且到8个节点时,红黑树的性能优势也会开始展现出来,因此8是一个较合理的数字。

为什么红黑树转回链表是6

因为中间多个个7,不会使得红黑树和链表之间频繁转换,如果我们设置节点多于8个转红黑树,少于8个就马上转链表,当节点个数在8徘徊时,就会频繁进行红黑树和链表的转换,造成性能的损耗


参考资料

JDK集合源码之HashMap解析

Java集合之一—HashMap

最后修改:2022 年 05 月 09 日
请博主喝杯咖啡~~~