• 1 HashMap 內部結構
• 2 HashMap#put
  • 2.1 流程
  • 2.2 Object#hashCode、Object#equals
• 3 Resize
  • 3.1 JDK 7 流程
  • 3.2 JDK 8 流程
  • 3.3 建立避免 resize 既 HashMap
• 4 筆記
  • 4.1 內部運作
  • 4.2 測試用代碼
    • 4.2.1 Oracle JDK 7 既測試結果
    • 4.2.2 Oracle JDK 8 既測試結果
  • 4.3 Mutable key 既問題
• 5 參考資料

• 如果 HashMap 既 entries 裡面存在 key 既 key，就用 value 覆蓋果個 entry 既 value。
• 如果 HashMap 既 entries 裡面唔存在 key 既 key，就將 key 同 value 作為新既 entry 放入 HashMap 既 entries 之中。

1. 對 key 進行 Object#hashCode，得出 hash（null key 既 hash 係 0）。
2. 將 hash 以及 bit-shifted hash 進行 bitwise XOR 處理（HashMap#hash）。
   • 令到除左 lower bits 之外，連 higher bits 都可以影響到 hash。
   • 目的係萬一我地有啲寫得差既 hashCode method，呢一層既處理可以幫我地把關。
   • 操作／處理
     • Bitwise XOR with bit-shifted hash（Oracle JDK 7、Oracle JDK 8）
     • Bitwise XOR with hash seed（Oracle JDK 7）
3. 對 hash 進行 & (<bucket size> - 1)，得出 bucket index（null key 既 bucket index 係 0）。
   • 因為 bucket size 係 2 既次方數，所以結果同 % 一樣，但就會 efficient 啲。
4. 將 entry 覆蓋或者放入 HashMap 既特定 bucket
   • Bucket 既 data structure
     • 如果 HashMap 既容量達到 64 而且 bucket 既 linked list 長度超過 8，就會 treeify 成 red-black tree，否則就繼續用 linked list。
   • Collision
     • 因為我地將無限值既 hash 轉化成 bucket index，咁就有 collision 既可能，bucket 有可能會存放多過 1 個 element。
     • Collision 情境
       • 一樣既 hash，所以得出一樣既 bucket index。
       • 唔一樣既 hash，但得出一樣既 bucket index。
       • 唔一樣既 hash，而又得出唔一樣既 bucket index。
     • 處理 hash collision
       • 如果 bucket index 所在既 bucket 未有 linked list／red-black tree，咁就 init 一個出黎，放呢個 entry 落去。
       • 如果 bucket index 所在既 bucket 已經存在 linked list／red-black tree，咁就由頭到尾 traverse 成個 linked list／red-black tree。
         1. 對每個 element 既 key 進行 Object#equals，睇下 key 係咪已經喺呢個 HashMap 裡面存在。
         2. 如果一樣，就取代個 value；否則，整一個新既 linked list element，然後將 linked list 既最後一個 element（佢既 next）指向呢個新既 element。

• Object#hashCode 既 contract
  • 如果 equals method 所用到既 data 冇改變過，咁不斷 call hashCode method 返回既結果喺同一個 runtime 裡面必須維持不變。
  • 當 2 個 objects 通過 equals method 得出 true 既結果，咁佢地既 hashCode method 既結果就必須要返回一樣既 int value。
  • 當 2 個 objects 通過 equals method 得出 false 既結果，佢地既 hashCode method 既結果係冇必要返回唔同既 int values，但唔同既 int values 有可以提升 hash table 既效能。
• Object#equals 既 contract
  • o.equals(o) 應該要返回 true。
  • 只有當 a.equals(b) 既結果係 true，咁 b.equals(a) 既結果都應該要係 true。
  • a.equals(b) 以及 b.equals(c) 既結果都係 true 既話，a.equals(c) 眉結果應該要係 true。
  • 如果 equals method 所用到既 data 冇改變過，咁不斷 call a.equals(b) 返回既結果應該維持不變。
  • o.equals(null) 既結果應該要係 false。
  • Override equals method 既同時係需要 override 埋 hashCode method。

