对于写了这么久的HashMap，对其知之甚少，趁大三有点闲时，打算深入了解下HashMap的原理。

  1. HashMap、HashTable之间有什么关系
  2. HashMap在put、remove的时候做了什么
  3. resize（再哈希）是什么

  4. 为什么每次扩容，容量都是原来的二次方

    HashMap和HashTable间的关系

    HashMap和HashTable间的差异：

  5. HashMap是线程不安全的,HashTable几乎都加上了方法级别的Synchronize，所以同一时间最多只有一个线程可以对同个方法进行调用

  6. HashMap允许null键和null值,HashTable遇到null值会抛出NPE
    HashTable的源码分析戳这里

HashMap再put、remove的时候做了什么

JDK6

  1. /**
  2.  * 第一次注意到put有返回值
  3.  * 如果put之前key已经存在和值X的对应关系，则返回值X
  4.  * 如果put之前key没有对应关系，则返回null
  5.  */
  6. public V put(K key, V value) {
  7.     // 当key为null时，特殊处理，这是和HashTable不一样的地方
  8.     // HashMap允许key、value为null
  9.     if (key == null)
  10.         return putForNullKey(value);
  11.     // hash一下，这里用到的是扰动函数
  12.     int hash = hash(key.hashCode());
  13.     // 获取该hash值的bucketIndex
  14.     int i = indexFor(hash, table.length);
  15.     // 遍历对应bucktIndex位置的Entry
  16.     for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  17.         Object k;
  18.         // 比较该bucktIndex下的所有Entry
  19.         // 比较hash值、比较key是否相等（从值和地址两方面进行比较）
  20.         // 为什么要再比较次hash值
  21.         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  22.             V oldValue = e.value;
  23.             e.value = value;
  24.             e.recordAccess(this);
  25.             return oldValue;
  26.         }
  27.     }
  28.     // fail-fast的计数器
  29.     modCount++;
  30.     // 添加新值
  31.     addEntry(hash, key, value, i);
  32.     return null;
  33. }
  34. private V putForNullKey(V value) {
  35.     // 从Entry数组下标为0的位置开始一一遍历
  36.     for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  37.         // 是否存在这么一个entry，其key为null
  38.         // 如果存在则替换新值
  39.         if (e.key == null) {
  40.             V oldValue = e.value;
  41.             e.value = value;
  42.             // 钩子函数
  43.             // 可以看一下LinkedHashMap
  44.             e.recordAccess(this);
  45.             return oldValue;
  46.         }
  47.     }
  48.     // 计数器加一
  49.     modCount++;
  50.     // 新添加一个键值对
  51.     addEntry(0, null, value, 0);
  52.     return null;
  53. }
  54. void addEntry(int hash, K key, V value, int bucketIndex) {
  55.     // 获取下该bucketIndex下的Entry
  56.     Entry<K,V> e = table[bucketIndex];
  57.     // 产生了hash冲突。将Old Entry连接到New Entry后面
  58.     table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
  59.     // 判断是否要再hash
  60.     if (size++ >= threshold)
  61.         // 因为capacity本身就是2的n次方，见HashMap的初始方法
  62.         // 所以每次扩大，只需要*2
  63.         resize(2 * table.length);
  64. }
  65. void resize(int newCapacity) {
  66.     Entry[] oldTable = table;
  67.     int oldCapacity = oldTable.length;
  68.     if (oldCapacity == MAXIMUM_CAPACITY) {
  69.         threshold = Integer.MAX_VALUE;
  70.         return;
  71.     }
  73.     Entry[] newTable = new Entry[newCapacity];
  74.     // 移动数组
  75.     transfer(newTable);
  76.     table = newTable;
  77.     threshold = (int)(newCapacity * loadFactor);
  78. }
  79. void transfer(Entry[] newTable) {
  80.     Entry[] src = table;
  81.     int newCapacity = newTable.length;
  82.     // 遍历全部的Entry
  83.     for (int j = 0; j < src.length; j++) {
  84.         Entry<K,V> e = src[j];
  85.         // 如果该BucketIndex存在数值
  86.         if (e != null) {
  87.             src[j] = null;
  88.             do {
  89.                 // 保存下一个Entry
  90.                 Entry<K,V> next = e.next;
  91.                 // 获取该e对象在新entry数组的index
  92.                 int i = indexFor(e.hash, newCapacity);
  93.                 // 是否发生hash冲突，如果有，就接到e对象的后面，没有就是null
  94.                 e.next = newTable[i];
  95.                 // 将e设置到对应的位置
  96.                 newTable[i] = e;
  97.                 e = next;
  98.             } while (e != null);
  99.         }
  100.     }
  101. }

JDK7

在JDK6的基础上，没有做特别的改变，倒是去除了modCount的volatile关键字(1.7取消了modCount的volatile)。
移除volatile的原因:
对于单线程集合，没必要承担volatile的额外消耗；多线程情况下，也不应该使用单线程集合，所以在hashmap里面移除volatile

移除Volatile的原文

JDK8

需要红黑树的知识，待学习

再哈希

/**
 * 扩容，根据key的hash和数组总长度重新hash获取新的BucketIndex，然后存放
 * 因为不是线程安全的，再哈希可能会发生死循环
 */
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    // 移动数组
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

每次扩容，容量都是原来的二次方

容量都是2的N次，主要是为了下面的indexFor()埋下伏笔，我们在使用HashMap最希望它的Entry能平均分布，那样找起来更高效。我们想到的第一个算法就是hash % length，先保证不超过最大长度，其次保证hash坐落的位置。但是取模运算是所有运算符里较为繁杂的运算指令。大师们为了更高效，就不得不采用位运算符并让hash的每位都参与到运算中。这里放出式子hash & (length - 1)

/** 
 * Returns index for hash code h. 
 */  
static int indexFor(int h, int length) {  
    return h & (length-1);  
}

可以看一下，如果容量的长度不是2的幂次方

length: 1000 0000
          &
hash:   0110 1111

上述例子实际可存放的位置就只有一个: 1000 0000 ，会有大量的空间被浪费，hash的很多位没有参与到运算中去，增大了hash冲突，所以应该尽可能的让所有位都是1，那么理想状况下应该是如下所示

length: 1111 1111
          &
hash:   0110 1111

但是这样的容量很难通过一次移位获取，所以实际情况应该是2的N次方 - 1，尽可能的将1布满。如下所示

length: 0111 1111
          &
hash:   0110 1111

通过移位获取最大的2的N次方，减去1，获得最可能的理想情况，允许存在128个位置。一个是256，一个是255，前者只能存放1个位置，后者可以存放128个位置，其高效可想而知。

所以容量是2的幂次方是为了减少空间的浪费，降低hash冲突的几率