存储结构

1.7

JDK 1.7的HashMap采用数组+链表的方式进行存储，当不同的key经过了哈希等操作后若获得了数组中同样的下标，这些在数组中下表相同的节点就会以链表的方式存储。如下图所示。
图片说明

1.8

JDK 1.8的HashMap采用数组+链表+红黑树的方式存储。和1.7版本不同的是，当链表中的元素大于等于8时，会将链表转为红黑树进行存储，如下图所示：
图片说明

为什么链表转成红黑树的阈值时8，而不是7或者10呢？

实际上，链表转红黑树有两个阈值，当链表长度大于等于8，转红黑树；当红黑树节点小于等于6，转链表。中间留了一个7作差值可以方式链表和树之间的频繁转换。假设如果设计成超过8就转树，小于等于8就转链表，如果一个HashMap不停插入删除元素，链表个数在8处徘徊，就可能频繁发生树和链表之间的互转，效率很低。
另一方面，由于treenodes的大小越是常规节点的两倍。而容器中节点分布在hash桶中的频率遵循泊松分布，桶的长度超过8的概率相当小，所以作者选择了8作为阈值。
链表节点的插入方法

1.7
使用头插法。将最新插入的节点插入都链表的头部。会有两个问题：

在扩容的时候，由于要将旧数组的元素拷贝到新数组，由于采用的是头插***导致拷贝后的链表逆序。

同样是在扩容和拷贝的阶段，根据拷贝函数的源码：

void transfer(Entry[] newTable) {
Entry[] src = table;                   //src引用了旧的Entry数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
   Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
   if (e != null) {
       src[j] = null; 
       do {
           Entry<K,V> next = e.next;
           int i = indexFor(e.hash, newCapacity); 
           e.next = newTable[i]; // 新数组要插入的位置的已有元素拼接到要插入的元素的尾部
           newTable[i] = e;      //新插入的元素覆盖新数组（的头部）
           e = next;             //访问下一个要插入的元素
       } while (e != null);
   }
}
}

在并发执行时，假设线程A和B几乎同时往HashMap中插入一个节点并且都触发了扩容的操作。假设线程A先进入transfer()函数开始复制，当A取到了旧数组的Entry节点e后由于某些原因无法继续执行了。在此时B进入了transfer()函数并且执行完毕。之后A继续执行。因为头插法，此时新链表的头节点在经过了B的操作后，为e。而A要操作（复制）的节点，也为e。所以当执行到e.next = newTable[i]时，意味着e.next指向了自己，由此产生了死循环。

1.8

使用尾插法，不会导致逆序和死循环的问题。

为什么能用尾插法？
因为较长的链表会转成红黑树，确保即使是尾插时间复杂度也不会很高。

哈希算法与扩容

节点下标计算方式

在key经过哈希后得到的一个数，应该怎么通过这个数获得该key对应的数组下标？一般而言可以直接使该数字对数组长度取余获得（准确地说是对数组长度-1，因为下标从0开始）。但是取余运算比较麻烦。因此HashMap中是这样做的：
让初始得到的哈希值和该哈希值的高16位异或。这一步目的是，希望能够在数组容量较小的情况下，也可以利用到哈希值的高位部分，使得计算出的下标更加均匀，减少碰撞。为什么这样做可以让哈希值高位都参与进下标的计算？先看下一步。
将得到的新的哈希值和（数组容量-1）这个数做与运算，得到的就会是一个0到数组长度-1的数。这样做巧妙之处在于，不用进行取余运算，但是这样做的前提是数组长度必须是2的倍数，因此这就解释了为什么HashMap扩容总是乘以2
图片说明
备注：h >>> 16的意思是取h的高16位，即将h的高16位右移到低16位，其余补0

HashMap关于容量的几个属性：

int threshold; //在length和负载因子对应下允许的最大元素数目
final float loadFactor; //负载因子
int modCount; //内部结构发生变化的次数
int size; //HashMap实际元素个数

threshold = length * loadFactor
负载因子是0-1的一个数，这意味着，当HashMap里存储的元素个数小于threshold（即容量*负载因子），则扩容。负载因子默认0.75，这个数是在时间和空间效率上的平衡选择。如果内存很多，要求时间效率很高，可以降低负载因子（让HashMap变得更稀疏，更难发生碰撞），如果内存不多，对时间效率要求不高，则可增加负载因子。

扩容后的下标计算方式

1.7

直接用hash值和需要扩容的二进制数进行与运算

1.8

利用了1.7时候的计算规律，只需要判断hash值中新增的参与运算的位是0还是1就可以确定扩容后的下标。如果新增的参与运算的位是0，扩容后的位置=原始位置；如果是1，扩容后的位置=原始位置+扩容前的旧容量，如下图所示：
图片说明

HashMap的线程不安全

HashMap无同步锁的保护，而在JDK1.7中更是可能在多线程触发扩容时出现死循环链表的现象。
多线程下建议使用线程安全的ConcurrentHashMap

HashMap键值NULL问题

允许键为NULL，且只允许有一个NULL值，此时的hash值默认设置为0。
允许值为NULL，且可以多个为NULL

HashMap存储位置不保证有序

因为插入顺序和存储顺序不同，插入顺序是用户插入的顺序，存储顺序根据hash算法计算得出。hash算法讲究随机、均匀，不具备先后规律。

HashMap存储位置随时间变化

因为存在扩容操作。当存储元素个数大于扩容阈值，则会扩容HashMap，导致元素存储位置被重新计算。

怎样的对象适合做HashMap的key

需要重写hashCode()方法和equals()方法

hashCode()方法：计算本对象的哈希值，决定了以本对象为key的键值对的存储位置，若性能不好的hash算***导致严重碰撞。
equals()方法：用于比较存储位置上是否已经存在要给定的key对象。一定要实现这个方法是因为根据key进行的get和put操作都必须准确判断是否Map里存在一样的key了，换言之要保证Map中key的唯一性。
String、Integer等包装类适合做key
他们是final类型，具备key的不可变性，不会出现放入和获取时hash值不同的情况
它们内部重写了equals、hashCode()方法，严格遵守相关规范，不会出现相同值Hash计算不同的情况。

HashMap如何解决冲突

Hash算法

hashCode()的高性能
扰动处理：1.7 4次位运算+5次异或；1.8 1次位运算+1次异或
前提：需要数组长度是2的n次幂

扩容机制

当HashMap内的元素个数>存储阈值（容量*装载因子）时扩容。保持HashMap的稀疏以防止碰撞。

数据结构

1.7 采用数组+链表
1.8 采用数组+链表+红黑树，应对发生冲突的状况。发生冲突时1.7采用头插法将元素插入链表中，1.8才用红黑树+尾插法插入元素。

HashMap原理与在JDK1.7/1.8中的不同