• "Aa"、"BB"
  • Hash 同樣係 2112。
    • String#hashCode 既計法將係每個 char 作為 int value 乘以 31 既 char index（右至左，0-based）咁多既次方。
      • A 既 ASCII 係 65。
      • a 既 ASCII 係 97。
      • B 既 ASCII 係 66。
      • 65 * 31 + 97 等於 66 * 31 + 66 等於 2112。
  • String#equals 既結果係 false。

• 如果用 HashMap 既 no-arg constructor，咁默認就會有 16 個 buckets（DEFAULT_INITIAL_CAPACITY）。
• 如果用 HashMap 既 new HashMap<>(int initialCapacity) constructor 或者 new HashMap<>(int initialCapacity, float loadFactor) constructor，咁 bucket 數量就會係不少於 initialCapacity 而最接近 2 既次方數既一個數字（e.g. 3 就會得出 4，而 10 就會得出 16）。

• 新增呢個 entry 之前，實際數量達到容量既 load factor
• 當前既 bucket 有 linked list（出現 collision）

1. 建立一個全新既 bucket array，容量係舊既 2 倍。
2. 將本來既 bucket array 既所有 entries 抄過去新既 bucket array（HashMap#transfer(Entry[] newTable) method）。
   1. 對所有 bucket 既 linked list
      1. 由 linked list 第 1 個 element 開始至到最後一個 element
         1. 對 entry 既 hash 進行 & (<bucket size> - 1)，得出新既 bucket index
         2. 將 entry 放喺新 bucket 既頭部，佢會（佢既 next）指向現有既 entry（如果未有就 null）。

1. 建立一個全新既 bucket array，容量係舊既 2 倍。
2. 將本來既 bucket array 既所有 entries 抄過去新既 bucket array。
   1. 對所有舊 buckets
      • 如果係 linked list
        1. 由 linked list 第 1 個 element 開始至到最後一個 element
           1. 對 entry 既 hash 進行 & <old bucket size>
              • 如果結果係 0（即係屬於前半部分，屬於舊既 bucket indexes）
                1. 將 entry 放喺新 linked list 既尾部（借助 loHead、loTail）。如果已經有 entry，現有 entry（佢既 next）會指向呢個 entry。
              • 如果結果唔係 0（即係屬於後半部分，屬於新增既 bucket indexes）
                1. 將 entry 放喺新 linked list 既尾部（借助 hiHead、hiTail）。如果已經有 entry，現有 entry（佢既 next）會指向呢個 entry。
           2. 將新 buckets 指向 loHead、hiHead
              • 屬於新 buckets 前半部分既果一個 linked list 就會係 loHead（newTab[j] = loHead;）。
              • 屬於新 buckets 後半部分既果一個 linked list 就會係 hiHead（newTab[j + oldCap] = hiHead;）。
      • 如果係 red-black tree
        1. 同處理 linked list 既方式相似，最後 loHead、hiHead 會 treeify 成 red-black trees。

• 理論上，如果出現過多既 collisions，以上既做法都唔可以保證 HashMap 唔會 resize。
• 實際上，資料本身帶有隨機性，而只要我地寫好啲 hashCode method，唔好令到 collision 咁容易發生就得。

• HashMap#put 係用 & (<bucket size> - 1)
  • 目的係要知道 key 屬於邊一個 bucket index，所以就需要知道係 0 至 <bucket size> - 1 邊一個。
