HashMap会分四篇博客介绍，分别是基本思想、优化、线程安全和拓展。本文介绍基本思想。
HashMap 基本数据结构
Java HashMap解决哈希冲突，使用了成链法，故采用了数组Node[]加链表Node.next的数据结构。
Java8为降低链表查询的时间复杂度，引入了红黑树TreeNode。
class HashMap<Key, Value> {
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private static final int DEFAULT_TABLE_SIZE = 16;
private static final int TREEIFY_THRESHOLD = 8;
private int size; // HashMap 大小，即存储键值对的个数
private float loadFactor; // 负载因子
private int threshold; // 当前 table 长度和 loadFactor 负载因子下，能容下的最大键值对数
private Node[] table; // 存储键值对的数组
public HashMap() {
this(DEFAULT_TABLE_SIZE, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initSize, float initLoadFactor) {
this.loadFactor = initLoadFactor;
// table 的长度必须是 2^n，后面解释为什么这样设计
int tableSize = tableSizeFor(initSize);
// JDK 源码中 table 数组不在在构造函数中初始化，是 resize 时初始化
this.table = new Node[tableSize];
// 初始化阈值
this.threshold = (int) (this.table.length * this.loadFactor);
}
/**
* 节点数据结构，存储 Key 和 Value
*/
private static class Node<K, V> implements Map.Entry<K, V> {
int hash;
K key;
V value;
Node next;
}
/**
* 红黑树数据结构
*/
private static class TreeNode<K, V> extends Node<K, V> {
TreeNode<K, V> parent;
TreeNode<K, V> left;
TreeNode<K, V> right;
/**
* 将一个节点插入当前的红黑树
*/
TreeNode<K, V> putTreeVal(Node<K, V> node) { }
}
/**
* 求大于等于 cap 且为 2^n 的数
*/
static final int tableSizeFor(int cap) { }
}
如何存储 - 第一步：找桶
public void put(Key key, Value value) {
int hashCode = key.hashCode();
int hash = hash(hashCode);
// 等价于 index = hash % table.length
int index = hash & (table.length - 1);
}
/**
* 扰动函数：目的是增大 hashCode 的随机性，使其更散列。
*/
private int hash(int hashCode) { }
-
问题一：数组长度为什么设计成
用位运算代替乘除和求余运算，提高效率。2^n？
扩容是 2 倍扩容，可以直接使用左移运算；与运算可代替求余运算。 -
问题二：为什么与运算等价于求余运算？
首先明确，与运算不等价求余运算；m % n = m & (n-1)当且仅当 n 是 2 的次幂。
例如：
131101% 81000= (81000+ 50101) % 8 = 5（保留了 8 的后三位）
151111% 40100= (121100+ 30011) % 4 = 3（保留了 15 的后两位）
上面观察出，保留的位数正好是求模数1后面0的个数。从位运算看，就是和这么多个1做按位与。
即：131101% 81000= 131101& 70111；151111% 40100= 151111& 30011
图解
如何存储 - 第二步：找坑
public void put(Key key, Value value) {
Node head = table[index];
// 如果当前位置还没有存储，则直接创建节点
if (head == null) {
table[index] = new Node<>(hashCode, key, value);
}
// 红黑树则插入
else if (head instanceof TreeNode) {
((TreeNode<Key, Value>) head).putTreeVal(new Node<>(hash, key, value));
}
// 否则要遍历当前链表，为其找到合适位置
else {
int nodeCount = 0;
Node tail = null;
while (head != null) {
nodeCount++;
// 如果 key 已经存在，则直接替换 value，直接 return，不会 size++
if (head.hash == hashCode && head.key.equals(key)) {
head.value = value;
return;
}
// 找到尾结点
if (head.next == null) {
tail = head;
}
head = head.next;
}
// 循环结束，表示遍历到尾，未找到 key 存在，则新建一个节点
tail.next = new Node<>(hashCode, key, value);
// 链表长度超过阈值，转为红黑树
if (nodeCount > TREEIFY_THRESHOLD) {
treeifyBin(index);
}
}
// 最后记录键值对个数增加
size++;
}
/**
* 将 index 所在的链表转换为红黑树
*/
private void treeifyBin(int index) { }
扩容
private void resize() {
if (size <= threshold) {
return;
}
Node<Key, Value>[] oldTable = table;
int oldCap = oldTable.length;
// 计算新数组长度，并初始化新数组
int newCap = oldCap << 1;
table = new Node[newCap];
threshold = (int) (newCap * loadFactor);
// 遍历每个桶
for (int i = 0; i < oldCap; i++) {
Node<Key, Value> head = oldTable[i];
if (head == null) {
continue;
}
// 红黑树
if (head instanceof TreeNode) {
reassignTreeNode(head);
}
// 遍历链表，重新分配
else {
reassignNodeChain(head, i, oldCap);
}
}
}
/**
* 将链表上的节点重新分配
*/
private void reassignNodeChain(Node<Key, Value> head, int currentIndex, int oldCap) {
// 将一条链表拆成两条链表
Node<Key, Value> lowHead = null, lowTail = null;
Node<Key, Value> highHead = null, highTail = null;
do {
// 低位链，后面解释为什么这样判断
if ((head.hash & oldCap) == 0) {
if (lowHead == null) {
lowHead = head;
}
if (lowTail != null) {
lowTail.next = head;
}
lowTail = head;
}
// 高位链
else {
if (highHead == null) {
highHead = head;
}
if (highTail != null) {
highTail.next = head;
}
highTail = head;
}
} while ((head = head.next) != null);
// 将两条链表放入新 table，后面解释为什么这样放
table[currentIndex] = lowHead;
table[currentIndex + oldCap] = highHead;
}
/**
* 将红黑树上的节点重新分配
*/
private void reassignTreeNode(Node<Key, Value> head) { }
-
问题一：为什么一条链表上的节点一定会分为两条链？
设扰动后15，新数组长度8，原索引3。
根据上面解释的与运算原理，则新索引只会等于0011或0111。所以一定会分布在两条确定的链上。 -
问题二：新两条链在 table 中位置如何确定？
由问题一观察，0011 = 0011 | 0000或0111 = 0011 | 0100，即新索引等于原索引+0或+原数组长度。
图解
-
感谢
博客中使用了如下两篇博客中的图片，谢谢。同时这两篇博客也是非常好的学习HashMap的博客。
感谢 @前利 老师
感谢 @Carson_Ho 老师
