一、什么是hash表

数据结构的物理存储结构有两种：顺序存储结构和链式存储结构，在数组中根据下标查找某个元素，一次定位就可以找到，哈希表的主干就是数组。而这个下标的计算是通过hash函数来计算的，好的hash函数会使数据尽量的分散。
但是不管hash算法如何好，还是会有冲突发生，这就是hash冲突，解决方案有开放定址法，再散列函数法，链地址法，HashMap采用的就是链地址法，也就是数组加链表的方式。

二、HashMap实现原理

HashMap是Map的一个实现类，key不允许重复，可以为null，value无限制。jdk8之前，内部实现是由数组+链表来实现，jdk8的实现，在链表长度超过8的链表将转换为红黑树。
红黑树：https://www.cnblogs.com/skywang12345/p/3245399.html

  1. //默认的容量，即默认的数组长度 16
  2. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
  3. //最大的容量，即数组可定义的最大长度 
  4. static final int MAXIMUM_CAPACITY = 1 << 30;
  5. transient Node<K,V>[] table;
  6. //实际存储的键值对个数
  7. transient int size;
  8. //用于迭代防止结构性破坏的标量
  9. transient int modCount;

下面这三个属性是相关的，threshold 代表的下次扩容的size值，通常小于数组的实际长度。伴随着元素不断的被添加进数组，一旦数组中的元素数量达到这个阈值，那么表明数组应该被扩容而不应该继续任由元素加入。而这个阈值的具体值则由负载因子（loadFactor）和数组容量来决定，公式：threshold = capacity * loadFactor。

  1. int threshold;
  2. final float loadFactor;
  3. //HashMap 中默认负载因子为 0.75
  4. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  1. public HashMap(int initialCapacity, float loadFactor) {
  2.     if (initialCapacity < 0)
  3.         throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  4.     if (initialCapacity > MAXIMUM_CAPACITY)
  5.         initialCapacity = MAXIMUM_CAPACITY;
  6.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
  7.         throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
  8.     this.loadFactor = loadFactor;
  9.     this.threshold = tableSizeFor(initialCapacity);
  10. }

这是一个最基本的构造函数，需要调用方传入两个参数，initialCapacity 和 loadFactor。程序的大部分代码在判断传入参数的合法性，initialCapacity 小于零将抛出异常，大于 MAXIMUM_CAPACITY 将被限定为 MAXIMUM_CAPACITY。loadFactor 如果小于等于零或者非数字类型也会抛出异常。

整个构造函数的核心在对 threshold 的初始化操作：

  1. static final int tableSizeFor(int cap) {
  2.     int n = cap - 1;
  3.     n |= n >>> 1;
  4.     n |= n >>> 2;
  5.     n |= n >>> 4;
  6.     n |= n >>> 8;
  7.     n |= n >>> 16;
  8.     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  9. }

这是一个小巧但精妙的方法，这里通过异或的位运算将两个字节的 n 打造成比 cap 大但最接近 2 的 n 次幂的一个数值

1.1 put方法的实现

