介绍
HashMap 是 Java 开发工具包 (JDK) 中提供的一个关键类，它实现了 Map 接口，用于存储键值对（key-value pairs）。HashMap 是一种基于哈希表的 Map 实现，它允许使用任何对象作为键（key）和值（value），并且它不保证元素的顺序。
底层是一个Node单向链表结点数组。
以下是 HashMap 类的一些主要特点和用法：
主要特点
- 非同步：
HashMap不是线程安全的，如果多个线程同时修改HashMap，可能会导致数据的不一致。如果需要线程安全的 Map，可以考虑使用ConcurrentHashMap。 - 允许空键和空值：与某些其他 Map 实现不同，
HashMap允许使用null作为键或值。 - 基于哈希表：
HashMap的性能主要依赖于哈希表的实现。它使用键的hashCode()方法来确定元素在内部数组中的位置，从而实现快速的查找、插入和删除操作。 - 无序性：
HashMap不保证元素的顺序。如果需要保持插入顺序或访问顺序，可以考虑使用LinkedHashMap。 - 性能优化：
HashMap使用哈希表来存储数据，它提供了快速的插入、删除和查找操作。然而，某些情况下，哈希表中的桶链表可能会变得很长，导致查找操作的效率降低。为了解决这个问题，Java 8 引入了红黑树（Red-Black Tree）作为哈希表中链表的替代方案。- 红黑树是一种自平衡二叉查找树，它在插入和删除操作时会自动调整树的结构以保持平衡。这使得红黑树在最坏情况下的查找、插入和删除操作的时间复杂度都是 O(log n)，其中 n 是树中节点的数量。
- 在
HashMap中，当链表的长度超过一定阈值（if (binCount >= TREEIFY_THRESHOLD - 1)，TREEIFY_THRESHOLD=8 ）时，链表会被转换为红黑树。这样可以提高查找操作的效率。同样地，当红黑树中的节点数量减少到一定程度时，红黑树会被转换回链表，以节省空间。
构造器
所有构造器最终指向一个底层方法：
代码语言：javascript复制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: "
//【1】 loadFactor);
this.loadFactor = loadFactor;
//【2】
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
// 【2.1】
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
// 【2.2】
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
}
public static int numberOfLeadingZeros(int i) {
// HD, Count leading 0's
if (i <= 0)
return i == 0 ? 32 : 0;
int n = 31;
//【2.1.1】
if (i >= 1 << 16) { n -= 16; i >>>= 16; }
if (i >= 1 << 8) { n -= 8; i >>>= 8; }
if (i >= 1 << 4) { n -= 4; i >>>= 4; }
if (i >= 1 << 2) { n -= 2; i >>>= 2; }
return n - (i >>> 1);
}源码分析：
- 构造器可以分别指定initialCapacity初始化容量，以及loadFactor负载因子
- 【1】loadFactor赋值
- 【2】tableSizeFor：它接受一个整数参数
cap，表示期望的初始容量，并返回一个经过调整的、适用于HashMap的哈希表容量。另外，使用了无符号右移操作符
>>>，对于-1，其二进制表示为全1（在 32 位整数中）。无符号右移操作会将-1的二进制表示向右移动指定的位数，并在左侧填充0。- 【2.1】
Integer.numberOfLeadingZeros(cap - 1)：这个方法计算cap - 1的二进制表示中前导零的数量。例如，对于cap = 16，cap - 1 = 15，其二进制表示为1111，没有前导零，所以返回值为0。 - 【2.2】这是一个三元运算符链，确保返回的容量是大于等于期望容量的最小的
2的幂，同时不超过HashMap的最大容量限制。
- 【2.1】
增删改查
添加&更新数据
下面我们挑选最基础的put(K,V)讲解源码
代码语言：javascript复制public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//【1】空哈希表则扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//【2】头结点为空，则新建一个节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//【3】头节点不为空，下面处理
else {
Node<K,V> e; K k;
//【4】检查头结点，是否正好待取出
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//【5】如果是红黑树，则增加树节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//【6】如果是链表，则进行下面处理
for (int binCount = 0; ; binCount) {
//【7】遍历到末尾节点
if ((e = p.next) == null) {
//【8】新增一个节点加进去
p.next = newNode(hash, key, value, null);
//【9】如果链表长度=7，那么就要转红黑树了，因为这样的查找效率更高
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//【10】转成红黑树节点
treeifyBin(tab, hash);
break;
}
//【11】遍历到待取出节点，e就是要找的元素
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//【12】e是已经存在的元素，说明哈希冲突了
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//【13】更新e节点的值
e.value = value;
// 【14】HashMap#afterNodeAccess是一个空实现
afterNodeAccess(e);
return oldValue;
}
}
// 【15】操作次数 1
modCount;
// 【16】如果哈希表数量已经满（size 1），则进行扩容
if ( size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
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;
}
// 【17】newCap在老的容器大小扩一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 【18】下次扩容阈值：在老的扩容阈值同样-大小扩一倍
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"})
//【19】初始化哈希表数组，容量为newCap
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//【20】遍历老的哈希表数组
for (int j = 0; j < oldCap; j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 【21】空节点，则填充填充元素（哈希低32位-按位与运算-确保在数组newCap下标范围内）
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 【22】红黑树节点，则调用api进行叶子节点的插入
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// 【23】普通Node节点，则进行链表节点插入
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;
}源码分析：
移除数据
源码：
代码语言：javascript复制public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//【1】检查是否命中哈希表元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//【2】
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
//【3】
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
//【4】节点是链表，说明有多个元素哈希出现了，索引下标冲突，链表遍历寻找
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//【5】找到Node节点
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//【6】红黑树节点
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//【7】普通节点
else if (node == p)
// 【8】p是哈希表元素，链表只有一个元素node，即node==p，那让p直接指向node节点的下一个元素即可了
tab[index] = node.next;
else
//【9】p是node的前驱节点，也是链表元素之一，让p指向node的下一个元素即可
p.next = node.next;
modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}源码讲解：
获取操作
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;
// 【1】
if ((tab = table) != null
&& (n = tab.length) > 0
&& (first = tab[(n - 1) & hash]) != null) {
// 【2】always check first node
if (first.hash == hash
&& ((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 【3】
if ((e = first.next) != null) {
// 【4】节点是红黑树节点
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 【5】节点是链表-节点逐个比较
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}源码分析：
- 【1】检查哈希表是否存在且长度大于0，以及哈希桶中是否有节点
- 【2】总是检查第一个节点，提高查找性能
- 【3】头结点有数据
- 【4】头结点指向的是TreeNode树节点类型，调用红黑树的查找方法
- 【5】头结点指向的是链表类型，顺序遍历节点，逐个比较
设计思想
1、源码的tab[index = (n - 1) & hash]，目的是什么？
这段代码的核心思想是利用位运算来计算索引。具体来说，(n - 1) & hash这个表达式的作用是将hash的高位舍弃，只保留与n - 1的位数相同的低位。这样可以确保计算出的索引值在0到n - 2之间，因为n - 1的二进制表示中所有位都是1。
为什么要这样做呢？这是因为HashMap的容量n通常是2的幂次方，即n = 2^k。在这种情况下，n - 1的二进制表示中所有位都是1，这样可以充分利用哈希值的低位信息，减少哈希冲突的概率。
总结一句：哈希值的不同低位信息被用来计算不同的索引位置，有助于减少哈希冲突。
2、HashMap的哈希表扩容时机是什么？
HashMap中的元素数量超过其容量（capacity）与负载因子（load factor）的乘积时。
3、HashMap的哈希桶节点什么时候从Node链表转为红黑树？
当HashMap准备插入一个新元素，而当前桶（bucket）已经是一个链表，添加完这个元素之后，链表长度会达到阈值（默认为8），此时会触发扩容。
转为红黑树是为了提高桶元素的访问效率。
