底层实现：数组+链表(链表长度大于8转换为红黑树)
HashMap 是存储键值对的集合，每个键值对存储在一个Node<K,V>。HashMap的主干是一个名为table的Node数组
每个键值对key的hash值对应数组下标，遇到hash冲突时，采用链地址法
JDK1.7:通过键值对Entry<K,V>中的next属性来把hash冲突的所有Entry连接起来，因此每次都要遍历链表才能得到所要找的键值对，增删改查操作的时间复杂度为O（n）
JDK1.8: 当链表长度大于8时，会将链表转化为一棵红黑树，增删改查操作的时间复杂度为O（log（n））。
源码
键值对
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//hash值
final K key;//键值
V value;
Node<K,V> next;
……
}
key和hash属性为final的原因：在Java中，如果一个对象的属性值在业务逻辑上不需要改变，就将其声明为final，这样保证了安全性。
而且在这里若是让key或者hash发生改变，会导致该键值对无法被查找到
属性
默认初始化容量为 16，扩容容量必须是 2 的幂次方、最大容量为 1<< 30 、默认加载因子为 0.75。
transient int size;//实际键值对个数 int threshold;//阈值，超过到这个值后就要进行扩容 transient int modCount;//修改计数器，用于快速失败 final float loadFactor;//加载因子
threshold = table.length （默认值为16）* loadFactor（默认值为0.75） 这两个值可以在构造时自行输入。length值需要自己根据业务需求输入，输入合适的值能显著减少扩容次数 。
而loadFactor值在一般情况下0.75都是有不错的效率的。但是若是对时间效率要求很高，对空间效率要求很低，可以减小loadFactor值，反之增大loadFactor值，可以大于1。
modCount用于记录对象的改变结构的次数（不包含修改value的值的操作），这是用于在多线程情况下，当多个线程并发修改HashMap的结构时，多个线程都会去修改modCount这个成员变量，
而每个线程内部维护着一个局部变量的修改技术器，当线程做完修改操作后发现成员变量的modCount与局部变量不一致时，就抛出ConcurrentModificationException，这是fail-fast机制，
Java中如ArrayList等线程不安全的集合都有这个机制。
求key的hash值
（1）计算对象自己的hashCode()值
（2）计算上步得到的值高16位于低16位相与。否则在容器length较小时，无法发挥高位的作用，这样能使 得hash分布更加均匀，减少冲突。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//第一步与第二步
}
（3）定位操作，对上步计算得到hash值进行取模操作（这里用的是位运算，有个小技巧）
index = (n - 1) & hash//在这里等价于hash%n
HashMap规定length一定是2^N，N可为任意整数，如果自定义的length长度不为2的整数次幂，那么就会自动取成大于设定值的最接近的2^N的值。
在这个前提下，我们再来看这个二进制与运算。如在n=16的情况下，15的二进制码为 1111，不管是什么数，和11111做&操作，低五位不会变，而高位全部为0，即与hash%n的结果是一样的。
而且在计算机中，位运算的效率是最高的，因此这样会大大提升查询效率。
扩容
if (++size > threshold)//当完成put操作后，发现新的size大于了阈值
resize();
newThr = oldThr << 1; // double threshold
每次扩容为之前的两倍：在扩容之后就要把具体键值对搬迁到新的table数组中。
put
/**
* 添加键值对到HashMap中
*
* @param hash key所对应的哈希值
* @param key 键值对中的键（key）
* @param value 键值对中的值（value）
* @param onlyIfAbsent 如果存在相同的值，是否替换已有的值，true表示替换，false表示不替换
* @param evict 表是否在创建模式，如果为false，则表是在创建模式
* @return 返回旧值或者null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
HashMap.Node<K, V>[] tab;// 临时变量，用来临时存放链表数组
HashMap.Node<K, V> p;
int n, i;
// 检查链表数组table是否为空，table为null或者table数组的长度为0都表示为空
if ((tab = table) == null || (n = tab.length) == 0)
// 如果为空则初始化，并扩容，然后返回新链表数组的长度，将长度赋值给变量n
// resize()方法就是初始化并扩容，该方法具体请参考：
n = (tab = resize()).length;
// (n-1)&hash这条语句就是JDK1.7中HashMap源码中的indexFor()方法的功能，即得到该对象存放在数组中的具体位置（下标）
// 判断该位置的元素是否为null，即是否存在元素，如果存在则表示已经发生哈希冲突，如果不存在，则添加元素结点
if ((p = tab[i = (n - 1) & hash]) == null)
// 表示不存在元素的情况
// 则新添加一个元素到链表数组的对应下标位置，该结点也是链表的链头
tab[i] = newNode(hash, key, value, null);
else {
// 表示存在元素的情况
// 则发生了哈希冲突，下面的代码则是尝试解决冲突问题
HashMap.Node<K, V> e;
K k;
// 判断待添加元素的hash值和key值是否同已经存在（冲突）的元素的hash值和key值同时相等
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 如果相等，则表示两个元素相互重复了，那么使用变量e来临时存储这个重复元素
e = p;
// 如果不相等，表示没有重复，并且判断结点类型是否是红黑树类型
else if (p instanceof HashMap.TreeNode)
// 那么就将该键值对存储到红黑树中
e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
// 如果不相等，且结点类型不是红黑树类型，那么就是链表，即采用拉链法解决冲突
else {
// 遍历链表中所有结点，这是一个死循环，需要通过break跳出循环
for (int binCount = 0; ; ++binCount) {
// 如果p的下一个结点为null，则p是链表中的最后一个结点
if ((e = p.next) == null) {
// 则将键值对添加到最后一个结点的后面
p.next = newNode(hash, key, value, null);
// 同时binCount也是一个计数器，统计该链表已经有几个元素了
// TREEIFY_THRESHOLD是常量，表示阈值，默认值为8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 但链表中元素个数超过了阈值，则将链表转换成红黑树
treeifyBin(tab, hash);
// 跳出循环
break;
}
// 判断待添加元素的hash值和key值是否同链表中已有元素的hash值和key值同时相等
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
// 如果相等，则表示已经存在相同的键，跳出循环
break;
// 将下一个节点赋值给当前节点，继续往下遍历链表
p = e;
}
}
// 如果e不为空，则表示已经存在重复的值，即存在hash值和key值同时相等的元素
if (e != null) {
// 保存旧值
V oldValue = e.value;
// 然后替换为新值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 此函数会将链表中最近使用的Node节点放到链表末端，因为未使用的节点下次使用的概率较低
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 记录修改次数
++modCount;
// 如果添加元素后，超过阈值
if (++size > threshold)
// 则对HashMap进行扩容
resize();
// 给LinkedHashMap使用
afterNodeInsertion(evict);
return null;
}