HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）HashMap不保证映射的顺序，特别是它不保证该顺序恒久不变。
HashMap底层采用哈希表结构（数组+链表、JDK1.8后为数组+链表+红黑树）实现，结合了数组和链表的优点：
数组优点： 通过数组下标可以快速实现对数组元素的访问，效率极高；
链表优点： 插入或删除数据不需要移动元素，只需修改节点引用，效率极高。
HashMap图示如下：
HashMap内部使用数组存储数据，数组中的每个元素类型为Node<K,V>：
//Node包含了四个字段：hash、key、value、next，其中next表示链表的下一个节点。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<k,V> next; //链表的下一个节点
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final boolean equals(Object o) {
if (o == this) return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
JDK1.8之前，HashMap底层实现用的是数组+链表。（JDK1.8以后用数组+链表+红黑树）。
HashMap通过hash方法计算key的哈希码，然后通过（n-1）&hash 公式（n为数组长度,初始化数组默认长度为16），得到key在数组中存放的下标。
当两个key在数组中存在的下标一致时（哈希冲突，哈希碰撞），数据将以链表的方式存储。
在链表中查找数据必须从第一个元素开始一层一层往下找，直到找到为止，时间复杂度为O(N)，所以当链表长度越来越长时，HashMap的效率越来越低。
哈希码如何计算？添加链接描述
如何解决？
加入红黑树
当链表中的元素超过8个（TREEIFY_THRESHOLD）并且数组长度大于64（MIN_TREEIFY_CAPACITY）时，会将链表转换为红黑树，转换后数据查询时间复杂度从O(N)变为O(logN)。
红黑树的节点使用TreeNode表示：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
...
}
HashMap包含几个重要的变量：
// 数组默认的初始化长度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 数组最大容量，2的30次幂，即1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转换为红黑树的长度阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转换为链表的长度阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 链表转换为红黑树时，数组容量必须大于等于64
static final int MIN_TREEIFY_CAPACITY = 64;
// HashMap里键值对个数
transient int size;
// 扩容阈值，计算方法为 数组容量*加载因子
int threshold;
// HashMap使用数组存放数据，数组元素类型为
Node<K,V>transient Node<K,V>[] table;
// 加载因子
final float loadFactor;
// 用于快速失败，由于HashMap非线程安全，
//在对HashMap进行迭代时，如果期间其他线程的参与
//导致HashMap的结构发生变化了（比如put，remove等操作），
//直接抛出ConcurrentModificationException异常
transient int modCount;
加载因子也叫扩容因子，用于决定HashMap数组何时进行扩容。比如数组容量为16，加载因子为0.75，那么扩容阈值为数组容量加载因子，160.75=12，即HashMap数据量大于等于12时，数组就会进行扩容。
我们都知道，数组容量的大小在创建的时候就确定了，所谓的扩容指的是重新创建一个指定容量的数组，然后将旧值复制到新的数组里。扩容这个过程非常耗时，会影响程序性能。
所以加载因子是基于容量和性能之间平衡的结果：
当加载因子过大时，扩容阈值也变大，也就是说扩容的门槛提高了，这样容量的占用就会降低。但这时哈希碰撞的几率就会增加，效率下降；
当加载因子过小时，扩容阈值变小，扩容门槛降低，容量占用变大。这时候哈希碰撞的几率下降，效率提高。
可以看到容量占用和性能是此消彼长的关系，它们的平衡点由加载因子决定，0.75是一个即兼顾容量又兼顾性能的经验值。
通过hash方法计算key的哈希码添加链接描述
HashMap通过hash方法计算key的哈希码，然后通过（n-1）&hash 公式（n为数组长度，初始化数组默认长度为16），得到key在数组中存放的下标。
长度阈值大于8，数组容量必须大于等于64
存储数据的table字段使用transient修饰，通过transient修饰的字段在序列化的时候将被排除在外，那么HashMap在序列化后进行反序列化时，是如何回复数据的呢？HashMap通过自定义的readObject/writeObject方法自定义序列化和反序列化操作。这样做出于以下两点考虑：
1)table一般不会存满，即容量大于实际键值对个数，序列化table未使用的部分不仅考虑时间也浪费空间；
2)key对应的类型如果没有重写hashCode方法，那么它将调用 Object的hashCode方法，该方法为native方法，在不同的JVM下实现可能不同；换句话讲，同一个键值在不同的JVM环境下，在table中存储的位置可能不同，那么在反序列化table操作时可能会出错。
所以在HashXXX类中（），我们可以看到，这些类用于存储数据的字段都用transient修饰，并且都自定义了readObject/writeObject方法。
put操作过程总结：
public V put(K key, V value) { r
eturn putVal(hash(key), key, value, false, true);
}
put方法通过hash函数计算key对应的哈希值，hash函数源码如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
对于 32 位的处理器，会分成高（左边的） 16 位和低（右边的） 16 位int类型的数值是4个字节的，右移16位异或可以同时保留高16位于低16位的特征
如果key为null，返回0，不为null，则通过(h = key.hashCode()) ^ (h >>> 16)公式计算得到哈希值。该公式通过hashCode的高16位异或低16位得到哈希值，主要从性能、哈希碰撞角度考虑，减少系统开销，不会造成因为高位没有参与下标计算从而引起的碰撞。得到key对应的哈希值后，再调用putVal(hash(key), key, value, false, true)方法插入元素：
//put方法首先调用一个hash方法，计算出k的hash值
//将k的hash值,key,value传进来
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//这里onlyIfAbsent如果为true，表明不能修改已经存在的值，因此我们传入false
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断table是否为空，如果空的话，会先调用resize扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据当前key的hash值找到它在数组中的下标，判断当前下标位置是否已经存在元素，
//若没有，则把key、value包装成Node节点，直接添加到此位置。
//[i = (n - 1) & hash]相当于取模运算的位运算形式
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//如果当前位置已经有元素了(产生了哈希碰撞)，分为三种情况。
Node<K,V> e; K k;
//1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，
//则把p赋值给e，后续需要做值的覆盖处理
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//2.如果当前是红黑树结构，则把它加入到红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//3.此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部
else {
for (int binCount = 0; ; ++binCount) {
//如果头结点的下一个节点为空，则插入新节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果在插入的过程中，链表长度超过了8，则转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
//插入成功之后，跳出循环到next
break;
}
//若在链表中找到了相同key的话，直接退出循环，跳转到next
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// next
// 此时新值要覆盖旧值
if (e != null) {
V oldValue = e.value;
//用新值替换旧值，并返回旧值。
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果当前数组中的元素个数超过阈值，则扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
下面是get操作源码：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 判断数组是否为空，数组长度是否大于0，目标索引位置下元素是否为空，是的话直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果目标索引位置元素就是要找的元素，则直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果目标索引位置元素的下一个节点不为空
if ((e = first.next) != null) {
// 如果类型是红黑树，则从红黑树中查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 否则就是链表，遍历链表查找目标元素
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
通过put源码分析我们知道，数组的初始化和扩容都是通过调用resize方法完成的：
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;
}
// 扩大容量为当前容量的两倍，但不能超过 MAXIMUM_CAPACITY
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
// 如果初始化的值为 0，则使用默认的初始化容量，默认值为16
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的容量等于 0
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
table = newTab;
// 原数据不为空，将原数据复制到新 table 中
if (oldTab != null) {
// 根据容量循环数组，复制非空元素到新 table
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
// 链表复制，JDK 1.8 扩容优化部分
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;
}
// 原索引 + oldCap
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;
}
// 将原索引 + oldCap 放到哈希桶中
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
JDK1.8在扩容时通过高位运算 e.hash & oldCap 结果是否为0来确定元素是否需要移动，主要有如下两
种情况：
情况一：
扩容前oldCap=16，hash=5， (n-1)&hash=15&5=5 ， hash&oldCap=5&16=0 ；
扩容后newCap=32，hash=5， (n-1)&hash=31&5=5 ， hash&oldCap=5&16=0 。
这种情况下，扩容后元素索引位置不变，并且hash&oldCap==0。
情况二：
扩容前oldCap=16，hash=18， (n-1)&hash=15&18=2 ， hash&oldCap=18&16=16 ；
扩容后newCap=32，hash=18， (n-1)&hash=31&18=18 ， hash&oldCap=18&16=16 。
这种情况下，扩容后元素索引位置为18，即旧索引2加16(oldCap)，并且hash&oldCap!=0。