该系列文章收录在公众号【Ccww技术博客】，原创技术文章早于博客推出

前言

汇合在根底面试中是必备可缺的一部分，其中重要的HashMap更是少不了，那面试官会面试中发问那些问题呢，这些在JDK1.7和1.8有什么区别？？

  • HashMap的底层原理
  • HashMap的hash哈希函数的设计原理，以及HashMap下标获取形式？
  • HashMap扩容机制，hashMap中什么时候须要进行扩容，扩容resize()又是如何实现的
  • hashMap中put是如何实现的 ，JDK1.7和1.8有什么区别？
  • hashMap中get是如何实现的

  • 其余波及问题

    • HashMap具备的个性
    • 为什么Hash的底层数据长度总为2的N次方？如果输出值不是2的幂比方10会怎么样？
    • 加载因子为什么是 0.75？
    • 哈希表如何解决Hash抵触
    • 当有哈希抵触时，HashMap 是如何查找并确认元素的？
    • HashMap 是线程平安的吗，为什么不是线程平安的？

1. HashMap的底层原理

JDK1.7应用的是数组+ 单链表的数据结构。JDK1.8之后，应用的是数组+链表+红黑树的数据结构

HashMap数据结构图（jdk1.8）

//解决hash抵触，链表转成树的阈值，当桶中链表长度大于8时转成树 static final int TREEIFY_THRESHOLD = 8;//进行resize操作时，若桶中数量少于6则从树转成链表static final int UNTREEIFY_THRESHOLD = 6;/* 当须要将解决 hash 抵触的链表转变为红黑树时，须要判断下此时数组容量，若是因为数组容量太小（小于　MIN_TREEIFY_CAPACITY　）导致的 hash 抵触太多，则不进行链表转变为红黑树操作，转为利用　resize() 函数对　hashMap 扩容　*/static final int MIN_TREEIFY_CAPACITY = 64;

从HashMap常量中能够看出，当链表的深度达到8的时候，也就是默认阈值TREEIFY_THRESHOLD=8，就会主动扩容把链表转成红黑树的数据结构来把工夫复杂度从O(n)变成O(logN)进步了效率，而且当进行resize操作时，若桶中数量少于6则从树转成链表。

那为什么数据结构须要从JDK1.7换成JDK1.8的数组+链表+红黑树？

在JDK1.7中，当雷同的hash值时，HashMap一直地产生碰撞，那么雷同key地位的链表就会一直增长，当查问HashMap的相应key值的Vaule值时，就会去循环遍历这个超级大的链表，查问性能十分低下。

但在JDK1.8当链表超过8个节点数时，将会让红黑树来代替链表，查问性能失去了很好的晋升，从原来的是O(n)到O(logn)。

2. HashMap的hash哈希函数的设计原理，以及HashMap下标获取 hash &（n - 1）？

hash哈希函数的设计原理

static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
  1. 首先获取hashcode，一个32位的int值
  2. 而后将hashcode左移16位的值进行与或，行将高位与低位进行异或运算，缩小碰撞机率。

HashMap下标获取h % n = h &（n - 1）

  1. 取余运算，但在计算机运算中&必定比%快，又因为h % n = h &（n - 1），所以最终将第二步失去的hash跟n-1进行与运算。n是table中的长度。

设计起因：

  1. 肯定要尽可能升高hash碰撞，越扩散越好；
  2. 算法肯定要尽可能高效，因为这是高频操作, 因而采纳位运算；

3. HashMap扩容机制resize（）

HashMap扩容步骤分成两步：

  • 获取新值：新的容量值newCap ，新的扩容阀界值newThr获取
  • 数据迁徙：如果oldTab老数组不为空，阐明是扩容操作，那么波及到元素的转移操，遍历老数组，如果以后地位元素不为空，那么须要转移该元素到新数组

