hashMap源码解读

常量

常量名	类型	默认值	描述
DEFAULT_INITIAL_CAPACITY	int	1<<4 = 16	默认初始化容量大小
MAXIMUM_CAPACITY	int	1<<30	table最大长度,超过这个容量不再对table扩容
DEFAULT_LOAD_FACTOR	float	0.75f	默认负载系数,大于这个比例之后将进行扩容
UNTREEIFY_THRESHOLD	int	6	扩容时,某个哈希键上的元素小于6个时,数据结构由红黑树退化成链表
TREEIFY_THRESHOLD	int	8	扩容时,由链表进化成树的阈值,大于8个元素进化成红黑树
MIN_TREEIFY_CAPACITY	int	64	哈希键的个数小于64时,不进化成红黑树,原因是这时应该扩充键值数量来减少冲突.
threshold(非常量)	int		当size大于该值时进行扩容操作threshold = capacity*loadFactory
loadFactory(非常量)	float	0.75f	负载系数

数据结构

节点的数据结构由一个静态内部类Node<K,V>定义,实现了Map.Entry<K,V>接口

由四个属性构成

final int hash;//哈希结果
final K key;//key值
V value;//value值
Node<K,V> next;//指向下一个节点的指针

整体的结构是hash表使用数组存储,处理冲突采用链式方法处理,java8之后,联表长度大于定值会进化成红黑树.

哈希码计算

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

哈希值没有直接使用实例的hashcode方法进行计算,而是通过上面的hash方法重新计算了一遍.

计算方式是,key实例的hashcode值高16位不变,低16位与高16位的异或结果得到最终的hash值,当key为null时,hashcode为0.

为什么要这样做呢?

首先介绍一下hashmap中哈希取模计算的方式

hashmap中哈希键值的个数为2的次幂,这时取模运算可以使用按位与运算代替

 (n - 1) & hash]) == null)//使用按位与计算取模,n是table的长度

2进制的x次幂的结果用二进制表示为1000…的形式(1后面跟x个0),而(n-1 = 01111…),将hash与(n-1)按位与时,由于高位全为0,只有低位的1参与运算,就相当于对hash按n进行了取模运算.

回到刚才的话题,由于只有低x位参与运算,如果按照传统的方式对原始的key的hashcode进行取模运算,会导致高位不参与运算,这样的话会导致每个哈希键上的值分布的不均匀.而使用h = key.hashCode()) ^ (h >>> 16)​可以让高16位也参与运算,让分布变得更加均匀.

添加元素

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)//如果table的为null,或者长度为0,新建一个tablen = (tab = resize()).length;//计算取模结果i,判断插入位置i是否为空(没有冲突)if ((p = tab[i = (n - 1) & hash]) == null)//新建节点,并将节点复制给table上的第i个元素tab[i] = newNode(hash, key, value, null);else {//如果插入位置有冲突Node<K,V> e; K k;//判断插入的key值刚好等于table头节点的key值if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//将头结点赋值给ee = p;else if (p instanceof TreeNode)//如果不与头节点相等,而且p位置使用的是红黑树,则使用putTreeVal插入元素,并返回插入的节点ee = ((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);//判断插入新节点后,链表长度是否超过阈值TREEIFY_THRESHOLD,如果超过的话,将联表进化成红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//如果遍历过程中发现相等元素.终止遍历,这时e指向相等节点if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;//替换元素p = e;}}//如果e不等于null,并且onlyIfAbsent=false(hashmap使用的fasle),或者原value值为null,则会替换节点的value.if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;//为linkedhashmap预留的节点处理方法afterNodeAccess(e);return oldValue;}}++modCount;//判断是否需要扩充tableif (++size > threshold)resize();//为linkedhashmap预留的节点处理方法afterNodeInsertion(evict);return null;
}

resize

resize方法用于table的初始化和乘二扩容,假设原table长度为$n$,由于扩容都是乘2的,所以原来的节点要不还在原来的哈希键的位置上,要不在$原哈希值+n$位置上(在取模时多一位高位参加运算(按位与,因为扩容后的计算哈希值时高位多了一位1),当这一位是1时,hash结果=$原哈希值+n$,是0时hash值不变).

比如原来table的长度是8,二进制表示为0000 1000,按照 (n - 1) & hash计算哈希值.设插入元素的hash值=0001 0001

n-1 = 0000 $\color{red}0$111 n-1 = 0000 $\color{red}0$111

hash = 0001 $\color{red}1$011 hash = 0001 $\color{red}1$011

结果 = 0000 $\color{red}0$001 结果 = 0000 $\color{red}0$001

相当于只有后三位参加&运算,hash值的倒数第4位相当于未参加运算(和0进行& = 0)

现在扩容了 新的table长度为16, 二进制表示n = 0001 0000, n-1 = 0000 1111

n-1 = 0000 $\color{red}1$111 n-1 = 0000 1111

hash = 0001 $\color{red}1$011 hash = 0001 $\color{red}0$011

结果 = 0000 $\color{red}1$001 结果 = 0000 $\color{red}0$001

