共计 3639 个字符，预计需要花费 10 分钟才能阅读完成。
序
HashMap 是 Java 中常用的 Map 接口的实现类，因为在日常工作中非常频繁的出现，所以在大部分的 Java 面试中都会问几个关于 HashMap 的问题。掌握 HashMap 的实现原理，已经是 Java 程序员的基础操作了。
Map 接口
映射（Map）是一种用于存放键 / 值对的数据结构。如果提供了键，就能直接找到相对应的值。HashMap（哈希映射）是 Map 接口的一个实现类，主要使用哈希来实现键与值的映射。
定义。映射是一种用于存放键 / 值对的数据结构，主要支持两种操作：插入（put），即将一组新的键值对存入映射中；查找（get），即根据给定的键得到相应的值。
HashMap 的底层数据结构
HashMap 的底层是用散列表实现的，散列表是一种用数组来存储键值对的数据结构，它使用一个散列函数将键转换成数组的一个索引然后存储值。不过会有不同的键被散列成同个索引的情况出现，这叫做碰撞冲突。HashMap 用拉链法来解决这个问题，即散列表数组中的每个元素都指向一条链表，链表中的每个节点都存储了被散列到这个索引的键值对。
HashMap 的散列函数
根据散列表的定义我们知道，想要弄清楚 HashMap 的实现，我们首先需要知道 HashMap 的散列函数是怎么实现的，即 HashMap 是如何将一个键映射到数组的索引的。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
上面就是 HashMap 的散列函数源码了，可以看到如果键为 null 的话它的索引固定为 0，即 HashMap 是支持使用 null 作为键的。如果键不为 null 就用 Java 对象都有的 hashCode 方法获得一个哈希值，并将这个哈希值的低 16 位与高 16 位做异或处理，高 16 位不变。
这里有个问题就是为什么不直接用键的 hashcode，而要将 hashcode 的低 16 位与高 16 位做异或处理？这里是因为有三个前提：
int 有 32 位
HashMap 的数组长度都是 2 的幂
获取数组索引需要将键的哈希值和数组长度 - 1 做一个与操作（&）得到，即 tab[(n – 1) & hash]
首先因为 HashMap 的数组长度都是 2 的幂，（n – 1）的高 16 位都是 0，所以只有键的低 16 位参与索引运算。如果直接用键的 hashcode 的话，就会有很多碰撞冲突，所以用这种方法使得 hashcoede 的高 16 位也参与到索引的运算中来。下面是字符串“1234”在数组长度为 16 的索引运算过程：
public static void main(String[] args) {
int hashcode = “1234”.hashCode();
System.out.println(Integer.toBinaryString(hashcode));
// 输出为 10111 0000100001000010
System.out.println(Integer.toBinaryString(hashcode >>> 16));
// 输出为 10111
System.out.println(Integer.toBinaryString(hashcode ^ (hashcode >>> 16)));
// 输出为 10111 0000100001010101
System.out.println(Integer.toBinaryString(16 – 1));
// 输出为 1111
System.out.println(Integer.toBinaryString((16 – 1) & (hashcode ^ (hashcode >>> 16))));
// 输出为 101
}
碰撞冲突
虽然 HashMap 对散列函数做了很多优化，但是碰撞冲突还是不可避免的会出现。为了解决这个问题 HashMap 使用了拉链法，使用链表来存储碰撞冲突的键值对。并在 JDK 8 中进行了优化，当链表长度到达某个指定值时 HashMap 会自动将链表优化为红黑树。频繁碰撞冲突还可能是因为数组长度不够的原因，HashMap 还会根据键值对的数量进行自动扩容。
自动扩容
在讲 HashMap 的自动扩容前，先来看看 HashMap 有哪些相关的属性：
Node<K,V>[] table; 存放键值对的数组
int size; 已存放键值对的数量
int threshold; 当键值对的数量等于这个值的时候 HashMap 将进行扩容，值等于数组长度 * loadFactor
final float loadFactor; 负载因子，用于计算 threshold 的值，默认值为 0.75
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 数组长度的默认值 16
根据这些属性可以知道，HashMap 的自动扩容会根据数组长度和负载因子的积得到一个 threshold 的值，当键值对的数量等于 threshold 时就会开始扩容，下面是扩容的源码。大概过程是新建一个长度为旧数组两倍的新数组，并将原有的键值对都重新映射到新数组上。
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;
}
后记
这次主要是理解了一下 HashMap 的实现原理，特别重点写了很多关于散列函数的理解，并没有按照源码一行行的去理解。之所以这样是因为写这篇的动力主要来源于面试……而面试则只要讲下原理就可以了，并不需要把源码背下来。之前看 HashMap 的时候对散列函数都是跳过去的，只知道是用来计算键的 hash，不知道里面的原理。其实还有链表转红黑树的地方没有弄清楚，主要是红黑树不怎么理解，基础的重要性体现了出来。
我的博客
