HashMap 简介
HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。
HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个
JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。并且， HashMap 总是使用 2 的幂作为哈希表的大小。
数据结构
JDK 8版本的HashMap底层数据结构是数组+链表/红黑树结构，具体原因是：
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node[] table;
这是 HashMap 类中的一个成员变量，它是一个存储桶数组。table 数组用于存储键值对的实际数据。
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
这是 HashMap 内部定义的静态嵌套类 Node，它实现了 Map.Entry 接口。每个 Node 对象表示 HashMap 中的一个键值对，它包含键、值以及指向下一个节点的引用。
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode root() {
for (TreeNode r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}
这是 HashMap 内部定义的静态嵌套类 TreeNode，它是红黑树结构的节点。在 HashMap 中，当链表中的元素数量超过一定阈值时，会将链表转换为红黑树，以提高查找性能。
因此，transient Node[] table; 存储了实际的数据，static class Node 表示链表结构的节点，而 static final class TreeNode 表示红黑树结构的节点。这些组合在一起实现了 HashMap 数据结构的数组+链表（红黑树）的形式。
Hash
如果说HashMap的数据结构是其实现功能的基础，那么HashMap的Hash方法则是HashMap实现查找、插入的保障。
HashMap 并不是直接获取 key 的 hashCode 作为 hash 值的，它会通过一个扰动函数（所谓扰动函数指的是HashMap的hash方法）进行一些列位运算和混合操作，使得最终的哈希值更加均匀的分布在哈希表的桶中。使用hash方法就是为了减少hash碰撞的概率且提高HashMap的性能。
//扰动函数
static final int hash(Object key) {
//用于存储key对应的hash码
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//等同于:
int h;
//当key是null时，hash值默认是0，即HashMap只能有一个为Null的key
if (key == null) {
h = 0;
} else {
h = key.hashCode();
}
//进行异或操作并将结果赋值给 h
return h = h ^ (h >>> 16);
构造方法
HashMap的类属性和构造方法：
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1
