当前位置：首页 > news >正文

java集合-Map HashMap 源码解析

news 文章来源：https://blog.csdn.net/loushaoqi/article/details/144591322 2025/5/2 19:37:57

hashMap简介

HashMap是基于哈希表实现的，每一个元素是一个key-value对，无序，不可重复。
HashMap是非线程安全的，只是用于单线程环境下，多线程环境下可以采用concurrent并发包下的concurrentHashMap。
HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆。
hashmap集合的默认初始化容量为16(2<<3)，如果初始化增加的大小则是最接近该数的2的幂次方，默认加载因子为0.75，也就是说这个默认加载因子是当hashMap集合底层数组的容量达到75%时，数组就开始扩容。hashmap集合初始化容量是2的陪数，为了达到散列均匀，提高hashmap集合的存取效率。
无论我们指定的容量为多少，构造方法都会将实际容量设为不小于指定容量的2的次方的一个数，且最大值不能超过2的30次方
HashMap中key和value都允许为null。key为null的键值对永远都放在以table[0]为头结点的链表中。
JDK1.8之后当链表的长度达到 “8” 时，内部会调用 “treeifyBin” 方法，判断数组长度是否达到 “64” 达到就会自动变成红黑树的结构，达不到会调用扩容机制，当红黑树节点的个数达到 “6” 之后，又会变成链表结构。

源码解析

初始化Map

HashMap hashMap=new HashMap();
public HashMap() {
//DEFAULT_LOAD_FACTOR = 0.75f;this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}HashMap hashMap=new HashMap(5); 
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)//初始化大小不能为负数 throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
//不能超过最大值 if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;
//指定的扩容因子不能小于等于0 if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);
}//不管传多大的容量，容量都是最靠近设置值的2的幂次方

tableSizeFor()

static final int tableSizeFor(int cap) {//返回给定目标容量的两倍幂int n = cap - 1;//减1.防止传入的刚好是2的幂次方的时候，得到的是下一个幂次方，比如传入4，不减1，会得到8 n |= n >>> 1;//右移一位，然后|运算，能保证高2位是1，是4   n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;//类推到最大的2的32-1，也就是32个1！！因为 java中int4字节，也就是32位，达到int的最大值return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;//再加1， 
}
举例展示
n=cap-1 ; // 4 二进制位100 
n |= n >>> 1; // n>>>1 为 0000 0010 与n|运算 得到0000 0110 
n |= n >>> 2; // n>>>2 为 0000 0001 与n|运算 得到0000 0111 转换为十进制为7 
n |= n >>> 8; // 还是7 
n |= n >>> 16; // 还是7 
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? 
MAXIMUM_CAPACITY : n + 1; //再加1，返回8，得到的是传入的最近的2 的幂

put方法

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

hash()扰动函数

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//让高低位都参与下标hashcode的计算 
}

putVal（）方法

//hash 通过扰动函数得到的hash值  onlyIfAbsent false evict true 
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//定义变量 
//第一次进来 table为空，并且tab.length为0 if ((tab = table) == null || (n = tab.length) == 0)
//进入resize方法,得到一个初始化大小为8的数组 n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)//根据 hashcode取模7 得到下标，并且查询下标值是否为空，第一次为null tab[i] = newNode(hash, key, value, null);//在下标 位置new node 将key value赋值 else {//将数组上的链表移到新数组 Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

初始化resize方法

final Node<K,V>[] resize() {//返回一个node数组 Node<K,V>[] oldTab = table;//第一次进来为null int oldCap = (oldTab == null) ? 0 : oldTab.length;//oldCap=0 int oldThr = threshold;//传进来最靠近2的幂等的数据 现在传的是5 那么就是8 int newCap, newThr = 0;if (oldCap > 0) {//第一次进来不满足 if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in threshold// 满足 oldThr=8 initial capacity was placed in threshold 初始容量为阈值 newCap = oldThr;//newCap=8 else {               // zero initial threshold signifies using defaults零初始阈值表示使用默认值 不进入 
newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}
//满足条件if (newThr == 0) {float ft = (float)newCap * loadFactor;//ft=8*0.75 得到6 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);//newThr 为6 }threshold = newThr;//赋值扩容阈值为6 @SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//初始化8大小的数组 table = newTab;//将初始化的table赋值给tableif (oldTab != null) {//第一次不满足条件，不需要进行rehashfor (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;//返回初始化为8的tab 
}

第二个元素put

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i; 
//table为8容量的table 不为空，不进入该逻辑 if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)根据hash得 到下标，如果为空，直接new node tab[i] = newNode(hash, key, value, null);//在下标 位置new node 将key value赋值 else {//下标如果有位置，说明key是一样的，或者发生了hash冲突Node<K,V> e; K k;if (p.hash == hash &&//p为下标位置已有的值 如果该值的key跟传入的一致 把e替换成p ((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)//如果是黑红树 往红黑树添加节点e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//不是node节点也不是红黑树for (int binCount = 0; ; ++binCount) {
//e为p节点的下一个节点，如果为空，说明到了p节点位 置的最后一个位置（循环里把p设置为e）if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//加到p节点的nextif (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//如果binCount大于等于7 代表链表的长度达到 8的时候，转为红黑树 treeifyBin(tab, hash);//里面会先判断容量是否小于64，不然先进行resize扩容 break;//跳出循环}
//hash冲突 并且key相同的时候，直接跳出 覆盖原来 的key就行 if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for key//如果e不为null V oldValue = e.value;//得到原来位置的值if (!onlyIfAbsent || oldValue == null)//如果onlyIfAbsent为false 或者没有value 替换原来 的value e.value = value;afterNodeAccess(e);//模板方法 return oldValue;}}++modCount;if (++size > threshold)//如果大于我的阈值，进行resizeresize();afterNodeInsertion(evict);模板return null;
}