添加一个元素只需要传入一个键和一个值即可，putVal 方法是关键

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
  2.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  3.     //如果 table 还未被初始化，那么初始化它
  4.     if ((tab = table) == null || (n = tab.length) == 0)
  5.         n = (tab = resize()).length;
  6.     //根据键的 hash 值找到该键对应到数组中存储的索引
  7.     //如果为 null，那么说明此索引位置并没有被占用
  8.     //这里因为n始终是2的n次方，所以n-1 的二进制就全是1
  9.     if ((p = tab[i = (n - 1) & hash]) == null)
  10.         tab[i] = newNode(hash, key, value, null);
  11.     //不为 null，说明此处已经被占用，只需要将构建一个节点插入到这个链表的尾部即可
  12.     else {
  13.         Node<K,V> e; K k;
  14.         //当前结点和将要插入的结点的 hash 和 key 相同，说明这是一次修改操作
  15.         if (p.hash == hash &&
  16.             ((k = p.key) == key || (key != null && key.equals(k))))
  17.             e = p;
  18.         //如果 p 这个头结点是红黑树结点的话，以红黑树的插入形式进行插入
  19.         else if (p instanceof TreeNode)
  20.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  21.         //遍历此条链表，将构建一个节点插入到该链表的尾部
  22.         else {
  23.             for (int binCount = 0; ; ++binCount) {
  24.                 if ((e = p.next) == null) {
  25.                     p.next = newNode(hash, key, value, null);
  26.                     //如果插入后链表长度大于等于 8 ，将链表裂变成红黑树
  27.                     if (binCount >= TREEIFY_THRESHOLD - 1)
  28.                         treeifyBin(tab, hash);
  29.                     break;
  30.                 }
  31.                 //遍历的过程中，如果发现与某个结点的 hash和key，这依然是一次修改操作 
  32.                 if (e.hash == hash &&
  33.                     ((k = e.key) == key || (key != null && key.equals(k))))
  34.                     break;
  35.                 p = e;
  36.             }
  37.         }
  38.         //e 不是 null，说明当前的 put 操作是一次修改操作并且e指向的就是需要被修改的结点
  39.         if (e != null) { 
  40.             V oldValue = e.value;
  41.             if (!onlyIfAbsent || oldValue == null)
  42.                 e.value = value;
  43.             afterNodeAccess(e);
  44.             return oldValue;
  45.         }
  46.     }
  47.     ++modCount;
  48.     //如果添加后，数组容量达到阈值，进行扩容
  49.     if (++size > threshold)
  50.         resize();
  51.     afterNodeInsertion(evict);
  52.     return null;
  53. }

从整体上来看，该方法的逻辑已经清晰，然后看看一些细节。

首先，我们看 resize 这个方法是如何对 table 进行初始化的

  1. //扩容方法
  2. final Node<K,V>[] resize() {
  3.     Node<K,V>[] oldTab = table;
  4.     //拿到旧数组的长度
  5.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  6.     int oldThr = threshold;
  7.     int newCap, newThr = 0;
  8.     //说明旧数组已经被初始化完成了，此处需要给旧数组扩容
  9.     if (oldCap > 0) {
  10.         //极限的限定，达到容量限定的极限将不再扩容
  11.         if (oldCap >= MAXIMUM_CAPACITY) {
  12.             threshold = Integer.MAX_VALUE;
  13.             return oldTab;
  14.         }
  15.         //未达到极限，将数组容量扩大两倍，阈值也扩大两倍
  16.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  17.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  18.             newThr = oldThr << 1; 
  19.     }
  20.     //构造函数根据传入的容量已经计算了下次扩容的一个合适的数组容量暂存在threshold中，
  21.     //这里直接使用
  22.     else if (oldThr > 0) 
  23.         newCap = oldThr;
  24.     //数组未初始化并且阈值也为0，说明一切都以默认值进行构造
  25.     else {
  26.         newCap = DEFAULT_INITIAL_CAPACITY;
  27.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  28.     }
  29.     //newCap = oldThr 之后并没有计算阈值，所以 newThr = 0
  30.     if (newThr == 0) {
  31.         float ft = (float)newCap * loadFactor;
  32.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  33.                   (int)ft : Integer.MAX_VALUE);
  34.     }
  35.     threshold = newThr;
  36.     //根据新的容量初始化一个数组
  37.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  38.     table = newTab;
  39.     //旧数组不为 null，这次的 resize 是一次扩容行为
  40.     if (oldTab != null) {
  41.         //将旧数组中的每个节点位置相对静止地拷贝值新数组中
  42.         for (int j = 0; j < oldCap; ++j) {
  43.             Node<K,V> e;
  44.             //获取头结点
  45.             if ((e = oldTab[j]) != null) {
  46.                 oldTab[j] = null;
  47.                 //说明链表或者红黑树只有一个头结点，转移至新表
  48.                 if (e.next == null)
  49.                     newTab[e.hash & (newCap - 1)] = e;
  50.                 //如果 e 是红黑树结点，红黑树分裂，转移至新表
  51.                 else if (e instanceof TreeNode)
  52.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  53.                 //这部分是将链表中的各个节点原序地转移至新表中，我们后续会详细说明
  54.                 else { 
  55.                     Node<K,V> loHead = null, loTail = null;
  56.                     Node<K,V> hiHead = null, hiTail = null;
  57.                     Node<K,V> next;
  58.                     do {
  59.                         next = e.next;
  60.                         if ((e.hash & oldCap) == 0) {
  61.                             if (loTail == null)
  62.                                 loHead = e;
  63.                             else
  64.                                 loTail.next = e;
  65.                             loTail = e;
  66.                         } else {
  67.                             if (hiTail == null)
  68.                                 hiHead = e;
  69.                             else
  70.                                 hiTail.next = e;
  71.                             hiTail = e;
  72.                         }
  73.                     } while ((e = next) != null);
  74.                     if (loTail != null) {
  75.                         loTail.next = null;
  76.                         newTab[j] = loHead;
  77.                     }
  78.                     if (hiTail != null) {
  79.                         hiTail.next = null;
  80.                     newTab[j + oldCap] = hiHead;
  81.                     }
  82.                 }
  83.             }
  84.         }
  85.     }
  86.     //不论你是扩容还是初始化，都可以返回 newTab
  87.     return newTab;

