简介
HashMap 采用 key/value 存储结构，每个 key 对应唯一的 value，查询和修改的速度都很快，能达到 O(1)的平均时间复杂度。它是非线程安全的，且不保证元素存储的顺序。
继承体系
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable{...}
HashMap 实现了 Cloneable，可以被克隆。
HashMap 实现了 Serializable，可以被序列化。
HashMap 继承自 AbstractMap，实现了 Map 接口，具有 Map 的所有功能。
存储结构
在 Java1.8 中，HashMap 的实现采用了（数组 + 链表 + 红黑树）的复杂结构，数组的一个元素又称作桶。
重要属性
//默认的初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大的容量为2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
容量为什么是 2 的整数次幂？
减少哈希冲突，均匀分布元素。
2 的幂次方减 1 后每一位都是 1，让数组每一个位置都能添加到元素。
例如十进制 8，对应二进制 1000，减 1 是 0111，这样在&hash 值使数组每个位置都是可以添加到元素的，如果有一个位置为 0，那么无论 hash 值是多少那一位总是 0，例如 0101，&hash 后第二位总是 0，也就是说数组中下标为 2 的位置总是空的。
如果初始化大小设置的不是 2 的幂次方，hashmap 也会调整到比初始化值大且最近的一个 2 的幂作为 capacity。
//当桶的使用数量达到多少时进行扩容，threshold = capacity * loadFactor
int threshold;
Threshold 是通过初始容量和 LoadFactor 计算所得，在初始 HashMap 不设置参数的情况下，默认边界值为 12。
//装载因子，用来计算容量达到多少时才进行扩容，默认装载因子为0.75。
final float loadFactor;
为什么装载因子是 0.75？
1.出于容量和性能之间平衡的结果
对于使用链表法的哈希表来说，查找一个元素的平均时间是 O(1+n)，这里的 n 指的是遍历链表的长度，因此加载因子越大，对空间的利用就越充分，这就意味着链表的长度越长，查找效率也就越低。如果设置的加载因子太小，那么哈希表的数据将过于稀疏，对空间造成严重浪费。
2.提升扩容效率
HashMap 的容量（capacity）有一个固定的要求，那就是一定是 2 的幂。所以，如果负载因子是 3/4 的。话，那么和 capacity 的乘积结果就可以是一个整数。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
Node 是一个典型的单链表节点，其中，hash 用来存储 key 计算得来的 hash 值。Node 类作为 HashMap 中的一个内部类，除了 key、value 两个属性外，还定义了一个 next 指针。当有哈希冲突时，HashMap 会用之前数组当中相同哈希值对应存储的 Node 对象，通过指针指向新增的相同哈希值的 Node 对象的引用。
什么是哈希冲突
哈希是通过对数据进行再压缩，提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的，而数据可能比较多，导致经过哈希函数处理后仍然有不同的数据对应相同的哈希值。这时候就产生了哈希冲突。
哈希冲突还有个通俗易懂的原理----鸽巢原理（也叫抽屉原理）。这个原理本身很简单，它是说，如果有 10 个鸽巢，有 11 只鸽子，那肯定有 1 个鸽巢中的鸽子数量多于 1 个，换句话说就是，肯定有 2 只鸽子在 1 个鸽巢内。
重要方法
查询
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果桶的数量大于0 并且待查找的key所在的桶的第一个元素不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//检查第一个元素是不是要查找的元素，如果是直接返回
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;
}
插入
public V put(K key, V value) {
return putVal(hash(key), key, value, false, 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;
//如果桶的数量为0，则初始化
if ((tab = table) == null || (n = tab.length) == 0) //线程问题
n = (tab = resize()).length;
//(n - 1) & hash 计算元素在哪个桶中，如果这个桶中还没有元素，则把这个元素放在桶中的第一个位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//如果桶中已经有元素存在了
Node<K,V> e; K k;
//如果桶中第一个元素的key与待插入元素的key相同，保存到e中用于后续修改value值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
//如果第一个元素是树节点，则调用树节点的putTreeVal插入元素
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//遍历这个桶对应的链表，binCount用于存储链表中元素的个数
for (int binCount = 0; ; ++binCount) {
//如果链表遍历完了都没有找到相同key的元素，说明该key对应的元素不存在，则在链表最后插入一个新节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果插入新节点后链表长度大于8，则判断是否需要树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果待插入的key在链表中找到了，则退出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
//判断是否需要替换旧值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判断是否需要扩容
if (++size > threshold) //线程问题
resize();
afterNodeInsertion(evict);
return null;
}
在判断是否出现 hash 碰撞中（即注释线程问题的判断），假设两个线程 A、B 都在进行 put 操作，并且 hash 函数计算出的插入下标是相同的，当线程 A 执行完第六行代码后由于时间片耗尽导致被挂起，而线程 B 得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程 A 获得时间片，由于之前已经进行了 hash 碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程 B 插入的数据被线程 A 覆盖了，从而线程不安全。
除此之外，最后的是否需要扩容判断里有个 ++size，还是线程 A、B，这两个线程同时进行 put 操作时，假设当前 HashMap 的 zise 大小为 10，当线程 A 执行到该行代码时，从主内存中获得 size 的值为 10 后准备进行 +1 操作，但是由于时间片耗尽只好让出 CPU，线程 B 拿到 CPU 还是从主内存中拿到 size 的值 10 进行 +1 操作，完成了 put 操作并将 size=11 写回主内存，然后线程 A 再次拿到 CPU 并继续执行(此时 size 的值仍为 10)，当执行完 put 操作后，还是将 size=11 写回内存，此时，线程 A、B 都执行了一次 put 操作，但是 size 的值只增加了 1，所有说还是由于数据覆盖又导致了线程不安全。
当然 JDK1.8 已经比 JDK1.7 做了优化，在 JDK1.7 中，当并发执行扩容操作时会造成环形链和数据丢失的情况。在 JDK1.8 中，在并发执行 put 操作时会发生数据覆盖的情况。
扩容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
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)
//如果旧容量的两倍小于最大容量并且旧容量大于默认初始容量（16），则容量扩大为两倍，扩容门槛也扩大为两倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
//使用非默认构造方法创建的map，第一次插入元素会走到这里
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//调用默认构造方法创建的map，第一次插入元素会走到这里
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
//如果新扩容门槛为0，则计算为容量*装载因子，但不能超过最大容量
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//把桶赋值为新数组
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//清空旧桶，便于GC回收
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 order
//如果这个链表不止一个元素且不是一颗树，则分化成两个链表插入到新的桶中去
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;
else
loTail.next = e;
loTail = e;
}
else {
//元素放在高位链表中
if (hiTail == null)
hiHead = e;
else
hiTail.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;
}
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于