HashMap 基于哈希表的 Map 接口实现，主要用来存放键值对数据。HashMap 不是同步的，这意味着它不是线程安全的。如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有线程安全的能力，或者使用ConcurrentHashMap。HashMap 最多允许一条数据的键为 null，允许多条数据的值为 null。此外，HashMap 中的映射不是有序的。
JDK1.8 之前 HashMap 由数组 + 链表组成，数组是 HashMap 的主体，链表则是主要使用链地址法解决哈希冲突，即当两个对象调用的 hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用了。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8 ）并且当前数组的长度大于 64 时，此时此索引位置上的所有数据改为使用红黑树存储。
HashMap 继承自 AbstractMap 抽象类，并实现了 Map、Cloneable、Serializable，可以用来存储键值对类型的数据，同时支持复制和序列化。
父类 AbstractMap
AbstractMap 提供了一套基于键值对访问的接口。通过继承此类，子类仅需实现部分代码即可拥有完整的一套访问键值对数据的接口。
**AbstractMap 只有一个抽象方法 entrySet()，其他大多方法都是调用 entrySet() 去处理数据。**所以子类继承可以把关注点放在 entrySet() 方法上，这个方法返回一个保存所有 key-value 映射的 Set。
public abstract Set<Entry<K,V>> entrySet();
如果想要实现一个可变的 Map，我们还需要重写 put() 方法，因为 AbstractMap 类中默认不支持 put 实现，子类必须重写该方法的实现，否则会抛出异常：
public V put(K key, V value) { throw new UnsupportedOperationException(); }
成员变量
初始化容量：16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- 当我们根据 key 的 hash 确定其在数组的位置时，如果 n 为 2 的幂次方，可以保证数据的均匀插入，如果 n 不是 2 的幂次方，可能数组的一些位置永远不会插入数据，浪费数组的空间，加大 hash 冲突，降低 HashMap 的性能
- 一般我们可能会想通过 % 求余来确定位置，只不过性能不如 & 运算。所以 HashMap 使用后者来确定位置，而且当 n 是 2 的幂次方时：
hash & (length - 1) == hash % length - HashMap 容量为 2 次幂的原因为了数据的的均匀分布，减少冲突，毕竟 hash 冲突越大，代表数组中一个链的长度越大，这样的话会降低性能
- 如果创建 HashMap 对象时，输入的数组长度是 10（不是 2 的幂），HashMap 通过一系列位移运算和或运算得到离初始容量最近的 2 的幂次数
最大容量：2 的 30 次幂
static final int MAXIMUM_CAPACITY = 1 << 30;
HashMap 集合最大容量的上限是：2 的 30 次幂。
默认的负载因子： 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
链表和树相互转换阈值
static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6;
JDK1.8 新增特性，当桶中的链表的元素个数超过 8 则会转红黑树。当桶上的结点数小于 6 时红黑树又会转换成链表。
首先我们要知道，无论是链表的结构还是红黑树的结构，都是设计者在寻找一种时间和空间的平衡。链表的查找效率为 O(n)，而红黑树的查找效率为 O(logn)，查找效率是变高了，但是插入效率变低了，如果从一开始就用红黑树并不合适。从概率学的角度选了一个合适的临界值为 8。
当元素数量为 8 的时候，红黑树的平均查找长度是 3。而链表的平均查找长度是 4，显然树要快一些，而当元素数量小于等于 6 的时候，链表的平均查找长度是 3，其实也很快，没有必要使用红黑树结构，因为转换的过程也需要一定的时间。
6 和 8 中间有个差值 7 还可以防止链表和树之间频繁的转换。
最小树形化阈值：64
static final int MIN_TREEIFY_CAPACITY = 64;
当 HashMap 桶的容量超过这个值时才能进行树形化 ，否则会先选择扩容，而不是树形化。为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD。
存储元素的数组
transient Node<K,V>[] table;
在 JDK1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构，其中 table 就是 HashMap 中的数组，JDK1.8 之前数组类型是 Entry 类型。从 JDK1.8 之后是 Node 类型。只是换了个名字，都实现了一样的接口：Map.Entry。负责存储键值对数据的。
存放元素的个数
transient int size;
存放元素（键值对）的个数，注意这个不等于数组的长度。
统计修改次数
transient int modCount;
每次扩容和更改 map 结构的计数器。
扩容临界值用来调整大小
int threshold;
计算公式：capacity（数组长度默认16）* loadFactor（负载因子默认 0.75）。这个值是当前已占用数组长度的最大值。当 size >= threshold 的时候，就要考虑对数组进行扩容操作，临界值是衡量数组是否需要扩增的一个标准，扩容后的 HashMap 容量是之前容量的两倍。
哈希表的加载因子：0.75
final float loadFactor;
用来衡量 HashMap 满的程度，表示 HashMap 的疏密程度。loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。计算 HashMap 的实时加载因子：size / capacity。
当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时，表示 HashMap 太挤了，需要扩容，而扩容这个过程涉及到 rehash、复制数据等操作，非常消耗性能。所以开发中尽量减少扩容的次数，可以通过创建 HashMap 集合对象时指定初始容量来尽量避免。
同时在 HashMap 的构造器中可以定制 loadFactor。
/** * 构造一个带指定初始容量和加载因子的空 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); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
为什么加载因子设置为 0.75，初始化临界值是 12？
loadFactor 越趋近于 1，那么数组中存放的数据也就越多，也就越密，会让链表的长度增加，降低查询效率，loadFactor 越趋近于 0，数组中存放的数据也就越少，也就越稀疏。既要兼顾数组利用率还要考虑链表元素不要太多，经过大量测试 0.75 是最佳方案。
threshold 表示扩容临界值，计算公式：capacity（数组长度默认16）* loadFactor（负载因子默认 0.75）。当 size >= threshold 的时候，就要考虑对数组进行扩容操作。所以最开始的初始化临界值是 12，临界值是衡量数组是否需要扩增的一个标准，扩容后的 HashMap 容量是之前容量的两倍。那么接下来的临界值就是 24、48、96 …
构造方法
HashMap 的构造方法主要是用于设置初始化容量和加载因子，也可以传入 Map 对数据初始化。
无参构造
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
使用无参构造的时候，加载因子 DEFAULT_LOAD_FACTOR 默认值为 0.75f，初始化容量 DEFAULT_INITIAL_CAPACITY 为 16。
指定初始化容量和加载因子
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; this.threshold = tableSizeFor(initialCapacity); }
默认情况下 HashMap 的容量是 16，但是，如果用户通过构造函数指定了一个数字作为容量，那么会选择大于该数字的第一个 2 的幂作为容量（3->4、7->8、9->16），即 tableSizeFor 方法的作用。
指定初始化容量
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
本质上使用的还是上门的构造方法，只不过是指定初始化容量，使用默认的加载因子。
传入 Map 数据进行初始化
public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
使用默认的加载因子，之后调用 putMapEntries 处理元素，循环原始 Map，不断调用 putVal 方法添加数据。
成员方法
新增元素 put
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
HashMap 暴露 put 方法用于添加数据，而 put 方法种实际上调用 putVal 实现添加逻辑。
首先 putVal 方法接收的第一个参数为 key 的哈希值，计算逻辑如下：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
- 如果 key 等于 null，那么返回的哈希值为 0
- 如果 key 不等于 null，首先调用 key 的 hashCode 方法赋值给 h，然后和 h 无符号右移 16 位后的二进制进行按位异或得到最后的 hash 值
所以从 hash 方法中可以看出，HashMap 允许其中一条数据的键为空。按位异或运算（^）：相同的二进制数位上，数字相同，结果为 0，不同为 1。
键值之道：深入学习Java中强大的HashMap（二）https://developer.aliyun.com/article/1480892
