JDK17 HashMap

HashMap

ArrayList用动态数组存放元素，而HashMap用动态数组（桶）存储键值对。
如果两个键值对映射到桶同一个索引，则称为散列冲突。HashMap采用拉链法解决冲突，即桶中每个索引指向一个链表或者红黑树，多个键值对存放在同一个链表/红黑树中。
拉链法的优点是：

1. 链表是动态申请的，适合动态扩容的桶。
2. 解决冲突方法比较简单，无堆积现象(非键冲突键值对不会冲突)。查找效率高。
3. 键值对规模较大时可以充分利用桶索引，节省空间。

拉链法的缺点是：键值对规模较小时，浪费空间。而ThreadLocalMap用的就是开放地址法解决冲突。

构造器方法

HashMap的构造器方法有很多，最常见的有2个，一个设置初始容量，一个不设置初始容量。

方法	含义
HashMap(int initialCapacity)	指定初始容量
public HashMap()	默认初始容量为16

推荐指定初始容量，原因是如果默认初始容量不足以存储元素，HashMap会扩容。每次扩容都会将元素重新计算哈希值并放入新桶，非常消耗性能。
因此初始容量设为expectedSize / 0.75F + 1.0F。

public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY) // MAXIMUM_CAPACITY = 1 << 30.也就是2的30次方。initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;// tableSizeFor方法是取比initialCapacity大的最小的2的次幂// threshold=capacity * load factor，数组容量超过threshold则扩容this.threshold = tableSizeFor(initialCapacity);
}

键值对

HashMap采用Node静态内部类存储元素。散列值是为了快速定位桶索引。next表示链表下一个Node节点。

如果链表达到一定规模，将链表转为红黑树存储元素。

哈希映射

HashMap<K, V>的键可以是任意类型，为了将键对象映射为桶索引，第一步调用hash(Object key)方法将键对象散列为int类型散列值h。

static final int hash(Object key) {int h;// 如果key == null, 则数组下标为0// 如果key != null, 调用key的hashCode()方法计算哈希值h//	   h >>> 16 是获取h的高16位//     h ^ (h >>> 16)是将低16位与高16位进行异或运算return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

第二步，数组下标i = (n - 1) & hash，其中n是桶容量，且为2的次幂。第三步，HashMap将键值对存储在桶的索引i位置。

散列值h是int类型，范围很大。但是通常情况下，内存中数组容量不会太大，通常用不着h的高位。这会导致更频繁的冲突，即众多元素散列到同一个索引，导致部分索元素众多，部分索引元素过少，不平衡。为了解决这个问题，HashMap将低16位与高16位进行异或运算，意图减少冲突。

为了提高计算效率，HashMap规定桶的容量是2的次幂，使得(n - 1) & hash = hash % n，与运算比取模运算效率更高。当n是2的m次方，则n-1的低位是m个1，(n - 1)&hash就是将hash的低m位设为索引。

桶扩容

如果键值对越来越多，而桶不扩容，则单个索引的链表/红黑树会存放过多元素，影响查询效率。为了降低冲突，提高查询效率，因此桶扩容。

扩容时机是元素数量达到容量*加载因子，源码为size > threshold。默认加载因子是0.75，即数组中超过75%的索引不为空，为红黑树/链表，则扩容。

桶扩容源码在resize()方法。resize()方法第一部分是根据旧容量oldCap和旧阈值oldThr计算新容量newCap和新阈值newThr。主要有以下几种情况：

1. 调用无参构造器后初次调用resize()方法，oldCap=0, oldThr = 0.则newCap = 16, newThr = 12。
2. 调用有参构造器HashMap(int initialCapacity)后初次调用resize()方法,oldCap = 0,oldThr不为0且为2的次幂，则newCap=oldThr, newThr=newCap*loadFactor。
3. 桶容量oldCap>=2^30，则threadhold设为最大值，表示不再扩容。
4. oldCap >= 16, oldCap * 2 < 2^30，则newThr = oldThr * 2。即将阈值加倍。
   
   得到阈值之后执行扩容。桶索引元素非空有3种情况：1. 红黑树。2. 链表。 3. 单个键值对。如果是单个键值对，则重新映射到新索引。
   
   如果是链表，将其拆分为低位链表和高位链表，分别放在新桶的原索引和原索引+oldCap。
   假设oldCap=16, newCap=32，则扩容前hash=3,hash=19, hash=35的元素都存在j=3的链表上。扩容后hash=3，hash=35仍然在j=3，而hash=19会移动到j=19。HashMap试图将原链表的键值对均分到新链表的j及j + oldCap索引。
   HashMap采用拉链法存储键值对。
   

时间复杂度