HashMap作为Java集合框架中一个极其常用的框架，平时我们可能都已经十分熟悉他的用法了。然后面试中经常会被问到其内部的实现原理。本文就带各位来看一下，我们经常打交道的HashMap内部运行机制是怎样的。
一、基本介绍
HashMap作为集合框架中Map接口下的一个实现类，内部存储的是key-value的键值对形式。对于key的唯一性，HashMap采用如下方式：即先判断两个对象的hashcode方法返回值是否一致。如果不一致，那么果断不是相同key。如果一致，会再通过判断equals方法的返回值。这个时候，如果equals方法返回false，那么这两个key还是不相同。如果返回true，那么才证明这两个key相同。
请一定牢记这个判断规则，后面我们会在源码中再次遇到他。
二、HashMap的内部存储结构——Hash表
我们知道常用的两种数据存储结构：数组、链表。但是这两者都是存在一定弊端的。数组由于存储区间连续，因此查找起来是非常快的，但是其增删操作就比较慢。而链表由于存储区间不连续，因此查找起来慢。但是因为其通过引用的方式进行链接，所以增删操作很快。
而HashMap的内部存储结构Hash表则结合了这两者的优点。因为Hash表结构是数组与链表的结合体。
Hash表是个啥玩意？其实名字已经完全暴露了它的属性：以Hash算法为基础建立的一个表结构！
接下来我们看看Hash表的结构是怎样的：
从图中我们可以直观的看到整体的结构：纵向有一个数组，这个数组中可以存储entry的地方（绿色的小格子）被称为Bucket。每一个Bucket中只保存一个entry。每一个蓝色的格子就是一个entry。他里面不仅封装了key和value，还有一个指向下一个entry的引用next。entry的next不断指向下去就构成了横向的链表结构。
接下来我们看看Hash表结构在HashMap源码中的体现。
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
/**
* An empty table instance to share when the table is not inflated.
*/
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
}
源码中的table对应的就是纵向的数组结构。其元素entry实际就是HashMapEntry<K,V>。
接下来我们来看看HashMapEntry的源码，他以一个静态内部类的形式存在于HashMap类中：
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
HashMapEntry<K,V> next;
int hash;
/**
* Creates new entry.
*/
HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
我们看看这个HashMapEntry的成员变量就不难理解Hash表示意图中的横向链表了。除了key，value，hash值，还有一个指向下一个节点的next。
三、HashMap的put方法分析
我们已经知道了HashMap内部的Hash表结构了。那么我们看看HashMap是如何确定一个entry的位置的。这里我们会从HashMap的put方法开始分析。put方法源码如下：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<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;
}
我们先来看一下key不为null的时候。首先会通过一个方法对这个key算出一个hash值。之后通过indexFor函数来寻找这个key应该在的行号。这个行号其实就是数组table的角标。
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
indexFor方法十分简单，就是将hash与table的长度-1得到的值做了一个与运算。即：
一个key不为null的Entry所在的行号 = Entry的key的hash值 & （table长度-1）。
找到了要插入的entry所在的行号后，就需要遍历看看是不是已经存在拥有相同key的entry了。for循环中就是对横向链表的遍历。判断是否为相同key的规则我们之前已经给出过了：
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
如果发现是相同key，那么会将旧entry中的value更新成新entry中的value。
如果遍历完一整行没有发现相同的key，那么就调用addEntry方法将entry加入到链表里。
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
*
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
这里将要插入entry的key的hash，key，value封装成了一个HashMapEntry。并把新的entry放到了链表的头部，同时也是所在行的bucket位置。旧的链表头部则以构造的第四个参数传到了新封装的HashMapEntry对象的next上。同时，在创建完一个新的HashMapEntry之后，HashMap的size自增加1。
最后我们来看看当key为null的时候。程序直接调用了putForNullKey方法并返回。putForNullKey方法源码如下：
private V putForNullKey(V value) {
for (HashMapEntry<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;
}
需要注意的是for循环的
HashMapEntry<K,V> e = table[0]
这就表明了，key为null的entry必定是被放在第0行上。
四、HashMap的get方法分析
get相关的方法源码如下：
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
if (size == 0) {
return null;
}
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
我们仍旧先看key非null的情况：
程序进一步调用getEntry方法。getEntry方法仍旧走了跟put一样的老套路。通过indexFor方法确定行号。之后遍历链表，通过之前我们讲过的key判断规则寻找要找的entry。有则返回，无则给null。
key为null的情况，就是直接查表的第0行了。这里不再过多赘述。
五、HashMap的容量：负载因子，容量值，临界值
先来看HashMap的两个参数：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 4;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
这俩哥们干嘛的？好吧，这需要我们先看一下HashMap的构造方法。这里我们直接看空参构造相关的函数：
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
空参函数默认就传入了DEFAULT_INITIAL_CAPACITY和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;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Android-Note: We always use the default load factor of 0.75f.
// This might appear wrong but it's just awkward design. We always call
// inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
// to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
// the load factor).
threshold = initialCapacity;
init();
}可以看出，当initialCapacity小于MAXIMUM_CAPACITY这个最大值的时候，initialCapacity就等于DEFAULT_INITIAL_CAPACITY。之后倒数第二句代码是重点：threshold=initialCapacity。其中threshold是HashMap中的一个成员变量。到这里大家只需要先理解成初始化HashMap时，threshold被赋值成了DEFAULT_INITIAL_CAPACITY。（注意初始化HashMap时当然还会有其他情况，我们这里只是为了更方便的理解源码。）
然后，我们需要回过头去看put方法的前三行：
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
刚开始初始化HashMap时，table其实是一个空的数组。当我们在put一个entry时，程序会先判断，如果table为空数组，立刻调用inflateTable方法。参数就是之前我们看到的threshold。
inflateTable方法干了什么呢？源码如下：
final float loadFactor = DEFAULT_LOAD_FACTOR;
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
// Android-changed: Replace usage of Math.min() here because this method is
// called from the <clinit> of runtime, at which point the native libraries
// needed by Float.* might not be loaded.
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
}
传进来的DEFAULT_INITIAL_CAPACITY先经过计算变成了capacity。然后重点就在最后一句了，这个时候table被重新设置了数组长度。那么DEFAULT_INITIAL_CAPACITY是干嘛的就显而易见了。他就是table数组的默认初始化长度，又被称为默认初始化容量值。这个容量指的就是table数组的容量！
还需要注意一点，初始化完之后，threshold就变成了capacity与loadFactory的乘积。而loadFactory其实就是DEFAULT_LOAD_FACTOR。这个后面会用到。
当然HashMap也提供了其他构造函数供我们自己设置这个默认长度：
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
接下来我们分析DEFAULT_LOAD_FACTOR。他被称为负载因子。为了便于理解，这里只帖几段主要代码：
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
可以看到当添加entry时，会先判断当前HashMap的size是不是已经大于等于table容量*负载因子了。如果是直接调用resize方法，并将table的长度设置为原来的两倍，并重新设置了threshold的值。
简单总结一下，其实这件事很简单：
当初始化HashMap时会设置一个table的初始长度。这个初始长度被称为默认容量值。table的长度则被称为容量值。容量值*负载因子的大小被作为一个临界值。如果HashMap的size一旦大于等于这个临界值，那么不等table被装满，立刻将table的长度设置为原来长度的两倍以提供更多的bucket位置。
好了，到此，HashMap工作原理基本就分析完了。