1、简介

HashMap是java.util.map接口下的实现类，继承了AbstractMap类，实现了Map接口，允许一个null键和多个null值，非线程安全，内部存储的元素是无序的，常用子类有LinkedHashMap

2、数据结构

HashMap的主干是一个Entry数组，Entry是HashMap的基本组成单元，每一个Entry包含了一个Key-Value的键值对。通过拉链法来解决hash碰撞。所以简单来说HashMap是由数组+链表构成的，在JDK1.8开始，引入了红黑树，并且将拉链法的插入方式改为了尾插法（JDk1.7之前都是头插法，有可能造成死循环），当链表长度大于阈值8且数组长度大于64时，链表会树化成红黑树，当红黑树中节点个数小于6时，树会变成链表。

3、重要成员变量

  1. //初始化容量大小，必须为2的整数幂，默认为16，可通过构造方法自定义 
  2. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
  4. //容量最大值，默认为2^30，必须为2的整数倍 
  5. static final int MAXIMUM_CAPACITY = 1 << 30; 
  7. //加载因子，默认为0.75，可通过构造方法自定义 
  8. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  10. //链表树化的节点数最小值8 
  11. static final int TREEIFY_THRESHOLD = 8; 
  13. //树转化为链表的最小节点数6 
  14. static final int UNTREEIFY_THRESHOLD = 6; 
  16. //树化时，哈希表的最小长度，如果达不到，则先进行resize扩容，再树化 
  17. static final int MIN_TREEIFY_CAPACITY = 64;

4、构造器

  1. //HashMap一共有四个构造器，分别是：
  3. /* 无参数构造器，使用默认的容量和负载因子 */ 
  4. public HashMap(){}   
  6. /* 指定容量参数构造器，使用默认的负载因子 */ 
  7. public HashMap(int initialCapacity){} 
  9. /* 指定容量参数和负载因子参数的构造器 */ 
  10. public HashMap(int initialCapacity, float loadFactor){} 
  12. /* 传入一个已存在的Map的构造器 */ 
  13. public HashMap(Map<? extends K, ? extends V> m){}
  15. //其中容量参数默认为16，HashMap的实际容量，一定是2的整数幂；负载因子的默认值为0.75，这是综合考虑了时间和空间后的选择，不建议修改。

5、在插入元素时，是如何计算插入位置的？

先调用key的hashCode()方法获得其初始hashCode，再讲该hashCode进行无符号右移16运算，得到一个结果，再将该结果与hashCode进行位异或运算得到一个hash值，在实际插入的时候，再讲该hash值与数组长度length-1后进行位与运算（此处的位与运算等价于hash值与length进行取余运算），计算出最终的插入位置。

  1. /* JDK1.8 */
  2. static final int hash(Object key) {
  3.     int h;
  4.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  5. }

5.1、为什么要将key的hashCode与其高16位进行异或运算

在java中，hashCode是32位的，通常对根据key值计算得到的原始hashcode进行取余运算，而取余运算有个缺陷，其结果对高位是无效的，只对低位有效，所以此处要先将原始的hashcode无符号右移16位，再与原始值进行异或运算，目的是使得高位的差异也能影响到取余运算的结果，从而降低哈希碰撞的概率。

6、 为什么HashMap的数组实际长度一定是2的整数幂

首先要明确一个概念：任意数对2的N次方进行%(取余)运算时，等同于其和2的N次方-1作&(位与)运算。而位与运算的效率比取余运算的效率要提升5~8倍。
为了降低hash碰撞，使得元素散列分布，在计算最终的插入位置时，会将hash值对数组的长度length进行取余运算。具体运算规则是：(length-1) & hash。
为了提升取余操作的运算效率，将取余运算转化成等价的位与运算，等价的条件就是length的值必须是2的整数幂。

综上所述，将length的值设置为2的整数幂，目的是为了提升运算效率，当然，最终目的是为了使得元素散列分布在数组上，降低hash碰撞的概率。

7、 HashMap如何保数组的实际长度一定是2的整数幂

