简介以及分析

总所周知，每当我们面试的时候，首先要考我们的主要是有集合属性，在集合属性中我们重点要考的就是map集合，对于Map我们使用的最大的也就是HashMap，提到了HashMap集合的属性，Hashmap在Jdk1.7到Jdk1.8进行升级的时候其底层的数据结构引入了红黑树和扩容的优化等，接下来的文章主要是结合Jdk1.7和Jdk1.8，深入对HashMap的数据结构和底层原理进行相关的功能的探讨。

HashMap的特点说明
HashMap是根据键的hashCode值存储数据，大多数的时候都是直接根据其的值直接定位到它的值，因此其相关的值是比较快速的，但是其遍历的过程却是没有规律的，HashMap只允许有一条记录的key为null，允许多条记录的value的值为空，HashMap是非线性安全的，即同一时刻是可以多个线程同时写HashMap,可能是导致数据的不一致，如果是有需要可以使用Collections的syschronized方法是HashMap具有线程的安全的能力，或者是使用CurrentHashMap来进行保证。

底层原理

对于我们经常使用的这样的一种数据类型，我们有必要进行相关的功能的研究和判断来彻底来搞懂我们的这个hashMap的底层原理，这个过程能够让我们能够在以后开发的过程中对这种数据结构的使用更加得心应手。

数据结构
对于hashMap而言，Jdk1.7之前的话主要是数组+链表来进行相关的实现的，Jdk1.8的时候开始了以数组+链表+红黑树进行实现的，这个过程中进行相关的功能的研究和实现，下面来让我们进行相关的具体的功能的分析，我们为什么会这样做呢？

那么我们首先要弄明白的是数据底层我们到底是存储的是什么数据结构，这样的存储有什么优点呢？

• 从源码上我们可以知道，HashMap有一个重要的字段，就是Node[] table,明显它是一个Node的数组，接下来我们来看下Node[JDK1.8]是什么，通过对源码进行分析，Node是HashMap的一个实现类，实现了Map.Entry接口，本质上还是一个key-value键值对，上图中的蓝色和黑色圆圈本质上都是一个Node对象。
  

• HashMap是使用哈希表来进行存储的，哈希表为了解决冲突，HashMap主要是采用了键地址法来解决问题，简单来说就是数组和链表的组合，在每个数组的后面都有一个链表，当数据通过hash算法得到一个值后，其对应的数据会放到一个对应的hash链表上进行存储，比如我们经常写的一种写法是map.put(“玉麒麟欧巴”,“Java开发程序员”);
  当我们进行相关的功能的开发的时候，我们通过对相关的key进行相关的Hashcode编码可以得到其相关的位置，相关的hash值后，我们就会进行相关的hash碰撞，当我们计算的值越分散，Hash的碰撞的几率就会少很多，map的取值率就会少很多。当然我们也并不是容器越大，其相关的碰撞率就一定会下降，此时我们要考虑的是有一个好的hash算法和一个扩容机制。

• 在理解hash和扩容之前，我们首先要了解HashMap的几个字段，在只有hashMap对于的源码之前我们首先要了解几个字段，此时我们可以进行相关的功能的判断
  
  Node[] table的默认值是length = 16，load factor为负载因子，默认值是0.75,threshold是所能容纳的最大的数据量的个数，显然是threshold = length * load factor,也就是在数组长度确定后，负载因子越大，其所能容纳的键值个数就越多。
  此时这里存在一个问题，即使负载因子和Hash算法设置的再合适，也难免避免不了拉链过长的情况，一旦拉链过长就会影响HashMap的性能，于是在Jdk1.8的时候引入了红黑树的数据结构，一旦链表的长度超过8，链表就会快速转换为红黑树，此时利用红黑树的快速的增删查改的速度，就能快速的提高其HashMap的运行的效率。

功能方法

HashMap的底层方法有很多，本文主要从怎么从key获取Hash桶的位置，put方法的详细执行，扩容三个有代表性的点进行详细的展开详解。

确定Hash桶数组索引位置
在我们在使用这个hashMap的时候，我们首先要做的就是确定hash数组的位置，正如我们所说，hash桶的结构是由数组+链表+红黑树组成的，我们进行hash算法的时候，我们当然希望其对于的hash值越分散越好，这样我们就能够通过hash算法快速定位到我们想要的值，而不用遍历链表，这样就能加快我们的开发的效率，那么我们先从源码中探索其结构，其过程就是三步：取key的hashCode值，高位运算，取模运算。

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

下面举例说明下，n为table的长度。

hashMap的put方法

put方法的流程相对较复杂，下面这是我写的关于其实现的数据的过程，具体的流程如图所示，下面可以进行相关的分析。

