HashMap源码分析
HashMap简介
本文针对HashMap的源码分析基于JDK 7，JDK 8在HashMap的实现上有着较大幅度的改进和优化，这部分优化我将另起一篇来阐述。另外，本文仅分析HashMap众多方法中最常用的方法，其余方法有需要时再研究 
。
HashMap的继承关系如下。
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
HashMap继承自AbstractMap，同时实现了Map、Cloneable和Serializable接口。因此，HashMap可以被克隆，并支持序列化。另外，HashMap是一个非线程安全的，因此适合运用在单线程环境下。如果是在多线程环境，可以通过Collections的静态方法synchronizedMap获得线程安全的HashMap，如下代码所示。
Map<String, String> map = Collections.synchronizedMap(new HashMap<String, String>());
存储结构
针对每个键值对，HashMap使用内部类Entry来存储，Entry核心代码如下。
static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
final int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
从整体上看，HashMap底层的存储结构是基于数组和链表实现的。对于每一个要存入HashMap的键值对（Key-Value Pair），通过计算Key的hash值来决定存入哪个数组单元（bucket），为了处理hash冲突，每个数组单元实际上是一条Entry单链表的头结点，其后引申出一条单链表。HashMap的存储结构如下图所示。
关键属性
HashMap定义了几个关键属性，对应的源码如下。
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry[] table;
transient int size;
int threshold;
final float loadFactor;
-
DEFAULT_INITIAL_CAPACITY代表HashMap槽（bucket）的默认容量，且该容量必须为2的幂，具体原因会在下文解释。 -
MAXIMUM_CAPACITY代表HashMap槽（bucket）的最大容量，如果传入的容量大于1 << 30，那么实际容量会被MAXIMUM_CAPACITY替换。 -
DEFAULT_LOAD_FACTOR是默认的加载因子，用于计算HashMap扩容的threshold，当HashMap的实际元素容量达到总容量的threshold时，对HashMap进行扩容。 -
table是存储Entry的数组，每个Entry是一条单链表的头结点。 -
size代表HashMap键值对的数量。 -
threshold是HashMap决定是否执行执行扩容操作的阈值，threshold = capacity * load factor。 -
loadFactor表示HashMap实际加载因子，通过构造方法传入。若未指定，loadFactor等于DEFAULT_LOAD_FACTOR。
需要进一步解释的是loadFactor属性，loadFactor描述了HashMap发生扩容时的填充程度。如果loadFactor设置过大，意味着在HashMap扩容前发生hash冲突的机会越大，因此单链表的长度也就会越长，那么在执行查找操作时，会由于单链表长度过长导致查找的效率降低。如果loadFactor设置过小，那么HashMap的空间利用率会降低，导致HashMap在很多空间都没有被利用的情况下便开始扩容。
构造方法
HashMap定义了四个构造方法，源码如下。
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);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init(); // 在源码中，init方法体不执行任何操作。
}
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
当调用HashMap默认构造方法时，HashMap对象的属性均会被设置为默认值，包括设置加载因子（DEFAULT_LOAD_FACTOR）、扩容阈值（threshold）和table的初始大小。
如果在创建HashMap对象时指定了bucket容量initialCapacity，通过源码我们可以看出在初始化对象时不一定会直接使用initialCapacity，而是选取满足小于等于initialCapacity前提条件下最大的且是2的幂的一个值作为实际bucket的大小。
如果向构造方法传递的参数是一个Map对象m，那么putAllForCreate方法会重新散列m中的每个元素，将它们存入相应的bucket中。putAllForCreate方法及其调用的相关方法如下。
private void putForCreate(K key, V value) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
createEntry(hash, key, value, i);
}
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
static int indexFor(int h, int length) {
return h & (length-1);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
putAllForCreate方法遍历每一个键值对e，通过putForCreat方法将e散列到对应的bucket中。putForCreate方法调用indexFor来确定键值对散列的bucket的位置。indexFor通过h & (length-1)返回bucket的位置，接着遍历对应的单链表来决定是更新操作还是插入操作。
我们需要关注的地方是indexFor为什么通过计算h & (length-1)来获得bucket的位置，而不是通过计算h % length？
实际上，在HashMap中，h & (length-1) == h % length，但是需要一个前提：length必须满足是2的幂。这也正是在解释DEFAULT_INITIAL_CAPACITY和HashMap构造方法时强调的HashMap的bucket容量必须是2的幂。当length是2的幂，那么length的二进制数可以表示为1000...000，因此length - 1的二进制数为0111...111，当h与length - 1位与时，除了h的最高位的被修改为0，其余位均保持不变，这也正是实现了h % length的效果。只是相比于h % length，h & (length-1)的效率会更高。
HashMap的bucket容量必须为2的幂的另一个重要原因是一旦满足此条件，那么length即为偶数，length - 1便为奇数，所以length - 1的最后一位必为1。因此，h & (length - 1)得到的值既可能是奇数，也可能是偶数，这确保了散列的均匀性。如果length - 1是偶数，那么h & (length - 1)得到的值必为偶数，那么HashMap的空间便浪费了一半。
存取方法
我们分析HashMap使用频率最高的两个方法get方法和put方法，源码如下。
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
从HashMap获取get元素时，先计算Key的hash值，定位到数组中对应的bucket，然后开始遍历Entry单链表，直到找到需要的元素，否则返回null。
当我们向HashMap中put新的键值对时，HashMap首先检查Key是否等于null，若为null，则执行putForNullKey方法，putForNullKey方法对应的源码如下。
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this); // 不做任何操作
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
如果Key等于null，那么就将该键值对添加到table[0]的位置，同时，遍历table[0]处的单链表并将链表中所有节点的值都覆盖为新传递进来的键值对的值。因此，该位置永远只有一个值。
如果Key不等于null，那么通过indexFor定位到bucket，然后遍历单链表，如果存在Key相等的键值对，就用新值覆盖旧值，并返回旧值。如果在单链表中没有找到对应的Key，那么调用addEntry方法创建新的Entry节点至单链表（作为头节点）。addEntry及关联方法源码如下。
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
当addEntry把新增键值对插入单链表后，会判断是否需要扩容，即判断当前HashMap的元素的个数是否大于threshold。若需要扩容，那么调用resize方法进行2倍扩容。resize方法会在内部调用transfer方法，transfer方法遍历旧数组及单链表，并将每个键值对重新散列，可以意识到，这整个rehash的开销相当大。
线程安全
关于线程安全，我们想要知道的是HashMap在什么情况下会发生线程不安全的情况？实际上，在上文分析put方法时，当HashMap的容量超过了threshold时，便执行resize操作，resize就存在线程不安全的问题。
关于resize哪儿不安全，我推荐左耳朵耗子写的 疫苗：Java HashMap的死循环，这篇文章图文并茂的解释了在rehash过程中出现线程不安全问题的根源。
HashMap VS HashTable
HashTable和HashMap底层采用相同的存储结构，在很多方法的实现上二者的思路基本一致。最主要的区别主要有两点。
-
HashTable实现了所谓的线程安全，在HashTable很多方法上都加上了synchronized。 - 在
HashMap的分析中，我们发现当我们新增键值对时，HashMap是允许Key和Value均为null。但是HashTable不允许Key或Value为null，关于这一点我们可以通过查看HashTable源码得知。
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) { // 若value为空则抛出NullPointerException。
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode(); // 若key为空则抛出NullPointerException。
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}