HashMap
HashMap 是 Java 集合框架中的重要类，用于存储键值对，基于哈希表实现。它提供了快速的查找、插入和删除操作，是开发中常用的工具之一。
# 1. HashMap 的基本特性
- 底层结构：
HashMap基于哈希表（数组 + 链表/红黑树）实现，数组用于快速定位，链表或红黑树用于解决哈希冲突。 - 非线程安全：
HashMap不是线程安全的，如果在多线程环境中使用，可以使用ConcurrentHashMap代替。 - 允许键值为 null：
HashMap允许一个键为null，并且允许多个值为null。
# 2. 构造函数
HashMap 提供了多个构造函数来满足不同的初始化需求：
默认构造函数：创建一个默认初始容量为 16，负载因子为 0.75 的哈希表。
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75 this.threshold = (int) Math.min(DEFAULT_INITIAL_CAPACITY * loadFactor, MAXIMUM_CAPACITY + 1); table = (Node<K,V>[])new Node[DEFAULT_INITIAL_CAPACITY]; }指定初始容量的构造函数：可以指定哈希表的初始容量。
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) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
# 3. put 方法源码分析
put() 方法用于在 HashMap 中插入键值对，核心逻辑如下：
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;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((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);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
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(key)：计算键的哈希值，以确定其在数组中的位置。
- resize()：在数组未初始化或容量不足时进行扩容，扩容后的大小是原来的两倍。
- newNode()：创建一个新节点并插入到数组中。
- 链表处理：如果发生哈希冲突，将新节点添加到链表的末尾。
- 红黑树处理：如果链表长度超过阈值（默认为 8），将链表转换为红黑树，以提高查询效率。
# 4. 扩容机制 (resize() 方法)
HashMap 的扩容机制是其性能的关键点，当元素数量超过阈值时，会进行扩容，扩容后的容量是原来的两倍。
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)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 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) {
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;
}
- 扩容条件：当元素数量超过阈值时（
size > threshold），触发扩容。 - 新容量计算：扩容后的新容量是原容量的两倍。
- 节点重新分布：将旧数组中的节点重新计算哈希值并移动到新数组中。
# 5. 删除元素 (remove() 方法)
remove() 方法用于从 HashMap 中删除键值对，核心逻辑如下：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[(n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = p.next) != null);
}
}
if (node != null) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
- removeNode()：用于从哈希表中删除节点。
- 如果节点是红黑树节点，则调用
removeTreeNode()方法进行删除操作。 - 如果节点是链表节点，则直接调整前后节点的引用以删除目标节点。
- 如果节点是红黑树节点，则调用
- 缩容处理：在
remove()操作中，HashMap并不会立即缩容，而是通过减少size来动态调整哈希表的负载率。缩容在一般实现中较少发生，主要是通过调整阈值来避免频繁的扩容和缩容操作。
# 6. Hash 值的计算与哈希碰撞避免
HashMap 使用哈希函数将键转换为数组的索引，以实现快速查找。以下是 hash() 方法的源码：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hashCode() 与扰动函数：
hashCode()方法是每个对象都有的方法，用于生成一个整数值。HashMap通过对hashCode()的高位和低位进行异或运算（h ^ (h >>> 16)），将高位的信息混合到低位，称为扰动函数。这种做法是为了减少哈希碰撞，使哈希值更加分散，避免过多的元素集中在同一个哈希桶中。
关于哈希碰撞的举例说明： 个人认为应该结合 HashMap 本身的哈希寻址特点来举例。假设 HashMap 现在的 table 数组容量为16，并且hash方法的右移位数为 h >>> 4，现在有3个key，对应的hash值恰好是116+1=17、216+1=33、3*16+1=49，如果不进行高低位异或运算，那么它们在哈希寻址后都会存放到 table[1] 的哈希桶下（也就是所为的哈希碰撞）。如果进行了高低位异或运算，最终这三个key就可能存放在不同的哈希桶下，具体的高低位异或运算如下：
// 下面每一段的第一行表示hash值，第二行表示二进制，第三行表示右移4位后的结果，第四行表示高低位异或运算后的结果
// 17
// 0001 0001
// 0000 0001
// 0001 0000
// 33
// 0010 0001
// 0000 0010
// 0010 0011
// 49
// 0011 0001
// 0000 0011
// 0011 0010
最后，个人思考，会不会出现一种情况，明明几个key的hash值直接进行哈希寻址不会发生碰撞，但进行高低位异或运算后，反而发生了碰撞？ 这种情况下，肯定是各自的高位和低位都互不相同，但经过高低位异或运算后，恰好导致低位相同了。不过这种数据的出现率应该是远远小于上面所说的高位不同而低位相同的数据。
# 哈希碰撞的处理
- 链地址法：当多个键的哈希值相同时，会发生哈希碰撞。
HashMap通过链地址法来解决冲突，将冲突的键值对存储在同一个哈希桶中的链表或红黑树中。 - 链表到红黑树的转换：当链表长度超过
TREEIFY_THRESHOLD（默认为 8）时，链表会转换为红黑树，以提高搜索性能，将时间复杂度从 O(n) 降低到 O(log n)。
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)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 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) {
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;
}
- 扩容条件：当元素数量超过阈值时（
size > threshold），触发扩容。 - 新容量计算：扩容后的新容量是原容量的两倍。
- 节点重新分布：将旧数组中的节点重新计算哈希值并移动到新数组中。
# 7. 总结
HashMap 是基于哈希表的数据结构，具有高效的查找、插入和删除性能。通过对源码的分析，我们可以看到其对哈希冲突的处理方式包括链表和红黑树，扩容机制通过增加容量来保持较低的哈希冲突概率。在使用 HashMap 时，需要注意其非线程安全的特性，如果需要在多线程环境中使用，可以考虑使用 ConcurrentHashMap。
上次更新: 2024/10/31, 18:28:18