现在有后四位参与运算,当hash值的倒数第四位为0时,结果与原table相同,当倒数低四位为1时,结果=原值+原哈希表长度

final Node<K,V>[] resize() {//原tableNode<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;//扩容阈值,大于这个容量会扩容int oldThr = threshold;int newCap, newThr = 0;//判断新table长度的过程//首先,如果oldTable长度大于0if (oldCap > 0) {//判断当前table的长度是否已超过最大容量if (oldCap >= MAXIMUM_CAPACITY) {//超过的话不扩容,直接返回,并将Integer.MAX_VALUE赋值给thresholdthreshold = Integer.MAX_VALUE;return oldTab;}//如果table扩容后长度小于最大长度,并且当前table长大于默认长度,则table长度乘2else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//如果table长度为0(未初始化),并且扩容阈值threshold大于0,则新table的长度为threshold,这种情况适用于new hashMap(inc initialCapacity)时传入了初始容量的情况,这是threshold会初始化为大于initialCapacity的最小2的n次幂的值,比如传入7,则初始table的长度为8,传入14,初始table的长度为16,这个值的初始化函数tableSizeFor(int cap)很有意思,下面再讲else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaults//如果oldtable长度为空,并且使用的new hashMap构造函数,没有传入初始容量,则没法计算初始阈值,这是使用默认的容量和阈值.默认容量为16,负载系数为0.75,扩容阈值threshold = 16 *0.75 = 12 newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//如果计算出来的阈值=0,则根据容量和负载系数等计算阈值if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//将计算出来的阈值赋值给全局变量thresholdthreshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})//根据上面计算出来的新table的长度newCap,新建table数组newTabNode<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//将table指向新table数组table = newTab;//数据重新映射过程.注意这个过程是线程不安全的,多线程情况下,多个线程同时操作node的指向,这样可能会导致链表循环引用if (oldTab != null) {//按哈希键逐个重新映射for (int j = 0; j < oldCap; ++j) {Node<K,V> e;//判断原table上,oldTab[j]是否为null,不为null时将e指向该hash键if ((e = oldTab[j]) != null) {//释放原table上的该哈希键上的引用oldTab[j] = null;//如果该链表只有一个元素(即只有table上的存储的头结点元素)if (e.next == null)//该节点重新计算哈希值后赋值给newTab的对应位置.newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)//如果使用的树结构存储,调用split方法进行重新映射((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order//如果是链表存储,遍历链表,重新映射,这里使用一种特殊的方法分两步进行重新映射//首先将链表按照(e.hash & oldCap) == 0是否等于0将原联表分成两个链表.这样做的原因,在table进行乘2扩容后,对于一条链上的数据,只有两种新的映射结果,一种是还等于原hash值,另一种是=原哈希值+原table长度,当(e.hash & oldCap) == 0时,说明e.hash再倒数第n位上元素为0,则其新的哈希映射结果与原table相同,当等于1时,映射结果=原哈希值+原table长度Node<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);//分成两个列表直接将新的链接头节点的指针复制给新table数组的对应位置即可,这样就完成可扩容if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

构造函数

有三个构造函数

public HashMap(int initialCapacity, float loadFactor) {//初始容量参数校验if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);//指定容量大于最大容量.使用最大容量(2<<<30)if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//负载参数校验if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;//获得大于initialCapacity初始容量最小的2的次幂的数this.threshold = tableSizeFor(initialCapacity);
}
//指定初始容量,负载使用默认负载
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

比较有意思的一点是,hashmap使用了延迟加载的策略,new HashMap时并不会把table等new出来,只要put的时候,才会再resize中判断table是否为null,如果为null再创建table.

tableSizeFor

获得大于initialCapacity初始容量最小的2的次幂的数

/*** Returns a power of two size for the given target capacity.*/
static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

第一行的减一是避免得到的结果大于2<<<30,int型去掉符号位有31个字节,2<<<30已经是int型能表示的最大2的整数次幂结果

n |= n >>> 1; 表示 n = n |(n>>>>1),假设n的二进制数,最高为等于1的数在第k位上,这一行的结果是将n的第k+1位变成1

n |= n >>> 2;由于n的第k和k+1位都是1,这一行的结果是n的第k到k+1+2位中间所有元素都是1,

n |= n >>> 4; 结果是n的第k到第k+1+4位元素都变成1

…

最后得到的结果是n从第k位开始到最后一位都是1(形如00011111)

再将n+1 = 00100000 刚好是比n大的最小的2的次幂结果

get

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}/*** Implements Map.get and related methods.** @param hash hash for key* @param key the key* @return the node, or null if none*/
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//参数校验,判断table是否为空,计算哈希结果,校验对应位置联表是否为空,校验失败返回nullif ((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;//遍历查找,找到返回节点,找不到返回nullif ((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);}}//未找到符合的key值,返回nullreturn null;
}

1.7 尾插法扩容为什么会有死循环

https://blog.csdn.net/weixin_44029692/article/details/89197432?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param

主要还是头插法会改变原有链表的顺序而尾插法不会