一.HashMap概述
HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
二.HashMap的数据结构
在讨论哈希表之前，我们先了解下两种最基础的数据结构：数组和链表。
数组：存储空间连续，可以通过下标索引直接查找到指定位置的元素，因此赋值或查找效率高。但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。
链表：存储空间不连续，大数据量下对元素的访问效率很低，需要遍历链表进行查找，但是增删元素很快。
接下来，我们再看下HashMap中使用的数据结构：哈希表，即数组+链表的结构。比如我们要插入或查找某个元素，先通过哈希函数计算出当前元素在数组中的存储地址，再通过数组下标一次定位即可完成操作。然而，如果两个不同的元素通过哈希函数得出的存储地址相同怎么办？其实这就是所谓的哈希冲突，也叫哈希碰撞。哈希冲突的解决方案有多种，HashMap采用了链地址法，即数组+链表的方式。如下图所示，数组中的每个元素都是链表的头节点，指向一个链表。存储的元素被Hash后，得到数组下标，再把元素放在数组下标元素指向的链表上。
三.HashMap的实现原理
1.HashMap类的内部结构
在理解HashMap的实现原理之前，我们先了解下HashMap的几个字段。
table是一个Entry数组，是HashMap的主干数组，Entry是HashMap的基本组成单元。
size是HashMap中实际存储的key-value键值对的数量。
threshold为阈值，是HashMap可以容纳的键值对的最大个数，如果超过这个数目HashMap就要resize(扩容)，扩容后的HashMap容量是之前容量的两倍。threshold一般为capacity*loadFactor。
loadFactor是装载因子，默认值是0.75。
modCount主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; //Entry数组，HashMap的主干数组
transient int size; //实际存储的key-value键值对的个数
int threshold; //阈值，HashMap可以容纳的键值对的最大个数，一般为capacity*loadFactor
final float loadFactor; //装载因子
transient int modCount; //用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败
Entry是HashMap中的一个静态内部类，每个Entry都包含一个key-value键值对，代码如下：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next; //存储指向下一个Entry的引用
int hash; //对key的hashcode值进行hash运算后得到的值，存储在Entry中，避免重复计算
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
2.HashMap的构造方法
HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值：initialCapacity默认为16，loadFactory默认为0.75。我们看下其中一个构造器，从下面这段代码可以看出，在常规构造器中，没有为table数组分配内存空间（有一个入参为指定Map的构造器例外），而是在执行put操作时才真正构建table数组。
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);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init(); //init方法在HashMap中并没有实际实现
}
3.HashMap的put方法
接下来，我们来看看put方法的实现。
public V put(K key, V value) {
// 如果table数组为空数组，则调用inflateTable方法对数组进行填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity，默认值为16
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果key为null，存储位置为table[0]
if (key == null)
return putForNullKey(value);
int hash = hash(key); //对key的hashcode进一步计算，确保散列均匀
int i = indexFor(hash, table.length); //获取在table中的存储位置，即桶的位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果key已存在，执行覆盖操作，用新value替换旧value，并返回旧value
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++; //保证并发访问时，若HashMap内部结构发生变化，快速响应失败
addEntry(hash, key, value, i); //新增一个Entry
return null;
}
先来看看inflateTable这个方法，inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32。
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize); //capacity一定是2的次幂
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
再来看看hash函数：
//这个hash函数用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
以上hash函数计算出的值，通过indexFor方法进一步处理来获取实际的存储位置。indexFor方法非常巧妙，它通过h&(length-1)来获取在数组中的存储位置。而HashMap的table数组的长度总是2的次幂，当length总是2的次幂时，h&(length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
//返回数组下标
static int indexFor(int h, int length) {
return h & (length-1);
}
因此，获取一个key在table数组中的存储位置的流程是这样的：取key的hashcode值、计算hash值、位运算获取桶下标。
再来看看addEntry的实现，通过以下代码可以得知，当发生哈希冲突并且size大于阈值的时候，需要调用resize方法对Entry数组进行扩容。扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部转移过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。后面再详细关注下resize方法的实现原理。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
最后，来看下createEntry方法的实现，我们通过具体的例子来看插入元素的过程。例如，第一个键值对A进来，通过计算其key的hash得到index=0，因此Entry[0] = A。之后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B。如果又进来C,index也等于0,那么C.next = B,Entry[0] = C。可以发现，由于采用头插法，Entry[0]对应的链表存储的节点为：C->B->A，即链表中节点的顺序与插入的顺序是相反的。
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++;
}
4.HashMap的resize方法
上文已经提到，当发生哈希冲突并且size大于阈值的时候，需要调用resize方法对Entry数组进行扩容。HashMap的resize方法的实现原理及扩容带来的死循环问题，可以看我之前写的一篇文章:深入浅出HashMap扩容死循环问题。
5.HashMap的get方法
我们来看下get方法的实现，get方法通过key值返回对应value，如果key为null，则直接去table[0]处检索。如果key不为null，则调用getEntry方法获取对应的节点。可以发现，get方法的实现相对简单，通过三步：取key的hashcode值、计算hash值、位运算获取桶下标，定位到table[i]后，再遍历链表，通过e.hash == hash和key的equals方法来对比查找相同的key即可。
public V get(Object key) {
//如果key为null，则直接去table[0]处检索即可
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//根据key的hashcode值计算hash值
int hash = (key == null) ? 0 : hash(key);
//通过indexFor方法获取桶索引，然后遍历链表，通过equals方法对比找出对应节点
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 != null && key.equals(k))))
return e;
}
return null;
}
四.为什么重写equals一定要重写hashCode
这里可以看我之前写的一篇文章：为什么重写equals一定要重写hashCode。
五.总结
简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。根据一个key定位数组的存储位置分为三步：取key的hashcode值、计算hash值、位运算获取桶下标。如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组位置包含链表，对于put操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增，如果发生哈希冲突并且size大于阈值，还需要调用resize方法对Entry数组进行扩容；对于get操作，仍需遍历链表，然后通过key对象的equals方法逐一对比查找。
参考：
HashMap实现原理及源码分析