• JDK 8 既 HashMap#resize 係用 & <old bucket size>
  • 目的係要知道現有既某個 bucket 既每一個 entry 喺新既 bucket array 裡面屬於前半部分（舊既 bucket indexes）定係後半部分（新既 bucket indexes），所以就需要知道新增既 bit 係 0 定係 1。
  • 新增既 bit 就係舊 bucket size 既二進制數字既 1 字果個位。
  • 想知道一個二進制數字對象特定既 bits 係 0 定係 1，就要對佢進行 bit masking 操作。
    1. 需要用一個二進制數字作為 mask——只有想要既 bits 係 1 而其他唔想要既 bits 係 0 既二進制數字。
    2. 用呢個 mask 對二進制數字對象進行 bitwise AND（&）操作。
    3. 而對舊 bucket index 既二進制數字進行 bit masking 所得出既結果只有 2 個。
       • 所有 bits 都係 0（亦即係 0）
       • 第 1 個 bit 係 1，其他 bits 係 0（亦即係舊 bucket index）
• 因為 bucket size 一定係 2 既次方數，所以佢既二進制一定係 1 後面有 N 個 0。
• 例子：容量由 16 resize 成 32
  • 舊 HashMap
    • 舊 bucket size 16 既二進制係 10000。
    • 舊 bucket size 16 - 1 既二進制係 1111。
  • 新 HashMap
    • 新 bucket size 32 既二進制係 100000。
    • 新 bucket size 32 - 1 既二進制係 11111。
  • 新增既 bit 係指 10000 既 1（2^4）。
    • 舊 HashMap 最大既 bucket index 1111 + 1 = 10000——第 1 個新增既 bucket index。
    • 10000 開始直至 11111 都係新增既 bucket indexes。

1public class HashMapTest {
2
3    public static void main(String[] args) {
4
5        final int cap = 16;
6        final int size = 28;
7
8        final Map<Foo, Integer> map = new HashMap<>(cap);
9
10        for (int i=0; i<size; i++) {
11            map.put(new Foo(i), i);
12            HashMapDebugUtils.printMap(map);
13        }
14    }
15}

1public final class HashMapDebugUtils {
2    private static Field nextField;
3
4    static {
5        try {
6            final Class<?> entryClass = Class.forName("java.util.HashMap$Entry");
7            nextField = entryClass.getDeclaredField("next");
8            nextField.setAccessible(true);
9        } catch (Exception e) {
10            try {
11                final Class<?> entryClass = Class.forName("java.util.HashMap$Node");
12                nextField = entryClass.getDeclaredField("next");
13                nextField.setAccessible(true);
14            } catch (Exception ex) {
15                ex.printStackTrace();
16            }
17        }
18    }
19
20    private HashMapDebugUtils() {}
21
22    public static void printMap(Map<?, ?> map) {
23        try {
24            final Class<?> mapType = map.getClass();
25            final Field tableField = mapType.getDeclaredField("table");
26            tableField.setAccessible(true);
27
28            final Object[] bucketArr = (Object[]) tableField.get(map);
29            final int capacity = bucketArr.length;
30
31            System.out.printf("Capacity: %5d", capacity);
32            System.out.printf("%5s|%5s", " ", " ");
33            System.out.printf("Size: %5d", map.size());
34            printBuckets(bucketArr);
35            System.out.println();
36        } catch (Exception e) {
37            e.printStackTrace();
38        }
39    }
40
41    private static void printBuckets(final Object[] bucketArr) throws Exception {
42
43        System.out.printf("%5s|%5s", " ", " ");
44        System.out.printf("Buckets: ");
45
46        for (int i=0; i<bucketArr.length; i++) {
47            printBucket(i, bucketArr[i]);
48
49            if (i<bucketArr.length-1) {
50                System.out.print(" | ");
51            }
52        }
53    }
54
55    private static void printBucket(int index, Object entry) throws Exception {
56
57        if (entry==null) {
58            System.out.printf("[%d]:  . ", index);
59            return;
60        }
61
62        final boolean isRedBlackTree = "java.util.HashMap$TreeNode".equals(entry.getClass().getName());
63
64        int count = 0;
65        do {
66            count++;
67            entry = nextField.get(entry);
68        } while (entry!=null);
69
70        System.out.printf("[%d]: %2d", index, count);
71        System.out.print(isRedBlackTree ? "t" : " ");
72    }
73}

