1. 实现原理
在JDK 7中， HashMap是通过单链表和数组实现的，采用头插法插入链表
在JDK 8 中，实现的方法是数组+链表/红黑树
HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。需要特别注意，主干数组的长度一定是2的次幂。
//HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组{}
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
为什么使用头插法：
- 对于链表，头插法是最快的插入方法（不需要遍历）
2.Entry
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的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
3. 几个重要字段
//实际存储的key-value键值对的个数
transient int size;
//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold
int threshold;
//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;
//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
4. 构造器
HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值
initialCapacity默认为16，loadFactory默认为0.75
我们看下其中一个
public HashMap(int initialCapacity, float loadFactor) {
//此处对传入的初始容量进行校验，最大不能超过MAXIMUM_CAPACITY = 1<<30(230)
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();//init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现
}
从上面这段代码我们可以看出，在常规构造器中，没有为数组table分配内存空间（有一个入参为指定Map的构造器例外），而是在执行put操作的时候才真正构建table数组
5. put方法
基本原理
伪代码如下：
void put(key, value){
int hashcode = key.hashCode();
int index = hashcode % table.length;
table[index] = new Entry(key, value, table[index]); // 第三个属性为next属性
}
思想：
通过调用
Object.hashCode()获得某个对象的哈希值作为标识的依据将哈希值映射为某个
[0, table.length - 1]的数作为其在数组中的下标index，该值满足这样的特点。一种简单的方法是取余操作（具体实现有其他的方法）。
不越界
均匀分布
用Key和Value构造一个Entry对象，然后将该对象插到由
table[index]指示的某单链表头节点前。新的Entry对象成为头节点。
table[index]指向该新对象。
源码：
public V put(K key, V value) {
//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(24=16)
if (table == EMPTY_TABLE) {
inflateTazheyixible(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;
}
注意：put方法有遍历逻辑以确定冲突链表是否有key相同的键值对。当无冲突时，链表仍然需要被完全遍历。头插法的优势在此方法并没有体现。复杂度O(n)
1. 数组初始化
如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(24=16)
- inflateTable方法。此方法的需要解决的主要问题是确定Entry数组的长度
/**
* Inflates the table.
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 首先计算容量, toSize 容量为 threshold,在构造方法中，
// threshold默认等于初始容量，也就是16
int capacity = roundUpToPowerOf2(toSize);
// 然后重新算成 threshold的值，默认为 capacity * loadFactor
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//初始化数组 容量为 capacity
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
长度capacity通过roundUpToPowerOf2(int i)提供，该方法旨在返回一个比入参number大的、最接近的2的幂次方数
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
核心方法Integer.highestOneBit(int i)见之前的文章Java源码评析-Integer.HighestOneBit(int num)
这里需要减一再左移一位，很好地解决了像16这种特殊值的情况
2. 处理Key为null的情况
if (key == null)
return putForNullKey(value);
putForNullKey方法
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
前面的操作将null作为一个具体的key处理。注意到addEntry(0, null, value, 0)，此时将null:value键值对的哈希值设置为0，并将其放到table[0]或table[0]的冲突链上
3. 计算hash值
传入key计算hash值。
int hash = hash(key);
这里并非直接通过Object.hashCode()方法得到哈希值，而是通过定义的hash()方法计算得到。
hash方法
//对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
hashSeed为哈希种子，默认为0。这里的一系列的位移、异或操作的目的是：尽可能多地利用k.hashCode()的位数，保证最终获取的存储位置尽量分布均匀
4. 计算对应的数组的下标
int i = indexFor(hash, table.length);//获取在table中的实际位置
indexFor方法
/**
* 返回数组下标
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
与操作：哈希值与数组长度-1
效果：
1 0 0 1 0
& 0 1 1 1 1
__________________
0 0 0 1 0 = 2
数组长度减一的目的：数组长度都是2的幂次方数，减去一之后的数都是001111···111的形式
与操作截留了hash对应位置，使其取值在[0, table.length - 1]范围内，而且因为哈希值的特性，满足均匀分布的特点，这样取到的index满足要求。
所以最终存储位置的确定流程是这样的：
[图片上传失败...(image-adbc86-1599290246163)]
扩容和插入
扩容的目的：缩短冲突链表，提高查询速度
注意：JDK1.7 扩容线程不安全
addEntry方法
扩容检测和操作
插入
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超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
size >= threshold
size：当前键值对的数目
阈值threshold = table.length * loadFactory`
loadFactory：加载因子float
null != table[bucketIndex]
table的指定位置不为空
扩容操作：
resize(2 * table.length);
扩容后的数组长度指定为当前数组长度的两倍。
resize(int newCapacity)
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// 如果数组已经最大，不扩容
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
扩容的步骤：
创建新的数组
Entry[] newTable = new Entry[newCapacity];转移原数组的内容到新数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index也可能会发生变化，需要重新计算index。
transfer方法
大部分时候rehash的取值为false
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newT able.length;
//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。
e.next = newTable[i];
newTable[i] = e;
// 将e指定为原链表的下一个元素（回到原链表中）
e = next;
}
}
}
双重循环，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去
:warning: 扩容前某一个index对应的链表在新的数组中的index对应的链表，顺序相反
:warning: 扩容后每个元素的在新数组中的下标只有两种情况
原数组下标与新数组新数组的下标相同
原数组下标 + OldTable.length = 新数组下标
原数组长度16，扩容为32
1. 假设原元素哈希值为
0101-1001
& 0000-1111
= 0000-1001(原数组中的下标)
0101-1001
& 0001-1111
= 0001-1001(新数组中的下标)
可以发现：原数组下标二进制最高位前一位为1即为新数组的下标，
即原数组下标 + OldTable.length = 新数组下标
2. 假设原元素哈希值为
0100-1001
& 0000-1111
= 0000-1001(原数组中的下标)
0100-1001
& 0001-1111
= 0000-1001(新数组中的下标)
可以发现：原数组下标与新数组新数组的下标相同
多线程扩容导致的死锁
原数组和链表
设同时有两个线程执行put操作，而且都同时进行到了resize中的扩容操作。
- 此时每一个线程都创建了一个新的数组
假设某一线程A正常执行完毕，另一线程B执行到了语句Entry<K,V> next = e.next上时由于某种原因阻塞了一段时间，当B唤醒后会出现如下图的状况：next2和e2代表线程B所属的next和e
此时B线程内部的引用next和2所指向了线程A执行完毕所创建的对象，而且线程B自身创建的数组是空的状态
- B线程继续下面的语句：
e.next = newTable[i];
- newTable[i] = e;
- e = next;
- 重新开始里层循环开始 Entry<K,V> next = e.next;
- e.next = newTable[i];
第二次循环结束
- 第三次循环 Entry<K,V> next = e.next;
:warning: next指针指向了NULL
- e.next = newTable[i];
问题出现：出现了循环链表
继续下去
- newTable[i] = e;
e = next;
循环结束，而且线程B结束后会把这个数组赋值给类中定义的数组。
当get方法访问这个index时，会出现死循环。
根本原因在于第1步时e和next已经出现掉转的情况
initHashSeedAsNeeded(int capacity)
初始化哈希种子（用于需要满足自定义的高级哈希算法需求时，期望提高哈希算法的散列性）
发现上述流程中rehash的值由initHashSeedAsNeeded提供，要求传入数组的容量
hashSeed默认为0，唯有currentAltHashing ^ useAltHashing的结果不是0时hashSeed的值才会改变，
===> useAltHashing为true时
===> capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD时
===> capacity >= jdk.map.athashing.threshold (一个JDK环境变量)
final boolean initHashSeedAsNeeded(int capacity) {
//通过上面的过程,我们知道了currentAltHashing =false
boolean currentAltHashing = hashSeed != 0;
//useAltHashing = false
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
// false ^ false 结果为false，switching为false
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
//返回false
return switching;
}
其他
ArratList：底层实现：数组
LinkedList: 底层实现：链表
一般来说，链表的插入快，查询慢，数组相反