1. 判断table[i] == null是空或者是null，否则就是resize()方法进行扩容。
2. 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向6，如果table[i]不为空，转向3；
3. 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals；
4. 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5；
5. 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
6. 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//tab：引用当前hashMap的散列表//p：表示当前散列表的元素//n：表示散列表数组的长度//i：表示路由寻址 结果Node<K,V>[] tab; Node<K,V> p; int n, i;//延迟初始化逻辑，第一次调用putVal时会初始化hashMap对象中的最耗费内存的散列表if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//最简单的一种情况：寻址找到的桶位 刚好是 null，这个时候，直接将当前k-v=>node 扔进去就可以了if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {//e：不为null的话，找到了一个与当前要插入的key-value一致的key的元素//k：表示临时的一个keyNode<K,V> e; K k;//表示桶位中的该元素，与你当前插入的元素的key完全一致，表示后续需要进行替换操作if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)//红黑树，下期讲。进QQ群:865-373-238e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//链表的情况，而且链表的头元素与我们要插入的key不一致。for (int binCount = 0; ; ++binCount) {//条件成立的话，说明迭代到最后一个元素了，也没找到一个与你要插入的key一致的node//说明需要加入到当前链表的末尾if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//条件成立的话，说明当前链表的长度，达到树化标准了，需要进行树化if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//树化操作treeifyBin(tab, hash);break;}//条件成立的话，说明找到了相同key的node元素，需要进行替换操作if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//e不等于null，条件成立说明，找到了一个与你插入元素key完全一致的数据，需要进行替换if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}//modCount：表示散列表结构被修改的次数，替换Node元素的value不计数++modCount;//插入新元素，size自增，如果自增后的值大于扩容阈值，则触发扩容。if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

扩容机制
扩容机制就是不断地进行对容器进行扩大，在一般的Java中的数组中的容器显然是不会随着不断地增加而变大，显然是无法完成相关的扩容的要求的，显然此时就是我们该来的相关的容器的扩容的过程，下面让我们来对Jdk1.7和Jdk1.8的数据结构不同，因为Jdk1.8引入了红黑树的概念，此时我们先用Jdk1.7的代码来分析

newTable[i]的引用赋值给了e.next上去，这主要是采用了链表的头插法，同一位置的新元素总会放到链表的头部位置，这样先放到索引上的一个元素放到Entry的尾部(如果发生了hash冲突的情况下)，某个元素经过hash算法后，可能会放到新链表的不同的位置。
在Jdk1.8的时候，我们使用的是扩展到原来的2次幂，所以元素的位置要不是原来的位置，要不然就是在原来的位置上移动2次幂的位置，看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。
元素在重新计算hash之后，因为n变成了原来的2倍，那么n-1的mask范围上在高位上多了1bit，因此新的index上会发生新的变化

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置，下面是关于Jdk1.8的源码

    final Node<K,V>[] resize() {//oldTab：引用扩容前的哈希表Node<K,V>[] oldTab = table;//oldCap：表示扩容之前table数组的长度int oldCap = (oldTab == null) ? 0 : oldTab.length;//oldThr：表示扩容之前的扩容阈值，触发本次扩容的阈值int oldThr = threshold;//newCap：扩容之后table数组的大小//newThr：扩容之后，下次再次触发扩容的条件int newCap, newThr = 0;//条件如果成立说明 hashMap中的散列表已经初始化过了，这是一次正常扩容if (oldCap > 0) {//扩容之前的table数组大小已经达到 最大阈值后，则不扩容，且设置扩容条件为 int 最大值。if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//oldCap左移一位实现数值翻倍，并且赋值给newCap， newCap 小于数组最大值限制 且 扩容之前的阈值 >= 16//这种情况下，则 下一次扩容的阈值 等于当前阈值翻倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//oldCap == 0,说明hashMap中的散列表是null//1.new HashMap(initCap, loadFactor);//2.new HashMap(initCap);//3.new HashMap(map); 并且这个map有数据else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//oldCap == 0，oldThr == 0//new HashMap();else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;//16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12}//newThr为零时，通过newCap和loadFactor计算出一个newThrif (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;//创建出一个更长 更大的数组@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;//说明，hashMap本次扩容之前，table不为nullif (oldTab != null) {for (int j = 0; j < oldCap; ++j) {//当前node节点Node<K,V> e;//说明当前桶位中有数据，但是数据具体是 单个数据，还是链表 还是 红黑树 并不知道if ((e = oldTab[j]) != null) {//方便JVM GC时回收内存oldTab[j] = null;//第一种情况：当前桶位只有一个元素，从未发生过碰撞，这情况 直接计算出当前元素应存放在 新数组中的位置，然后//扔进去就可以了if (e.next == null)newTab[e.hash & (newCap - 1)] = e;//第二种情况：当前节点已经树化，本期先不讲，下一期讲，红黑树。QQ群：865-373-238else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order//第三种情况：桶位已经形成链表//低位链表：存放在扩容之后的数组的下标位置，与当前数组的下标位置一致。Node<K,V> loHead = null, loTail = null;//高位链表：存放在扩容之后的数组的下表位置为 当前数组下标位置 + 扩容之前数组的长度Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;//hash-> .... 1 1111//hash-> .... 0 1111// 0b 10000if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}

JDK1.7和1.8性能对标

HashMap,如果是通过hash算法得到的索引的位置全部不相同，即hash算法非常好，那样的话getkey方法的时间复杂度就是O(1),如果是hash的算法的技术的碰撞非常多，所以其相关的索引的位置就是一样，这样所有的key和value都是在一个桶中，或者是在同一链表中，或者是同一个树中，时间复杂度分别是O(log(n))和O(n),JDK1.8显然是对其做了很大的改善，将整体的性能给提升了很多很多。