前言

上一篇我们学习了List集合。下面我们继续学习map集合中的hashMap。我们思考下：hashMap中，底层结构是什么？添加元素的时候，是怎么put的？扩容的原理又是什么？JDK1.8为什么要引入红黑树，解决什么问题？

1、HashMap的底层结构

在JDK1.7的时候，HashMap底层是采用：
数组+链表（单向链表）的方式
头插法
JDK1.8的时候，HashMap底层是采用：
数组+链表（单向链表）+红黑树的方式，当链表的长度超过8的时候而且数组长度大于或等于64的时候，链表会转为红黑树，当红黑树的节点个数小于6的时候，重新转回链表
尾插法，解决1.7的扩容死循环问题
JDK1.7HashMap和JDK1.8HashMap的区别：
1.7中因为没有红黑树，链表容易过长。而且有个致命BUG，再多线程的情况下扩容，可能会出现死循环问题
1.8中，采用了红黑树来解决链表过长，查询效率低下问题。而且采用了尾插法解决了死循环问题

2、HashMap的初始化因子0.75和初始化容量

初始化容量大小为16。
初始化因子选择0.75。是因为这个是最佳选择。加载因子越大，index下标冲突概率也就越大、反而空间利用率是非常高的；
加载因子越小，index下标冲突概率也就越小，反而空间利用率不是非常高；
如果index下标冲突越高、反而查询的成本非常高，反之非常低
因此,必须在 “冲突的机会”与”空间利用率”之间寻找一种平衡与折衷
官方推荐使用0.75作为加载因子

3、HashMap的hash冲突问题

hash冲突：对象不同，但是hashCode相同，产生冲突后，会存放到链表中去，然后通过equal来比较相同的key，对象是否相同
index冲突：是因为底层做二进制运算产生相同的index，对象不同，但是index相同，源码中，计算index的时候，在&运算中把长度搞成奇数，来减少下标冲突问题，一旦有下标冲突，也是存放到链表中去（这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在，因为如果只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少hash碰撞）

3、扩容的原理

判断当前的size是不是大于阈值（容量 初始因子），而且在产生index冲突下才进行扩容，减少资源消耗，每次扩容2（为了再计算hash值和下标的时候减少hash冲突）的容量，先重新计算元素的index位置，防止取值的时候index错乱。再计算新增的容量的index值，进行扩容。
扩容的时候hash值不需要重新计算，只计算index值

4、JDK1.7中扩容死循环的问题，1.8中如何解决

再1.7中，死循环问题描述：在多线程的情况下，同时对hashMap进行扩容，扩容的时候会重新计算index下标，把原来的值移到新的index去，因为采用的是头插法，导致会改变next的引用顺序，又因为hashMap线程不安全，多线程情况下。另外一个线程的指向会反过来，会造成一直引用循环下去，造成死循环。
1.8使用尾插法，修复了多线程扩容死循环