HashMap有一个可以指定容量参数的构造器，那如果输入一个不是2的整数幂的数呢？HashMap内部通过 tableSizeFor() 方法保证其容量一定为2的整数幂，源码如下：

  1. /* 返回大于且最接近于cap的一个2的整数幂的值 */
  2. /* 例如：输入10，返回16； 输入20，返回32 */
  3. static final int tableSizeFor(int cap) {
  4.     int n = cap - 1;
  5.     n |= n >>> 1;
  6.     n |= n >>> 2;
  7.     n |= n >>> 4;
  8.     n |= n >>> 8;
  9.     n |= n >>> 16;
  10.     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  11. }
  1. * 实现原理：
  2. * 首先明确|运算：或运算，一种二进制位运算符，两个二进制位中有任意一个值为1，则位或运算结果为1
  3. * java中int占4个字节，即32位，其最大值为2^31-1
  4. * cap-1 其目的是为了排除cap原本就是2的整数幂次方，否则就得不到想要的结果
  6. 假设cap=18，n=cap-1=17,
  7. 17转为32位的二进制位：0000 0000 0000 0000 0000 0000 0001 0001
  9. 1、首先将n右移1位得到:0000 0000 0000 0000 0000 0000 0000 1000
  10. 与原来的n进行|运算：
  11.   0000 0000 0000 0000 0000 0000 0000 1000
  12. | 0000 0000 0000 0000 0000 0000 0001 0001
  13. --------------------------------------------
  14.   0000 0000 0000 0000 0000 0000 0001 1001
  16. 2、将上一步得到的n右移2位得到：0000 0000 0000 0000 0000 0000 0000 0110
  17. 与原来的n进行|运算得到：0000 0000 0000 0000 0000 0000 0001 1111
  19. 3、将上一步得到的n右移4位得到：0000 0000 0000 0000 0000 0000 0000 0001
  20. 与原来的n进行|运算得到：0000 0000 0000 0000 0000 0000 0001 1111
  22. 4、将上一步得到的n右移8位得到：0000 0000 0000 0000 0000 0000 0000 0000
  23. 与原来的n进行|运算得到：0000 0000 0000 0000 0000 0000 0001 1111
  25. 5、将上一步得到的n右移16位得到：0000 0000 0000 0000 0000 0000 0000 0000
  26. 与原来的n进行|运算得到：0000 0000 0000 0000 0000 0000 0001 1111
  27. 转换为10进制：2^4 + 2^3 + 2^2 + 2^1 + 2^0 = 31
  29. 6、最后，如果cap是小于0，则返回2^0=1;如果计算出的n已经大于MAXIMUM_CAPACITY，则返回n+1=32

8、HashMap的resize()算法

resize()方法是HashMap的扩容方法，这个方法非常的消耗性能，需要将原有的元素重新计算位置再放进去。
那么hashmap什么时候进行扩容呢？当Hashmap中的元素个数超过数组大小乘以loadFactor(负载因子)时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过160.75=12的时候，就把数组的大小扩展为216=32，即每次扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知Hashmap中元素的个数，那么预设元素的个数能够有效的提高Hashmap的性能。

9、HashMap的线程安全问题

ConcurrentHashMap是线程安全的。其key和value都不允许有null。JDK1.7之前是由分段锁（Segment继承自ReentrantLock）实现的线程安全，JDK1.8升级为CAS+synchronized实现线程安全，将数据切分为一个个Node，每个Node相对独立，都有自己的并发度。
Hashtable也是线程安全的，其继承自Dictionary类，Dictionary类是一个已经被废弃的类（见其源码中的注释）。父类都被废弃，自然而然也没人用它的子类Hashtable了。HashTable中所有的方法都用了synchronized关键字修饰，效率低，与ConcurrentHashMap不同，HashTable是整个锁住，并发效率极低。

9.1、初始化的数组的线程安全问题

HashMap初始化数组并不是在创建HashMap实例的时候进行的，而是在第一次put元素的时候进行初始化的。

  1. //HashMap中第一次put时初始化数组
  2. if ((tab = table) == null || (n = tab.length) == 0)
  3.     n = (tab = resize()).length;

此时就存在线程安全问题。
在ConcurrentHashMap中也是在第一次put时进行扩容的，但是它对扩容操作加入了CAS机制来保证线程安全。

  1. //ConcurrentHashMap中第一次put时初始化数组
  2. if (tab == null || (n = tab.length) == 0)
  3.     tab = initTable();
  5. //初始化
  6. private final Node<K,V>[] initTable() {
  7.     Node<K,V>[] tab; int sc;
  8.     while ((tab = table) == null || tab.length == 0) {
  9.         if ((sc = sizeCtl) < 0)
  10.             Thread.yield(); // lost initialization race; just spin
  11.         //通过CAS来保证线程安全    
  12.         else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
  13.             try {
  14.                 if ((tab = table) == null || tab.length == 0) {
  15.                     int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
  16.                     @SuppressWarnings("unchecked")
  17.                     Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  18.                     table = tab = nt;
  19.                     sc = n - (n >>> 2);
  20.                 }
  21.             } finally {
  22.                 sizeCtl = sc;
  23.             }
  24.             break;
  25.         }
  26.     }
  27.     return tab;
  28. }