获取新值：新的容量值newCap ，新的扩容阀界值newThr获取

  • 扩容变量

    //原的元素数组Node<K,V>[] oldTab = table; //老的元素数组长度int oldCap = (oldTab == null) ? 0 : oldTab.length; // 老的扩容阀值设置int oldThr = threshold;// 新数组的容量，新数组的扩容阀值都初始化为0int newCap, newThr = 0;// 设置map的扩容阀值为 新的阀值 threshold = newThr;  //创立新的数组（对于第一次增加元素，那么这个数组就是第一个数组；对于存在oldTab的时候，那么这个数组就是要须要扩容到的新数组） Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 将该map的table属性指向到该新数组  table = newTab;

  • 当如果老数组长度oldCap > 0，阐明曾经存在元素，

    • 如果此时oldCap>=MAXIMUM_CAPACITY(1 << 30)，示意曾经到了最大容量，这时还要往map中put数据，则阈值设置为整数的最大值 Integer.MAX_VALUE，间接返回这个oldTab的内存地址
    • 如果扩容之后的新容量小于最大容量 ，且老的数组容量大于等于默认初始化容量（16），那么新数组的扩容阀值设置为老阀值的2倍（左移1位相当于乘以2，newCap = oldCap << 1），阈值也double（newThr= oldThr << 1）;
     // 如果老数组长度大于0，阐明曾经存在元素 if (oldCap > 0) {          if (oldCap >= MAXIMUM_CAPACITY) {              threshold = Integer.MAX_VALUE;                  return oldTab;          }          else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                    oldCap >= DEFAULT_INITIAL_CAPACITY)            newThr = oldThr << 1; // double threshold    }

  • 当老数组没有任何元素，如果老数组的扩容阀值大于0，那么设置新数组的容量为该阀值，newCap = oldThr。当newThr扩容阀值为0 ，newThr = (float)newCap * loadFactor（这一步也就意味着结构该map的时候，指定了初始化容量构造函数）;

     else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; .... if (newThr == 0) {     float ft = (float)newCap * loadFactor;      newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                (int)ft : Integer.MAX_VALUE);    }

  • 其余状况，设置新数组容量 为 16，且设置新数组扩容阀值为 160.75 = 12。0.75为负载因子，newCap =16，newThr=12（应用默认参数创立的该map，并且第一次增加元素）

     else { // zero initial threshold signifies using defaults            // 设置新数组容量 为 16            newCap = DEFAULT_INITIAL_CAPACITY;             // 设置新数组扩容阀值为 16*0.75 = 12。0.75为负载因子            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);       }

数据迁徙

如果oldTab老数组不为空，阐明是扩容操作，那么波及到元素的转移操，遍历老数组，如果以后地位元素不为空，那么须要转移该元素到新数组。

  • 如果元素没有有下一个节点，阐明该元素不存在hash抵触，因将元素存储到新的数组中，存储到数组的哪个地位须要依据hash值和数组长度来进行取模

     // 如果元素没有有下一个节点，阐明该元素不存在hash抵触  if (e.next == null)           newTab[e.hash & (newCap - 1)] = e;

  • 如果该节点为TreeNode类型，插入红黑树中

       // 如果该节点为TreeNode类型    else if (e instanceof TreeNode)             ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

  • 遍历链表，并将链表节点按原程序进行分组

    • 将元素的hash值 和 老数组的长度做与运算e.hash & oldCap，判断出是在原地位还是在原地位再挪动2次幂的地位（loTail低位指的是新数组的 0 到 oldCap-1 、hiTail高位指定的是oldCap 到 newCap - 1）

      • (e.hash & oldCap) == 0原地位，循环到链表尾端，赋值低位的元素loTail

      • (e.hash & oldCap) != 0 原地位再挪动2次幂的地位，循环到链表尾端，赋值高位的元素hiTail

         Node<K,V> loHead = null, loTail = null;  // 低位首尾节点 Node<K,V> hiHead = null, hiTail = null;  // 高位首尾节点 Node<K,V> next; // 遍历链表 do {       next = e.next;                      //如果hash值和该原长度做与运算等于0，阐明该元素能够搁置在低位链表中。     if ((e.hash & oldCap) == 0) {            // 如果没有尾，阐明链表为空          if (loTail == null)                   loHead = e;            // 如果有尾，那么链表不为空，把该元素挂到链表的最初。           else               loTail.next = e;          // 把尾节点设置为以后元素           loTail = e;          }         // 如果与运算后果不为0，阐明hash值大于老数组长度（例如hash值为17）         // 此时该元素应该搁置到新数组的高位地位上         else {                 if (hiTail == null)                       hiHead = e;                else                    hiTail.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;                    }

JDK1.8对resize()扩容办法进行了优化，通过rehash之后，元素的地位要么是在原地位，要么是在原地位再挪动2次幂的地位。

是不是有点不明确呢？那咱们来用图来解析一下：

联合e.hash & oldCapn取值判断是在高位还是在低位，即如图（a）示意扩容前的key1和key2两种key确定索引地位的示例，
图（b）示意扩容后key1和key2两种key确定索引，元素在从新计算hash之后，因为n变为2倍，那么n-1的mask范畴在高位多1bit(红色)，因而新的index就会产生这样的变动：

因而，咱们在裁减HashMap的时候，不须要像JDK1.7的实现那样从新计算hash，只须要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，能够看看下图为16裁减为32的resize示意图：

在JDK1.7中rehash扩容的时候，旧链表迁徙新链表的时候，如果在新表的数组索引地位雷同的链表元素会倒置，然而在JDK1.8进行了优化，从上图能够看出，JDK1.8链表元素不会倒置。因而不会呈现链表死循环的问题。

因为篇幅过长，将分成两篇来介绍，接下来内容看《面试：为了进阿里，必须把握HashMap源码原理和面试题（图解版二）》

各位看官还能够吗？喜爱的话，动动手指导个再看????呗！！谢谢反对！
欢送扫码关注，原创技术文章第一工夫推出