简介
- HashMap 是基于哈希表的数据结构，用于存储键值对（key-value）。
- 其核心是将键的哈希值映射到数组索引位置，通过数组 + 链表（在 Java8 及之后是数组 + 链表 + 红黑树）来处理哈希冲突。
- HashMap 使用键的 hashCode（）方法计算哈希值，并通过 indexFor 方法（JDK1.7 及之后版本移除了这个方法，直接使用 (n－1）&hash）确定元素在数组中的存储位置。哈希值是经过一定扰动处理的，防止哈希值分布不均匀，从而减少冲突。
- HashMap 的默认初始容量为 16，负载因子为 0.75。也就是说，当存储的元素数量超过 16×0.75=12 个时，HashMap 会触发扩容操作，容量 x2 并重新分配元素位置。这种扩容是比较耗时的操作，频繁扩容会影响性能。
工作原理
HashMap 使用哈希表来存储数据。键的哈希值通过 hash() 方法计算，然后通过哈希函数将哈希值映射到数组的索引位置上。通过链地址法（chaining）来解决哈希冲突，即在每个数组索引处存储一个链表（Java 8 及之后版本采用红黑树以提高性能）。
public int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
常用操作
- 添加元素
map.put(k,v);
- 获取元素
Object v = map.get(k);
- 移除元素
Object v = map.remove(k);
- 遍历元素
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
优缺点
优点：快速查找、可灵活存储不同类型的对象（允许出现 null 键和值，null 键只能存在一个）。
缺点：线程不安全，无序。
java8 对 HashMap 的改造
数据结构
- 变化：从数组 + 链表改为数组 + 链表或红黑树。
- 当发生哈希冲突时，元素会被存储在链表中。如果链表过长，则转换为红黑树，将查找时间复杂度由 O(n) 降低至 O(logn)。
链表插入方式
- 变化：从头插法改为尾插法。
- 说明：在 JDK 1.7 中，新元素被放置到链表头部；而在 JDK 1.8 中，遍历链表并将新元素放置到链表尾部。
- 原因：JDK 1.7 的头插法在扩容时可能导致链表反转，在多线程环境下可能会产生环状结构，而尾插法则避免了这一问题。
扩容机制
- 变化：减少了散列函数的操作次数。
- 说明：JDK 1.7 的散列函数执行了四次位移和异或操作，而 JDK 1.8 只执行一次
- 原因：尽管多次操作可能提供更好的分布性，但实际上边际效益不大，简化后的散列函数提高了计算速度且对于大多数应用场景来说足够有效。
源码解析
put
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) {
// 声明变量 `tab` 表示哈希表数组，`p` 表示当前节点，`n` 表示数组长度，`i` 表示数组索引。
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
//如果没有定义大小，会进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//通过 (n - 1) & hash 计算键对应的数组索引 i,判断下标位置有没有数据，没有的话把当前值存放在这个下标的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//当前下标位置已经有值的情况
Node<K,V> e; K k;
//要put的节点和已有的节点hash和key都相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断当前节点的类型，类型为TreeNode的话插入红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
//判断当前节点的next是否有值，直到遍历到没值的时候将节点插入到链表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//TREEIFY_THRESHOLD=8,链表容量到达8的时候会将链表构建为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
//若遍历过程中找到相同的键，跳出循环。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//key冲突的时候所执行的逻辑（注意区分hash冲突和key冲突）
if (e != null) { // existing mapping for key
V oldValue = e.value;
//原有的值为null或onlyIfAbsent为false进行值的替换
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//LinkedHashMap中实现了该方法-作用是调整节点顺序
afterNodeAccess(e);
//返回原有的值
return oldValue;
}
}
++modCount;
//插入新的节点后判断是否要扩容
if (++size > threshold)
resize();
//LinkedHashMap中有具体实现，用于节点插入后的操作
afterNodeInsertion(evict);
//返回null表示键原来不存在
return null;
}
resize
该方法的主要作用是初始化哈希表或者将哈希表的大小扩大一倍。
//方法不能被重写，返回Node<K,V>即新的hashMap
final Node<K,V>[] resize() {
//旧的hashMap
Node<K,V>[] oldTab = table;
//旧容量及阈值
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
//新容量及阈值
int newCap, newThr = 0;
//根据旧的容量及阈值来决定新的容量及阈值
if (oldCap > 0) {
//旧容量达到最大容量 `MAXIMUM_CAPACITY`，将阈值设为 `Integer.MAX_VALUE`，不再扩容，直接返回旧哈希表。
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
}
//初始容量设置为0但阈值大于0，新容量=旧阈值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//旧容量和旧阈值都为 0：使用默认初始容量和默认负载因子计算新阈值
newCap = DEFAULT_INITIAL_CAPACITY; //16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //0.75*16
}
//若新阈值仍为 0，则根据新容量和负载因子计算新阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//使用新的容量定义新的hashMap
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) {
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
//比如老数组容量是16，那下标就为0-15
//扩容操作*2，容量就变为32，下标为0-31
//低位：0-15，高位16-31
//定义了四个变量
// 低位头 低位尾
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;
}