1public final class Foo {
2    private final int val;
3
4    public Foo(int val) {
5        this.val = val;
6    }
7
8    @Override
9    public int hashCode() {
10        return Math.max(0, val-11);
11    }
12
13    @Override
14    public boolean equals(Object obj) {
15        if (this == obj) return true;
16        if (!(obj instanceof Foo)) return false;
17        Foo other = (Foo) obj;
18        return val == other.val;
19    }
20}

• 當容量係 16 既情況下，實際數量係有機會去到 27。
• 當新增第 28 個 entry 既時候，容量先至由 16 擴大到 32。

1Capacity:    16     |     Size:     1
2Capacity:    16     |     Size:     2
3Capacity:    16     |     Size:     3
4Capacity:    16     |     Size:     4
5Capacity:    16     |     Size:     5
6Capacity:    16     |     Size:     6
7Capacity:    16     |     Size:     7
8Capacity:    16     |     Size:     8
9Capacity:    16     |     Size:     9
10Capacity:    16     |     Size:    10
11Capacity:    16     |     Size:    11
12Capacity:    16     |     Size:    12
13Capacity:    16     |     Size:    13
14Capacity:    16     |     Size:    14
15Capacity:    16     |     Size:    15
16Capacity:    16     |     Size:    16
17Capacity:    16     |     Size:    17
18Capacity:    16     |     Size:    18
19Capacity:    16     |     Size:    19
20Capacity:    16     |     Size:    20
21Capacity:    16     |     Size:    21
22Capacity:    16     |     Size:    22
23Capacity:    16     |     Size:    23
24Capacity:    16     |     Size:    24
25Capacity:    16     |     Size:    25
26Capacity:    16     |     Size:    26
27Capacity:    16     |     Size:    27
28Capacity:    32     |     Size:    28

• 當實際數量去到 9 而舊容量係 16（多過 TREEIFY_THRESHOLD 既 8 但係容量小過 MIN_TREEIFY_CAPACITY 既 64），容量會由 16 擴大到 32。
• 當實際數量去到 10 而舊容量係 32（多過 TREEIFY_THRESHOLD 既 8 但係容量小過 MIN_TREEIFY_CAPACITY 既 64），容量會由 32 擴大到 64。
• 當實際數量去到 11 而舊容量係 64（多過 TREEIFY_THRESHOLD 既 8 而且容量達到 MIN_TREEIFY_CAPACITY 既 64），bucket 會由 linked list treeify 成 red-black tree。

1Capacity:    16     |     Size:     1     |     Buckets: [0]:  1 
2Capacity:    16     |     Size:     2     |     Buckets: [0]:  2 
3Capacity:    16     |     Size:     3     |     Buckets: [0]:  3 
4Capacity:    16     |     Size:     4     |     Buckets: [0]:  4 
5Capacity:    16     |     Size:     5     |     Buckets: [0]:  5 
6Capacity:    16     |     Size:     6     |     Buckets: [0]:  6 
7Capacity:    16     |     Size:     7     |     Buckets: [0]:  7 
8Capacity:    16     |     Size:     8     |     Buckets: [0]:  8 
9Capacity:    32     |     Size:     9     |     Buckets: [0]:  9 
10Capacity:    64     |     Size:    10     |     Buckets: [0]: 10 
11Capacity:    64     |     Size:    11     |     Buckets: [0]: 11t
12Capacity:    64     |     Size:    12     |     Buckets: [0]: 12t
13Capacity:    64     |     Size:    13     |     Buckets: [0]: 12t
14Capacity:    64     |     Size:    14     |     Buckets: [0]: 12t
15Capacity:    64     |     Size:    15     |     Buckets: [0]: 12t
16Capacity:    64     |     Size:    16     |     Buckets: [0]: 12t
17Capacity:    64     |     Size:    17     |     Buckets: [0]: 12t
18Capacity:    64     |     Size:    18     |     Buckets: [0]: 12t
19Capacity:    64     |     Size:    19     |     Buckets: [0]: 12t
20Capacity:    64     |     Size:    20     |     Buckets: [0]: 12t
21Capacity:    64     |     Size:    21     |     Buckets: [0]: 12t
22Capacity:    64     |     Size:    22     |     Buckets: [0]: 12t
23Capacity:    64     |     Size:    23     |     Buckets: [0]: 12t
24Capacity:    64     |     Size:    24     |     Buckets: [0]: 12t
25Capacity:    64     |     Size:    25     |     Buckets: [0]: 12t
26Capacity:    64     |     Size:    26     |     Buckets: [0]: 12t
27Capacity:    64     |     Size:    27     |     Buckets: [0]: 12t
28Capacity:    64     |     Size:    28     |     Buckets: [0]: 12t

