更多 Java 集合類方面的文章，請(qǐng)參見文集《Java 集合類》

Java 集合

• Java 集合實(shí)際上是多個(gè) 引用變量 組成的集合，這些引用變量指向?qū)嶋H的對(duì)象
• 并不會(huì)真正地將對(duì)象放入集合中

Map.Entry

• 為 Map 中的元素，表示為 key - value pair

  interface Entry<K,V>
  

Bucket

A bucket is used to store key - value pairs.
In hash map, bucket use simple linked list to store object. (與 java.util.LinkedList 不同，it is a separate and simple implementation just for map)

對(duì)象中的兩個(gè)方法：

• equals() - 返回 boolean
  • 自反
  • 對(duì)稱
  • 傳遞
• hashCode() - 返回 int
  • 若兩個(gè)對(duì)象通過 equals() 判斷相等，則 hash code 肯定相等
  • 反之不一定

HashMap 的實(shí)現(xiàn)： 鏈表散列：數(shù)組 + 鏈表

Node<K,V> HashMap 中元素的存儲(chǔ)結(jié)構(gòu)

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

影響 HashMap 性能的兩個(gè)因素：

• initial capacity 即初始 bucket 的數(shù)目

  • DEFAULT_INITIAL_CAPACITY 為 16

• load factor - is the measure of how full the hash table is allowed before its capacity is automatically increased.

  • DEFAULT_LOAD_FACTOR 為 0.75
  • 若超過 load factor，則需要重新 rehash，整個(gè) Map 需要重建
  • load factor 越大：空間利用率高，沖突概率大，鏈表長(zhǎng)，查找效率低
  • load factor 越小：空間利用率低，沖突概率小，鏈表短，查找效率高

Java8 HashMap 插入元素的過程

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

從中可以看出：

• 通過 key 的 hash code 計(jì)算其在數(shù)組中的索引：if ((p = tab[i = (n - 1) & hash]) == null)
  • (n - 1) & hash：確保索引在數(shù)組范圍內(nèi)
  • 為什么不直接用 hash 對(duì) 數(shù)組長(zhǎng)度取模？因?yàn)槌ㄟ\(yùn)算效率低
• 如果數(shù)組中對(duì)應(yīng)的索引位置上已經(jīng)有元素了：
  • 如果該元素的 key 與要添加的 key 相同（通過 equals 方法比較），則不添加，返回已存在元素的 value
  • 否則，將該位置設(shè)為新的 Node，原先的 Node 后移，即設(shè)置為新 Node 的 next，返回
• ++modCount; 標(biāo)明該 HashMap 已被修改

為什么哈希表的容量 n 一定是2的冪

比如2，4，8，16，32

• 若 n 為 2 的冪，則(n - 1) & hash 相當(dāng)于對(duì) n 取模，確保了散列的均勻，同時(shí)提升了效率
• 若 n 為偶數(shù)，(n - 1) 為奇數(shù)，最后一位為 1，&與運(yùn)算后，最有一位可能是 0，也可能是 1
• 若 n 為奇數(shù)，(n - 1) 為偶數(shù)，最后一位為 0，&與運(yùn)算后，最有一位只可能是 0，浪費(fèi)了一半的空間

HashMap VS HashTable

• 繼承方式不同：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

關(guān)于 Dictionary 這個(gè)接口，API 中有如下描述：

NOTE: This class is obsolete. New implementations should implement the Map interface, rather than extending this class.

• 是否線程安全：

  • HashMap 非同步，線程不安全。可以通過 Collections.synchronizedMap(m); 來創(chuàng)建線程安全的 HashMap。
  • Hashtable 同步，線程安全。Hashtable 中的幾乎所有的 public 的方法都是 synchronized 的，而有些方法也是在內(nèi)部通過 synchronized 代碼塊來實(shí)現(xiàn)。

• key 和 value 是否可以為 null：

  • HashMap 中 key 和 value 都可以為 null。因此 get(key) 為 null 并不能代表該 key 不存在，需要使用 containsKey(key) 來判斷。
  • Hashtable 中 key 和 value 都不可以為 null。

• 數(shù)組索引的計(jì)算方式：

  • HashMap：在 key 的 hash code 的基礎(chǔ)上通過 (n - 1) & hash 來計(jì)算數(shù)組的索引
  • Hashtable：直接使用 key 的 hash code 與數(shù)組長(zhǎng)度求余作為數(shù)組的索引 int index = (hash & 0x7FFFFFFF) % tab.length;

• 數(shù)組的初始容量及擴(kuò)容方式

  • HashMap：初始容量為16，擴(kuò)容 2 * old size
  • Hashtable：初始容量為11，擴(kuò)容 2 * old size + 1

幾種 Map 的對(duì)比