扩容resize方法

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;//已有的的数组table int oldCap = (oldTab == null) ? 0 : oldTab.length;// 之前table长度为8 int oldThr = threshold;//之前的阈值为6int newCap, newThr = 0;if (oldCap > 0) {//8>0满足if (oldCap >= MAXIMUM_CAPACITY) {//不为最大值，没有 扩容到最大值 threshold = Integer.MAX_VALUE;return oldTab;}//newCap为之前容量的2倍 如果小于最大值并且之前的容量大于默 认的大小，newThr为老阈值的2倍（我们的例子不满足） else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {//满足该场景，当前新的阈值还是0 float ft = (float)newCap * loadFactor;//根据新的table容量计算下次扩容的阈值 为16 *0.75=12 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);//12赋值 给newThr }threshold = newThr;//阈值设置为12@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;//讲table数组扩容到16if (oldTab != null) {//满足 for (int j = 0; j < oldCap; ++j) {//循环老的数组数据 Node<K,V> e;if ((e = oldTab[j]) != null) {//将下标的数据赋 值给e oldTab[j] = null;if (e.next == null)//e的next为null。代表当前位置不是链表，没有发生hash冲突 newTab[e.hash & (newCap - 1)] = e;// 把e放到新的位置 else if (e instanceof TreeNode)//如果是红黑 树，将树移到新的位置 如果小于6 会退化成单向链表 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

get方法

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode方法

final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//table不为空，并且通过hash拿到的value不为空 if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
//第一个节点的数据就是我要的key，直接返回第一个节点if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))
//不为空，说明是红黑树或者链表 return first;if ((e = first.next) != null) {if (first instanceof TreeNode)//如果是红黑树，返回红黑树节点return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {//如果是链表，从链表循环找到我的数据 if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

put原理

第一步首先将k,v封装到Node对象当中（节点）。

第二步它的底层会调用K的hashCode()方法得出hash值。

第三步通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。

因此，放在hashMap集合key部分的元素如果是自定义对象的话都需要重写hashCode和equal方法。

get原理

第一步：先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。

第二步：通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。

在hashMap添加元素的时候会计算添加元素的hash值，通过hash值确定放在哪个hash桶中，当不同的元素计算出相同的hash桶的时候，这样就发生了哈希碰撞

哈希碰撞

开放地址发：

当冲突发生时，使用某种探查技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的地址。

开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)

其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。

如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2)，称二次探测再散列。

如果di取值可能为伪随机数列。称伪随机探测再散列。

链地址法（拉链法）hashMap使用的就这这种方法：

将相同hash值的对象组织成一个链表放在hash值对应的槽位；

再哈希法：

当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。

比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止

建立一个公共溢出区:

假设哈希函数的值域为[0,m-1],则设向量HashTable[0…m-1]为基本表，另外设立存储空间向量OverTable[0…v]用以存储发生冲突的记录。

HashMap中的“死锁”

HashMap是非线程安全，死锁一般都是产生于并发情况下。我们假设有二个进程T1、T2，HashMap容量为2,T1线程放入key A、B、C、D、E。在T1线程中A、B、C Hash值相同，于是形成一个链接，假设为A->C->B，而D、E Hash值不同，于是容量不足，需要新建一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中(refresh)。这时T2进程闯进来了，T1暂时挂起，T2进程也准备放入新的key，这时也发现容量不足，也refresh一把。refresh之后原来的链表结构假设为C->A，之后T1进程继续执行，链接结构为A->C,这时就形成A.next=B,B.next=A的环形链表。一旦取值进入这个环形链表就会陷入死循环。

解决办法：

使用线程安全的ConcurrentHashMap

hashMap的容量怎么扩充

table 数组大小是由 capacity 这个参数确定的，默认是16，也可以构造

时传入，最大限制是1<<30；并且必须是2的幂次方

loadFactor 是装载因子，主要目的是用来确认table 数组是否需要动态

扩展，默认值是0.75，比如table 数组大小为 16，装载因子为 0.75

时，threshold 就是12，当 table 的实际大小超过 12时，table就需要

动态扩容；

扩容时，调用 resize() 方法，将 table 长度变为原来的两倍，并且根据

新的容量，计算新的数据索引值

hashMap 在JDK1.8跟1.7的区别，chm在JDK1.8跟1.7的区别

1.7采用数组+单链表，1.8在单链表超过8并且数组长度超过64时，单
1.7扩容时需要重新计算哈希值和索引位置，1.8不重新计算哈希值，而是采用和扩容后容量进行&操作来计算新的索引位置。
1.7插入元素到单链表中采用头插入法，1.8采用的是尾插入法。（1.7重新计算hash值并发有闭环链表风险）

chm 上述hashMap的变更也是chm的变更，还有锁

1.7采用分段锁的机制，锁住的是一个segment数组，采用重入锁

ReentrantLock（重入锁）

1.8.采用Node + CAS + Synchronized来保证并发安全,取消类 Segment，直接锁entry

为什么取消重入锁，采用synchronized?

粒度降低了；

JVM 开发团队没有放弃 synchronized，而且基于 JVM 的 synchronized

优化空间更大，更加自然。

在大量的数据操作下，对于 JVM 的内存压力，基于 API 的

ReentrantLock 会开销更多的内存。