1public class Bar {
2    private int val;
3
4    public Bar(int val) {
5        this.val = val;
6    }
7
8    public void setVal(int val) {
9        this.val = val;
10    }
11
12    @Override
13    public int hashCode() {
14        return val;
15    }
16
17    @Override
18    public boolean equals(Object obj) {
19        if (this == obj) return true;
20        if (!(obj instanceof Bar)) return false;
21        Bar other = (Bar) obj;
22        System.out.println("Bar#equals: " + (val==other.val) + " (" + val + " = " + other.val + ")");
23        return val == other.val;
24    }
25}

1public class HashMapWithMutableElementTest {
2
3    public static void main(String[] args) throws Exception {
4
5        final Bar bar = new Bar(1);
6
7        final Map<Bar, String> map = new HashMap<>();
8        map.put(bar, "one");
9        HashMapDebugUtils.printMap(map); // bucket [1]: 1 個 entry
10
11        System.out.println(map.containsKey(new Bar(1))); // true
12
13        bar.setVal(2);
14        HashMapDebugUtils.printMap(map); // bucket [1]: 1 個 entry
15
16        System.out.println(map.containsKey(new Bar(1))); // false
17        System.out.println(map.containsKey(new Bar(2))); // false
18
19        map.put(new Bar(2), "two");
20        HashMapDebugUtils.printMap(map); // bucket [1]: 1 個 entry | [2]: 1 個 entry
21
22        System.out.println(map.remove(new Bar(1))); // null
23        System.out.println(map.remove(new Bar(2))); // two
24        HashMapDebugUtils.printMap(map); // bucket [1]: 1 個 entry
25
26        final Map<Bar, String> newMap = new HashMap<>(map);
27        HashMapDebugUtils.printMap(newMap); // bucket [0]: 1 個 entry
28        System.out.println(newMap.containsKey(new Bar(2))); // true
29
30        System.out.println(newMap.remove(new Bar(2))); // one
31        HashMapDebugUtils.printMap(newMap); // bucket [0]: 1 個 entry
32    }
33}

• 我地既 HashMap 會用 mutable 既 Bar class 作為 key type。
  • Bar#hashCode 會返回 int type 既 val field value。
  • Bar#equals 會用 val field value 黎比較 object equality。
