扰动函数

首先贴上HashMap的源码：

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

这里不难发现，我们并没有直接返回hashCode方法里求得的哈希值，而是进行了一个位移后求异或的操作。通过高位和低位相异或增加了随机性，以减少碰撞的可能。

初始化容量和负载因子

HashMap需要容量为2的幂次，默认的初始容量是16，而当容量不足时会进行扩容，这时我们需要一个指标衡量HashMap的装载满的程度，这就是负载因子/装填因子，默认值为0.75。当装载的元素个数超过 容量*负载因子，则需要扩容，而扩容需要重建hash表，非常影响性能。因此我们希望在大概知道使用的元素数量级的时候对我们的HashMap进行初始容量的指定。
但这又涉及到一个问题，如果我指定的初始容量不满足容量的需要也就是不是2的幂次。这时HashMap会自动找到一个大于我们初始指定容量的2的幂次数。
下面是源码：

  1. static final float DEFAULT_LOAD_FACTOR = 0.75f; //这是装填因子
  3. //这一段是对指定容量的匹配
  4. static final int tableSizeFor(int cap) {
  5.         int n = cap - 1;
  6.         n |= n >>> 1;
  7.         n |= n >>> 2;
  8.         n |= n >>> 4;
  9.         n |= n >>> 8;
  10.         n |= n >>> 16;
  11.         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  12.     }

这里解释一下这个位运算的操作。首先我们假设输入的初始容量为9，二进制就是1001，这时我们先减一得到1000，然后再通过移位取或将低位填充1，就是1111，最后再加一得到10000就是我们要得到的16。
最后再说一个重要的点：由于负载因子的存在，你的预期容量实际不应该是预设容量的值。
举个例子，如果你觉得你可能会存入7个元素，这时你设置7为初始容量new HashMap<>(7);会自动给你扩充到8。但是问题在于，由于负载因子为0.75，实际上你在填充第6个元素就会达到扩容条件。这时应该使用的容量反而是16。
推荐使用的是 Maps.newHashMapWithExpectedSize(7);这样就可以自动去解算应该设置的初始大小。

扩容元素拆分

扩容过程在1.7的jdk需要重新计算哈希值，而在1.8中已经优化不再需要了。
扩容源码如下：

  1. final Node<K,V>[] resize() {
  2.         Node<K,V>[] oldTab = table;
  3.         int oldCap = (oldTab == null) ? 0 : oldTab.length;
  4.         int oldThr = threshold;
  5.         int newCap, newThr = 0;
  6.         if (oldCap > 0) {
  7.             if (oldCap >= MAXIMUM_CAPACITY) {
  8.                 threshold = Integer.MAX_VALUE;
  9.                 return oldTab;
  10.             }
  11.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  12.                      oldCap >= DEFAULT_INITIAL_CAPACITY)
  13.                 newThr = oldThr << 1; // double threshold
  14.         }
  15.         else if (oldThr > 0) // initial capacity was placed in threshold
  16.             newCap = oldThr;
  17.         else {               // zero initial threshold signifies using defaults
  18.             newCap = DEFAULT_INITIAL_CAPACITY;
  19.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  20.         }
  21.         if (newThr == 0) {
  22.             float ft = (float)newCap * loadFactor;
  23.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  24.                       (int)ft : Integer.MAX_VALUE);
  25.         }
  26.         threshold = newThr;
  27.         @SuppressWarnings({"rawtypes","unchecked"})
  28.             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  29.         table = newTab;
  30.         if (oldTab != null) {
  31.             for (int j = 0; j < oldCap; ++j) {
  32.                 Node<K,V> e;
  33.                 if ((e = oldTab[j]) != null) {
  34.                     oldTab[j] = null;
  35.                     if (e.next == null)
  36.                         newTab[e.hash & (newCap - 1)] = e;
  37.                     else if (e instanceof TreeNode)
  38.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  39.                     else { // preserve order
  40.                         Node<K,V> loHead = null, loTail = null;
  41.                         Node<K,V> hiHead = null, hiTail = null;
  42.                         Node<K,V> next;
  43.                         do {
  44.                             next = e.next;
  45.                             if ((e.hash & oldCap) == 0) {
  46.                                 if (loTail == null)
  47.                                     loHead = e;
  48.                                 else
  49.                                     loTail.next = e;
  50.                                 loTail = e;
  51.                             }
  52.                             else {
  53.                                 if (hiTail == null)
  54.                                     hiHead = e;
  55.                                 else
  56.                                     hiTail.next = e;
  57.                                 hiTail = e;
  58.                             }
  59.                         } while ((e = next) != null);
  60.                         if (loTail != null) {
  61.                             loTail.next = null;
  62.                             newTab[j] = loHead;
  63.                         }
  64.                         if (hiTail != null) {
  65.                             hiTail.next = null;
  66.                             newTab[j + oldCap] = hiHead;
  67.                         }
  68.                     }
  69.                 }
  70.             }
  71.         }
  72.         return newTab;
  73.     }