9.2、put元素时的线程安全问题

HashMap在put元素时，先通过一系列的算法计算得到元素要插入的实际位置，再判断该位置上是否已存在元素，如果已存在元素，再判断该已存在元素是否与要插入的元素key相同，如果相同则覆盖value；如果当前位置不存在元素，则直接插入；如果当前位置已为链表或者树，则进行相应的插入操作。这个过程的特点就是先判断一个条件，再基于这个判断结果来进行下一步操作，但是HashMap中这个过程并非是原子性的操作，所以存在线程安全问题。
在ConcurrentHashMap中是通过CAS+Synchronized来保证线程安全的。

  1. //ConcurrentHashMap中，如果当前位置没有已存在元素，通过CAS来保插入的线程安全
  2. else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  3.     if (casTabAt(tab, i, null,
  4.                  new Node<K,V>(hash, key, value, null)))
  5.         break;                   // no lock when adding to empty bin
  6. }
  1. //如果当前位置已存在元素，通过synchronized来保证线程安全，并且使用的锁对象时当前位置节点，也就是说只会锁住当前这一个位置，而不会影响到其他位置的put操作，从而提升并发性能
  2. else {
  3.     V oldVal = null;
  4.     synchronized (f) {//只锁住当前位置的头结点对象
  5.         if (tabAt(tab, i) == f) {
  6.             if (fh >= 0) {
  7.                 binCount = 1;
  8.                 for (Node<K,V> e = f;; ++binCount) {
  9.                     K ek;
  10.                     if (e.hash == hash &&
  11.                         ((ek = e.key) == key ||
  12.                          (ek != null && key.equals(ek)))) {
  13.                         oldVal = e.val;
  14.                         if (!onlyIfAbsent)
  15.                             e.val = value;
  16.                         break;
  17.                     }
  18.                     Node<K,V> pred = e;
  19.                     if ((e = e.next) == null) {
  20.                         pred.next = new Node<K,V>(hash, key,
  21.                                                   value, null);
  22.                         break;
  23.                     }
  24.                 }
  25.             }
  26.             else if (f instanceof TreeBin) {
  27.                 Node<K,V> p;
  28.                 binCount = 2;
  29.                 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  30.                                                value)) != null) {
  31.                     oldVal = p.val;
  32.                     if (!onlyIfAbsent)
  33.                         p.val = value;
  34.                 }
  35.             }
  36.         }
  37.     }

9.3、resize扩容时的线程安全问题

HashMap在容器中的元素个数达到了一定的阈值（数组长度 x 负载因子）时或者链表树化时会进行扩容操作。扩容时会先重新分配一个长度为原来的2倍的数组空间，然后把原有的元素全部重新通过算法计算其位置并插入的新的数组中。在扩容操作期间，如果有其他线程进行插入、扩容操作的话，就会引起线程安全问题。
在ConcurrentHashMap中，进行扩容操作时，会把数组按照一定长度分段，并发时，每个线程如果发现当前正在进行扩容操作，就会各自领取一段长度，帮着进行扩容操作，而把put操作暂放，这个过程是通过CAS来保证的。

  1. //如果当前正在进行扩容操作，就帮忙一起扩容
  2. else if ((fh = f.hash) == MOVED)
  3.     tab = helpTransfer(tab, f);
  7. //通过CAS来保证每个线程只处理自己的那一部分，互不干扰
  8. final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
  9.     Node<K,V>[] nextTab; int sc;
  10.     if (tab != null && (f instanceof ForwardingNode) &&
  11.         (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
  12.         int rs = resizeStamp(tab.length);
  13.         while (nextTab == nextTable && table == tab &&
  14.                (sc = sizeCtl) < 0) {
  15.             if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  16.                 sc == rs + MAX_RESIZERS || transferIndex <= 0)
  17.                 break;
  18.             if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
  19.                 transfer(tab, nextTab);
  20.                 break;
  21.             }
  22.         }
  23.         return nextTab;
  24.     }
  25.     return table;
  26. }