5、源码流程分析

  • 1、判断链表是否为空,为空的话则进行第一次扩容（初始化数组长度为16，阈值为12），用于第一次put值
  • 2、计算数组的下标(hash值得计算（hashCode() 的高 16 位异或低 16 位，(h = k.hashCode()) ^ (h >>> 16)）和index的计算，index的计算是tab[i = (n - 1) & hash])，判断这个数组是否为空，为空直接存入链表元素
  • 3、不为空，则表示产生了index冲突或者hash冲突。如果hash值相同而且key相同，则进行值得覆盖
  • 4、如果index链表类型是红黑树的话，按照红黑树的插入规则进行插入
  • 5、如果index链表类型不是红黑树（还是链表），循环遍历，找到链表中最后一个元素，而且元素长度没有大于8，进行尾插法（测试下存放元素到哪里就转红黑树），长度大于或等于8而且数组的长度小于64的时候，会进行扩容，而且会先转双向链表，再到红黑树进行插入（TreeNode即是双向链表又是红黑树）
  • 6、最后当数组长度大于阈值，则进行扩容，因为扩容完成后要进行下标的计算，resize()的时候会判断链表是不是红黑树，是的话重新计算index的时候会查看双向链表中的长度是不是小于6，是的话把红黑树转回单向链表
    1. //put值的时候，大纲方法
    2. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    3.              boolean evict) {
    4.   Node<K,V>[] tab; Node<K,V> p; int n, i;
    5.   if ((tab = table) == null || (n = tab.length) == 0)
    6.       n = (tab = resize()).length;
    7.   if ((p = tab[i = (n - 1) & hash]) == null)
    8.       tab[i] = newNode(hash, key, value, null);
    9.   else {
    10.       Node<K,V> e; K k;
    11.       if (p.hash == hash &&
    12.           ((k = p.key) == key || (key != null && key.equals(k))))
    13.           e = p;
    14.       else if (p instanceof TreeNode)
    15.           e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    16.       else {
    17.           for (int binCount = 0; ; ++binCount) {
    18.               if ((e = p.next) == null) {
    19.                   p.next = newNode(hash, key, value, null);
    20.                   if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    21.                       treeifyBin(tab, hash);
    22.                   break;
    23.               }
    24.               if (e.hash == hash &&
    25.                   ((k = e.key) == key || (key != null && key.equals(k))))
    26.                   break;
    27.               p = e;
    28.           }
    29.       }
    30.       if (e != null) { // existing mapping for key
    31.           V oldValue = e.value;
    32.           if (!onlyIfAbsent || oldValue == null)
    33.               e.value = value;
    34.           afterNodeAccess(e);
    35.           return oldValue;
    36.       }
    37.   }
    38.   ++modCount;
    39.   if (++size > threshold)
    40.       resize();
    41.   afterNodeInsertion(evict);
    42.   return null;
    43. }
  1. 为什么重写Equals还要重写HashCode方法

因为默认情况下，对对象间进行Equals，默认比较的是地址，这个时候会不相等，当重写了equals之后，对象相等，但是HashCode还是不等的，阿里巴巴手册规定要一起重写

  1. HashMap如何避免内存泄漏问题

重写Equals和重写HashCode方法

  1. HashMap1.7底层是如何实现的

数组加链表

  1. HashMapKey为null存放在什么位置

为null的时候存在数组第0个位置

  1. HashMap如何解决Hash冲突问题

采用链表加红黑树

  1. HashMap底层采用单链表还是双链表

单向链表

  1. 时间复杂度O(1)、O(N)、O(Logn)区别

时间复杂度为O(n) 从头查询到尾部，查询多次
时间复杂度为O(1) 查询一次 比如根据数组下标查询
时间复杂度为O(logn) 平方查询 比如红黑树

  1. HashMap根据key查询的时间复杂度

当没有发生Hash冲突的时候，则时间复杂度为O（1）
当发生Hash冲突，只有链表存放的时候，时间复杂度为O（n）。如果转为了红黑树，则时间复杂度为O（logn）

  1. HashMap底层是有序存放的吗？

无序的
10、LinkedHashMap 和 TreeMap底层如何实现有序的
采用双向链表来实现
11、HashMap底层如何降低Hash冲突概率
扩容的时候采用2的N次方，然后计算的时候，用当前的长度减去1，保证计算出来的值最后一位是1，这样后面算出来的index能减少hash冲突
12、HashMap中hash函数是怎么实现的？
13、为什么不直接将key作为哈希值而是与高16位做异或运算？
为了减少hash冲突
14、HashMap如何存放1万条key效率最高
15、HashMap高低位与取模运算有那些好处
增加速度，而且能搞减少hash冲突
16、HashMap1.8如何避免多线程扩容死循环问题
采用尾插法
17、为什么加载因子是0.75而不是1
是因为这个是最佳选择。加载因子越大，index下标冲突概率也就越大、反而空间利用率是非常高的；
加载因子越小，index下标冲突概率也就越小，反而空间利用率不是非常高；
如果index下标冲突越高、反而查询的成本非常高，反之非常低
因此,必须在 “冲突的机会”与”空间利用率”之间寻找一种平衡与折衷
官方推荐使用0.75作为加载因子
18、为什么HashMap1.8需要引入红黑树
为了解决链表过长的问题
19、为什么链表长度>8需要转红黑树？而不是6？
20、什么情况下，需要从红黑树转换成链表存放？
当链表的长度超过8的时候而且数组长度大于或等于64的时候
21、如何在高并发的情况下使用HashMap
22、ConcurrentHashMap底层实现的原理