Java容器详解二（HashMap）

1. 底层存储
在jdk1.8中，HashMap的哈希桶有两种存储结构，一种是单向链表，一种是红黑树，当哈希桶里面的节点个数大于8个的时候转为红黑树，以提高查询效率。哈希表的是一个数组，如下。

transient Node<K,V>[] table;

其初始化的大小为16，以后每次扩容增加一倍，哈希表的数组大小一定是2的幂次倍，因为一个哈希值散列的时候可以用hash&(length-1)，如果length数组长度为2的幂次倍，则该表达式计算的值就可以把hash值转换为0到length-1范围内的数作为数组索引，因此可以快速计算出一个hash值所对应的数组索引。
其完整的结构图如下

图1 哈希表底层存储结构原理图
Node就是HashMap的一个内部类，存储的数据实体，一个键值对，上图中的一个黑点就是一个Node对象。
当一个HashMap内的Node数量超过临界值时会触发扩容，table的容量变为原来的2倍，临界值是threshold = length * Load factor决定的，即数组长度和负载因子，负载因子默认0.75，数组长度默认16，负载因子一般不需要调整，除非特殊情况，比如，空间非常宽松而对时间要求较高可以调低负载因子，让散列更分散。
当扩容发生时，JDK1.8版本做了优化，扩容后的容量变为原来的2倍，原来的节点的哈希值要么不变，要么比原来大oldCap，原理如图所示
图2 变化原理图
HashMap不是线程安全的，在多线程中应该尽量避免使用，最好使用线程安全的ConcurrentHashMap类，因为HashMap可能在扩容的时候多线程下产生循环链表
2. 添加元素

1. 首先用过对象的hashCode方法返回哈希值。
2. 然后调用hash函数对哈希值进行处理，主要是进行高位运算，是为了减少冲突，尽量防止不同的对象产生相同的哈希值。
3. 根据哈希值来映射到数组相应索引位置，这里数组的长度一般都是2的幂次方，这样就可以通过一次与运算运算出来数组索引位置，在本文第一部分底层存储结构已经分析过了。
4. 存储对象，存储对象分为两种情况，这取决于底层存储结构，分为链表结构和红黑树结构。
5. 判断容器中存放的对象数量是否超过了容器的临界值，如果超过则进行扩容操作。

3. 扩容操作
当判断容器中的对象数量超过临界值的时候就会触发扩容操作，根据第一小节的内容可以知道，HashMap底层的存储结构是采用数组的结构。扩容的时候步骤如下

1. 首先按照条件来计算扩容后的大小，一般每次扩大为原来2倍，然后更新临界值，
   2.根据计算出来的容量大小new一个新的数组
   3.重新计算原来所有节点的哈希值，然后插入到相应的数组索引下。jdk1.8版本在这里做了一个优化，原来是把所有的节点重新计算哈希值，这里是根据了一个特性，因为数组长度增长的固定的倍数，2倍，所以所有的节点索引要么不变，要么是该索引加上原来的数组长度，其原理如2所示，其取决于该对象的哈希值的一个二进制位，这个二进制位在那个数组长度变为原来2倍的那个由0变为1的二进制位。就是图中如下几位。

   
   image.png