HashMap - 图1

1.2 remove方法的实现

删除操作就是一个查找+删除的过程，相对于添加操作其实容易一些，但那是你基于上述添加方法理解的不错的前提下。

  1. public V remove(Object key) {
  2.     Node<K,V> e;
  3.     return (e = removeNode(hash(key), key, null, false, true)) == null ?
  4.         null : e.value;
  5. }
  7. final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {
  8.     Node<K,V>[] tab; Node<K,V> p; int n, index;
  9.     //表不为空，并且索引处有值
  10.     if ((tab = table) != null && (n = tab.length) > 0 &&
  11.         (p = tab[index = (n - 1) & hash]) != null) {
  12.         Node<K,V> node = null, e; K k; V v;
  13.         //如果跟头节点相等，则将待删除node指向头节点
  14.         if (p.hash == hash &&
  15.             ((k = p.key) == key || (key != null && key.equals(k))))
  16.             node = p;
  17.         //如果有下个节点
  18.         else if ((e = p.next) != null) {
  19.             //如果是红黑树，通过红黑树的操作方法获得node
  20.             if (p instanceof TreeNode)
  21.                 node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
  22.             else {
  23.                 //否则就循环查找待删除node
  24.                 do {
  25.                     if (e.hash == hash &&
  26.                         ((k = e.key) == key ||
  27.                          (key != null && key.equals(k)))) {
  28.                         node = e;
  29.                         break;
  30.                     }
  31.                     p = e;
  32.                 } while ((e = e.next) != null);
  33.             }
  34.         }
  35.         //如果node不为空，
  36.         if (node != null && 
  37.             (!matchValue || 
  38.                 (v = node.value) == value ||(value != null && value.equals(v)))) {
  39.             //是红黑树，用红黑树的删除方法
  40.             if (node instanceof TreeNode)
  41.                 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
  42.             else if (node == p)
  43.                 //如果是头节点，则直接将下一个节点设置为头节点
  44.                 tab[index] = node.next;
  45.             else
  46.                 //否则，将头节点的下个节点设置为待删除的下一个节点
  47.                 p.next = node.next;
  48.             ++modCount;
  49.             --size;
  50.             afterNodeRemoval(node);
  51.             return node;
  52.         }
  53.     }
  54.     return null;
  55. }

三、总结

HashMap通过控制容量是2的n次方，初始值是16，便于hash的计算（可以使用位操作），加载因子是空间利用率和查询修改效率直接的一个平衡，默认是0.75。

1.7之前的版本并发下添加数据可能会引起闭环，导致死循环，产生原因，当两个线程同时进行扩容的时候，某个位置上有链表 1->2->3，假如线程1执行完第一行后挂起，e指向1，e.next指向2，当线程2扩容后，此位置上到链表变成了2 ->1，然后线程1开始执行
执行第一行后 next -> null
第二行 e.next -> 2 ->1
第三行 newTable[i] -> e 已经形成闭环
第四行 e -> null 退出循环

  1. 1、Entry<K,V> next = e.next;     
  2. 2、e.next = newTable[i];
  3. 3、newTable[i] = e;
  4. 4、e = next;