• 測試流程（Oracle JDK 8）
  1. 將 key 係 val: 1、value 係 one 既 entry 放入 HashMap。
     1. Hash 係 1，所以會放入 bucket 1。
     2. 可以見到 bucket 1 有 1 個 entry。
  2. 用 HashMap#containsKey 測試下 val: 1 既 key 係咪存在喺 HashMap 裡面。
     1. Hash 係 1，所以會喺 bucket 1 裡面搵。
     2. Bucket 1 既 linked list 只有 1 個 element，而對呢個 element 既 Bar#equals 返回 true（val 1 等於 1）。
     3. 結果係存在。
  3. 將呢個 Bar object 既 val 改成 2。
  4. 用 HashMap#containsKey 測試下 val: 1 既 key 係咪存在喺 HashMap 裡面。
     1. Hash 係 1，所以會喺 bucket 1 裡面搵。
     2. Bucket 1 既 linked list 只有 1 個 element，但係對呢個 element 既 Bar#equals 返回 false（val 1 唔等於 2）。
     3. 結果係唔存在。
  5. 用 HashMap#containsKey 測試下 val: 2 既 key 係咪存在喺 HashMap 裡面。
     1. Hash 係 2，所以會喺 bucket 2 裡面搵。
     2. Bucket 2 係空既。
     3. 結果係唔存在。
  6. 將 key 係 val: 2、value 係 two 既 entry 放入 HashMap。
     1. Hash 係 2，所以會放入 bucket 2。
     2. 可以見到 bucket 1 以及 bucket 2 各有 1 個 entry。
  7. 用 HashMap#remove 測試下刪除 key 係 val: 1 既 entry。
     1. Hash 係 1，所以會喺 bucket 1 裡面搵。
     2. Bucket 1 既 linked list 只有 1 個 element，但係對呢個 element 既 Bar#equals 返回 false（val 1 唔等於 2）。
     3. 冇刪除到 entry，所以返回 null。
  8. 用 HashMap#remove 測試下刪除 key 係 val: 2 既 entry。
     1. Hash 係 2，所以會喺 bucket 2 裡面搵。
     2. Bucket 2 既 linked list 只有 1 個 element，而對呢個 element 既 Bar#equals 返回 true（val 2 等於 2）。
     3. 因為刪除左 entry，所以返回 entry 既 value two。
     4. 可以見到 bucket 1 有 1 個 entry，而 bucket 2 就再冇 entry。
  9. 用 new HashMap<>(Map<? extends K,? extends V> m) constructor 重新建立一個 HashMap，argument 用上述既 HashMap。
     1. 可以見到只有 2 個 buckets——Bucket 0 有 1 個 entry，而 bucket 1 就冇 entry。
  10. 用 HashMap#containsKey 測試下 val: 2 既 key 係咪存在喺新既 HashMap 裡面。
      1. Hash 係 2，所以會喺 bucket 0 裡面搵。
      2. Bucket 0 既 linked list 只有 1 個 element，而對呢個 element 既 Bar#equals 返回 true（val 2 等於 2）。
      3. 結果係存在。

1public class HashSetWithMutableElementTest {
2
3    public static void main(String[] args) throws Exception {
4
5        final Bar bar = new Bar(1);
6
7        final Set<Bar> set = new HashSet<>();
8        set.add(bar);
9
10        System.out.println(set.contains(new Bar(1))); // true
11
12        bar.setVal(2);
13
14        System.out.println(set.contains(new Bar(1))); // false
15        System.out.println(set.contains(new Bar(2))); // false
16
17        set.add(new Bar(2));
18
19        System.out.println(set.remove(new Bar(1))); // false
20        System.out.println(set.remove(new Bar(2))); // true
21
22        final Set<Bar> newMap = new HashSet<>(set);
23        System.out.println(newMap.contains(new Bar(2))); // true
24        System.out.println(newMap.remove(new Bar(2))); // true
25    }
26}

• HashMap - JDK 7 vs JDK 8
• JDK 1.8 中 HashMap 的 resize 優化
• 深入理解 HashMap（四）：關鍵源碼逐行分析之 resize 擴容
• 你給 HashMap 初始化了容量，卻讓性能變加更糟？
• StackOverflow - Explanation of HashMap#hash(int) method
• OpenJDK 7 - HashMap.java source code
• OpenJDK 8 - HashMap.java source code
• OpenJDK 8 - HashSet.java source code