HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
HashMap是非线程安全的，实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。
HashMap 是无序的，即不会记录插入的顺序。
之前jdk1.7的存储结构是数组+链表，到了jdk1.8变成了数组+链表+红黑树。
HashMap 继承于AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。
底层数据结构：
jdk1.7存储结构图：
jdk1.7中，首先是把元素放在一个个数组里面，后来存放的数据越来越多，后来出现了链表，对于数组中的每一个元素，都可以有一条链表来存储元素。这就是有名的“拉链式”存储方法。
jdk8存储结构图：
jdk1.8我们会发现优化的部分就是把链表结构变成了红黑树。原来jdk1.7的优点是增删效率高，于是在jdk1.8的时候，不仅仅增删效率高，而且查找效率也提升了。当然不是说变成了红黑树效率就一定提高了，只有在链表的长度不小于8，而且数组的长度不小于64的时候才会将链表转化为红黑树。
// 序列化id
private static final long serialVersionUID = 362498820763181265L;
// HashMap容器初始值 1 << 4 = 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// HashMap容量极限 1 << 30 = 1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;
// 负载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当节点数大于8时 数组长度大于64时 会转为红黑树存储
static final int TREEIFY_THRESHOLD = 8;
// 当节点数小于6时会转为单向链表存储
static final int UNTREEIFY_THRESHOLD = 6;
// 当节点数大于8时 数组长度大于64时 红黑树树化
static final int MIN_TREEIFY_CAPACITY = 64;
// Node是Map.Entry接口的实现类
// 在此存储数据的Node数组容量是2次幂
// 每一个Node本质都是一个单向链表
transient Node<K,V>[] table;
// HashMap大小,它代表HashMap保存的键值对的多少
transient int size;
//HashMap被改变的次数
transient int modCount;
// 下一次HashMap扩容的阈值
int threshold;
// 存储负载因子的常量
final float loadFactor;
/*
initialCapacity 初始容量
loadFactor 负载因子 表示一个散列表的空间的使用程度
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) // 初始容量<0 抛异常
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) // 初始容量 > 最大容量
initialCapacity = MAXIMUM_CAPACITY; 初始容量 等于 最大容量
if (loadFactor <= 0 || Float.isNaN(loadFactor)) // 负载因子 小于等于0 或者 不是个数 抛异常
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor; // 将负载因子赋给该对象
this.threshold = tableSizeFor(initialCapacity); // 下次达到这个值 就扩容
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR); // 负载因子是0.75
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 默认初始容量大小是 16
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 负载因子是0.75
putMapEntries(m, false); //此构造方法主要实现了Map.putAll()
} // k-v值存
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/*
hash 计算key的hashcode值
key key值
value value值
onlyIfAbsent 如果hash冲突时，新值是否替换旧值 如果为真 不能改变已存在的值
evict 如果为假 这个表格在创建状态
*/
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不为空并且table长度不可为0,否则将从resize函数中获取
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通过取模运算（前文详细写道），来获得寻址结果
/ /也就是传入的key-value键值对在数组中的存储位置
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果为null，说明此处还没有存储元素，将key-value包装成Node设置在i处
tab[i] = newNode(hash, key, value, null);
else { // else说明寻址结果i已经存储的有元素了，哈希冲突了
Node<K,V> e; K k; // 两个临时变量，node和key
// 要插入的key和原位置的key一样 这里将p赋给e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 此时说明p已经树化，调用红黑树的方法添加到指定位置
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // //走到这里说明，hash寻址冲突了，并且和寻址结果i处的key不同，
// 也不是树，说明此时要在链表上操作了 找到链表的尾节点，插入新节点
for (int binCount = 0; ; ++binCount) { // 向node单向链表中添加数据
if ((e = p.next) == null) { // 找到链表最后一个
p.next = newNode(hash, key, value, null); // 赋值
if (binCount >= TREEIFY_THRESHOLD - 1) // 节点数大于8
treeifyBin(tab, hash); // 转换为红黑树
break;
}
//此时在链表找尾节点时，发现了和新插入节点完全一致的key，
// 所以记录，跳出，后文替换
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // p记录下一个节点
}
}
if (e != null) { //替换操作，如果e!=null，说明e记录了冲突的节点
//记录老值，用于返回
V oldValue = e.value;
// 开头传入的参数flase，说明冲突时会进行替换操作
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 具体实现在LinkedHashMap，此处不在详解
afterNodeAccess(e);
return oldValue;
}
}
++modCount; // 具体实现在LinkedHashMap，此处不在详解
if (++size > threshold) // 判断是否需要扩容
resize();
// 在插入后对 head 进行处理，
// 如果满足条件（即 evict 为 true，存在至少一个元素，且允许删除第一个元素）
// 则删除 head 所在的节点
afterNodeInsertion(evict);
return null;
}
JDK1.8之前，插入数据时，在链表中用头插法，但在多线程中可能会产生死链，所以在JDK1.8中在链表中使用尾插法来规避这个问题。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
键值对在哈希表中的位置（数组index） i = (n - 1) & hash
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // table赋予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; // 下次扩容大小 Integer.MAX_VALUE
return oldTab; // 返回老数组
}
// 若新表大小(oldCap*2)小于数组最大值 并且老值大于等于数组初始化大小
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 2 * oldThr 当作新表阈值
}
else if (oldThr > 0) // 如果老表下次扩容大小大于0
newCap = oldThr; // 新表长度 = 旧表阈值
else { // 零初始阈值表示使用默认值
newCap = DEFAULT_INITIAL_CAPACITY; // 信标长度 = 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 新表阈值等于 默认 0.75 * 16
}
if (newThr == 0) { // 如果新表阈值 = 0
float ft = (float)newCap * loadFactor; // 新表长度 * 0.75 默认
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; // 将当前表赋给table
if (oldTab != null) { // 如果oldTab中有值 循环遍历出
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) { // 获取老表第j个元素 赋给e
oldTab[j] = null; // 并将老表中的元素数据置Null
if (e.next == null) // 如果e后面没有节点了
newTab[e.hash & (newCap - 1)] = e; // 直接将e赋给新表
else if (e instanceof TreeNode) // 若e是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循环 获取新旧索引的节点
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;
}门限值等于（负载因子）x（容量），如果构建 HashMap 的时候没有指定它们，那么就是依据相应的默认常量值。
门限通常是以倍数进行调整 （newThr = oldThr << 1），我前面提到，根据 putVal 中的逻辑，当元素个数超过门限大小时，则调整 Map 大小。
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
// evict 表是否在创建模式，如果为false，则表是在创建模式。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size(); // 算出传进来表的大小
if (s > 0) {
if (table == null) { // 表等于null 说明是拷贝构造函数来调用的putMapEntries或者构造后还没放过任何元素
// 先不考虑容量必须为2的幂，那么下面括号里会算出来一个容量，使得size刚好不大于阈值。
// 但这样会算出小数来，但作为容量就必须向上取整，所以这里要加1
float ft = ((float)s / loadFactor) + 1.0F;
// 如果小于最大容量，就进行截断；否则就赋值为最大容量
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 虽然上面一顿操作猛如虎，但只有在算出来的容量t > 当前暂存的容量(容量可能会暂放到阈值上的)时，才会用t计算出新容量，再暂时放到阈值上
if (t > threshold)
threshold = tableSizeFor(t);
}
// 说明table已经初始化过了；判断传入map的size是否大于当前map的threshold，如果是，必须要resize
// 这种情况属于预先扩大容量，再put元素
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { // 赋值
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
} public Object clone() {
HashMap<K,V> result; // 构建一个HashMap
try {
result = (HashMap<K,V>)super.clone(); // 父类的复制 此时result里的值都是本hashmap的值，引用地址也一样
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
result.reinitialize(); // 将result 恢复至初始状态
result.putMapEntries(this, false); // 将本hashMap的值传入result中
return result; // 返回值 属于浅拷贝
}
protected Object clone() throws CloneNotSupportedException {
AbstractMap<?,?> result = (AbstractMap<?,?>)super.clone();
result.keySet = null; // 清空keySet 这两个值是作为视图来使用的
result.values = null; // 清空values
return result;
}