代码较长，原因是jdk1.8引入了红黑树，当链表长度超过8时就会转为红黑树。但是主体逻辑还算清晰。就是先判断是否为初次扩容，然后再保存当前容量阈值并进行扩容的操作，再通过拆分分配新的哈希表。
这里有一点需要注意，在初次扩容的时候，是先扩容再插入元素，而后续扩容都是先插入元素再扩容。
一般来说，我们扩容会把原来的长度扩充到2倍，所以要达到分散元素的目的，就将原来产生了碰撞的元素均匀的打散到新的位置去。
热点知识-Java的HashMap - 图1
由于我们扩容对于2进制来说就相当于将容量左移一位，因此我们在移动元素时，如果原来的哈希值新增位是0则元素位置不变，如果为1则相当于是原来位置加原来的容量。这也就解释了图中为何15处的元素有些留在原地，有些则转移到15+16=31的位置去了的情况。
这个算法很巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的槽中了。

插入

插入是哈希表的一个基本操作，其包含如下步骤：

  1. 计算插入元素哈希值并扰动
  2. 判断tab位是否为空或者长度为0，若是则扩容
  3. 根据哈希值计算下标，如果下标处为空则可直接插入，流程结束
  4. 若不空判断是链表还是树，并调用对应的方法插入（其中链表在jdk1.8是尾插，1.7是头插）
  5. 判断链表深度是否大于等于8，若是则转为红黑树
  6. 最后操作完毕判断是否超过阈值，是则扩容

源码如下：

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  2.                    boolean evict) {
  3.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  4.         if ((tab = table) == null || (n = tab.length) == 0)
  5.             n = (tab = resize()).length;
  6.         if ((p = tab[i = (n - 1) & hash]) == null)
  7.             tab[i] = newNode(hash, key, value, null);
  8.         else {
  9.             Node<K,V> e; K k;
  10.             if (p.hash == hash &&
  11.                 ((k = p.key) == key || (key != null && key.equals(k))))
  12.                 e = p;
  13.             else if (p instanceof TreeNode)
  14.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  15.             else {
  16.                 for (int binCount = 0; ; ++binCount) {
  17.                     if ((e = p.next) == null) {
  18.                         p.next = newNode(hash, key, value, null);
  19.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  20.                             treeifyBin(tab, hash);
  21.                         break;
  22.                     }
  23.                     if (e.hash == hash &&
  24.                         ((k = e.key) == key || (key != null && key.equals(k))))
  25.                         break;
  26.                     p = e;
  27.                 }
  28.             }
  29.             if (e != null) { // existing mapping for key
  30.                 V oldValue = e.value;
  31.                 if (!onlyIfAbsent || oldValue == null)
  32.                     e.value = value;
  33.                 afterNodeAccess(e);
  34.                 return oldValue;
  35.             }
  36.         }
  37.         ++modCount;
  38.         if (++size > threshold)
  39.             resize();
  40.         afterNodeInsertion(evict);
  41.         return null;
  42.     }

链表树化

当我们插入的碰撞元素较多，链表会增加的较长，从而影响哈希表的性能，这时我们需要对链表转化。
树化的源码如下：

  1. final void treeifyBin(Node<K,V>[] tab, int hash) {
  2.         int n, index; Node<K,V> e;
  3.         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  4.             resize();
  5.         else if ((e = tab[index = (n - 1) & hash]) != null) {
  6.             TreeNode<K,V> hd = null, tl = null;
  7.             do {
  8.                 TreeNode<K,V> p = replacementTreeNode(e, null);
  9.                 if (tl == null)
  10.                     hd = p;
  11.                 else {
  12.                     p.prev = tl;
  13.                     tl.next = p;
  14.                 }
  15.                 tl = p;
  16.             } while ((e = e.next) != null);
  17.             if ((tab[index] = hd) != null)
  18.                 //将树转化为红黑树
  19.                 hd.treeify(tab);
  20.         }
  21.     }

这一部分的代码并不复杂，就是通过一个函数将链表节点变为树节点，然后再按照规则进行连接成为树的结构。这里比较难的是将树转化为红黑树。由于红黑树也是一个十分重要的重点，故不在这里详细展开。
这里有几个注意事项：

  1. 链表树化的条件有两点；链表长度大于等于 8、桶容量大于 64，否则只是扩容，不会树化。
  2. 链表树化的过程中是先由链表转换为树节点，此时的树可能不是一颗平衡树。同时在树转换过程中会记录链表的顺序，tl.next = p，这主要方便后续树转链表和拆分更方便。

  3. 链表转换成树完成后，再进行红黑树的转换。红黑树的转换需要染色和旋转，以及比对大小。

    红黑树转链表

    由于在之前我们链表的树化时保留了链表的顺序，因此转链表的操作就十分简单了。直接将树节点转为链表节点就行。

    查找

    查找功能也是哈希表的重要功能之一，其流程大致如下。

  4. 根据Key值计算哈希值

  5. 判断Table是否为空，否则计算对应数组下标
  6. 访问数组元素是否为目标元素，否则是否为链表、树节点
  7. 如是链表节点遍历链表查找
  8. 如是树节点调用红黑树查找方法

    删除

    删除和插入一样，单看没啥难度，需要注意的点是红黑树本身删除的操作和红黑树小于容量的链表化。这里还是跳过红黑树删除的具体实现。

    遍历

    HashMap的遍历是用map.keySet()和map.entrySet()这两个方法，返回key集合和value集合。虽然HashMap的KeySet遍历是无序的，但是不论使用何种遍历方式，他们的遍历结果总是相同的。遍历顺序大体为先按照下标的顺序遍历，如遇到链表遍历链表再向下个下标走，遇到树则先遍历树根，然后按照中序遍历树。