关于面试:面试为了进阿里必须掌握HashMap原理和面试题图解版一

该系列文章收录在公众号【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 是线程平安的吗，为什么不是线程平安的？

JDK1.7 应用的是数组 + 单链表的数据结构。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 中，当雷同的 hash 值时，HashMap 一直地产生碰撞，那么雷同 key 地位的链表就会一直增长，当查问 HashMap 的相应 key 值的 Vaule 值时，就会去循环遍历这个超级大的链表，查问性能十分低下。

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

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

首先获取 hashcode，一个 32 位的 int 值
而后将 hashcode 左移 16 位的值进行与或，行将高位与低位进行异或运算，缩小碰撞机率。

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

设计起因：

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

HashMap 扩容步骤分成两步：

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

扩容变量

// 原的元素数组
Node<K,V>[] oldTab = table; 
// 老的元素数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length; 
// 老的扩容阀值设置
int oldThr = threshold;
// 新数组的容量，新数组的扩容阀值都初始化为 0
int 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 源码原理和面试题（图解版二）》

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

关于面试:面试为了进阿里必须掌握HashMap原理和面试题图解版一

前言

1. HashMap 的底层原理

HashMap 数据结构图（jdk1.8）

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

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

hash 哈希函数的设计原理

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

3. HashMap 扩容机制 resize（）

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

数据迁徙