超硬核HashMap底层构成以及扩容原理

2022-05-13 11:06:26 浏览数 (1)

HashMap的底层实现

JDK1.8之前

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

解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法可以减少碰撞。这点可以看后面

先说下JDK 1.8 HashMap 获取 hash 值的一个寻址优化

JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化（只扰动（异或）了一次），性能更好，但是原理和思想不变。

代码语言：javascript复制
static final int hash(Object key) { 
int h; 
// key.hashCode()：返回散列值也就是hashcode 
// ^ ：按位异或
// >>>:无符号右移，忽略符号位，空位都以0补齐
//这里的操作可以将hash后的结果里低16位是融合了原来高16位和低16位的异或结果的，尽量让不同key获取的hash结果在低16位是不一样的，这样在长度是一定的情况下，可以让key更加分散。 
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

对比一下 JDK1.7的 HashMap 的 hash 方法源码.

代码语言：javascript复制
static int hash(int h) {
// This function ensures that hashCodes that differ only by 
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动（异或）了 4 次。

所谓“

” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8之后

相比于之前的版本， JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。(链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树.为啥这样可以解决冲突呢?因为数组扩容涉及到重新hash的问题.)

TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。

推荐阅读： 《Java 8系列之重新认识HashMap》 ：https://zhuanlan.zhihu.com/p/2167380

Hashmap中的链表大小超过八个时会自动转化为红黑树，当删除小于六时重新变为链表，为啥呢？

根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换，小于等于6的时候就化为链表。

Hashmap中扩容因子选择的是0.75为啥呢？

主要是出于时间和空间上的考虑

  • 如果我们选择扩容因子是1,那么每次使用完全部空间再扩容势必造成时间上的等待问题
  • 如果我们选择扩容因子是0.5,那么每次使用一半就扩容,造成了每次都有一半的空间是浪费的.

所以最终平衡了一下选择0.75 https://blog.csdn.net/penghao_1/article/details/107631820

HashMap 的长度为什么是2的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash ”。（n代表数组长度）。这也就解释了 HashMap 的长度为什么是2的幂次方。

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，

（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。”

HashMap的put和get方法源码解析

put过程分析,源码请看链接put/get

代码语言：javascript复制
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

put()方法实际上是调用hash()方法获取到key的hash值 调用putVal()方法存储key-value 核心方法是putVal()方法 下面我会先分析一下hash()方法，因为这个方法涉及到hash值这个关键属性的计算。

代码语言：javascript复制
hash()方法
    static final int hash(Object key) {
        int h;
        // key为null时，hash值为0
        // key不为null时，调用key对象的hashCode()方法并通过位运算异或和无符号右移将高位分散到低位
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
hash()方法指定了null的hash值为0。这样就可以支持key为null。
(h = key.hashCode()) ^ (h >>> 16)这段代码通过位运算异或和无符号右移将高位分散到低位，这样做可以减少哈希碰撞的概率（这块不是很清楚原理，是从方法注释上了解到的）

putVal()方法的关键点:

  • 若table没有初始化则调用reszie()方法初始化。
  • 计算在数组位置，公式为(n - 1) & hash（等价于hash%n）。其中n为数组长度，hash为插入的键值对的key的哈希值。
  • 判断数组对应索引中的首节点是否为null，若为null，则创建链表，否则进入下一步。
  • 判断该首节点是否与插入的键值对的key和hash一致，若一致则替换该节点的值为value，否则进入下一步
  • 判断首节点是否为树节点，若是则调用树节点的putTreeVal()方法遍历红黑树，否则遍历链表。
  • 遍历红黑树时，若存在key和hash相同的节点就替换对应节点的值value，若不存在则插入新的树节点。
  • 遍历链表时，若存在key和hash相同的节点就替换对应节点的值为value。若找不到key和hash相同的节点，则链表尾部插入节点，同时进入下一步。
  • 若当前链表长度大于或等于树化阈值TREEIFY_THRESHOLD(8)时，则将链表转化为红黑树。
get()
代码语言：javascript复制
 public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

调用hash()方法获取到key的hash值 调用getNode()方法通过key和hash获取对应的value。不存在则返回null 核心方法是getNode()方法，下面我会先分析一下getNode()方法。

getNode()方法的关键点：

  1. 若散列表table不为null且长度大于0且其索引为(n - 1) & hash（等价于hash%n）的节点不为null。其中n为散列表长度，hash为插入的键值对的key的哈希值。则进入下一步，否则直接返回null

2 .判断首节点的key和hash是否与入参一致，若相同则返回首节点，否则进入下一步。 3判断节点个数只有1个，若是则返回null，否则进入下一步 4判断首节点是否为树节点，若是则遍历红黑树，否则为链表，进入下一步 5遍历链表，检索key和hash与入参相同的节点，若找到则返回该节点，否则返回null

HashMap 多线程操作导致死循环问题

在多线程下，进行 put 操作会导致 HashMap 死循环，原因在于 HashMap 的扩容 resize()方法。由于扩容是新建一个数组，复制原数据到数组。由于数组下标挂有链表，所以需要复制链表，但是多线程操作有可能导致环形链表。复制链表过程如下: 以下模拟2个线程同时扩容。假设，当前 HashMap 的空间为2（临界值为1），hashcode 分别为 0 和 1，在散列地址 0 处有元素 A 和 B，这时候要添加元素 C，C 经过 hash 运算，得到散列地址为 1，这时候由于超过了临界值，空间不够，需要调用 resize 方法进行扩容，那么在多线程条件下，会出现条件竞争，模拟过程如下：

这个过程为，先将 A 复制到新的 hash 表中，然后接着复制 B 到链头（A 的前边：B.next=A），本来 B.next=null，

到此也就结束了（跟线程二一样的过程），但是，由于线程二扩容的原因，将 B.next=A，所以，这里继续复制A，让

A.next=B，由此，环形链表出现：B.next=A; A.next=B

注意：jdk1.8已经解决了死循环的问题。

参考https://blog.csdn.net/hefenglian/article/details/79763634

HashMap 有哪几种常见的遍历方式?

HashMap 的 7 种遍历方式与性能分析！

hashmap jdk 编程算法

0 人点赞