HashTable詳解

概論

HashTable是遺留類，很多映射的常用功能與HashMap類似，不同的是它承自Dictionary類，并且是線程安全的，并發(fā)性不如ConcurrentHashMap，因?yàn)镃oncurrentHashMap引入了分段鎖。

Hashtable不建議在新代碼中使用，不需要線程安全的場合可以用HashMap替換，需要線程安全的場合可以用ConcurrentHashMap替換。

對比HashMap 的初始容量

默認(rèn)11 的初始容量

需要注意的是Hashtable的默認(rèn)初始容量大小是11，而HashMap 是16,但是他們的加載因子都是0.75f

  1.     /**
  2.      * Constructs a new, empty hashtable with a default initial capacity (11)
  3.      * and load factor (0.75).
  4.      */
  5.     public Hashtable() {
  6.         this(11, 0.75f);
  7.     }

Java

  1. /**
  2.  * Constructs an empty <tt>HashMap</tt> with the default initial capacity
  3.  * (16) and the default load factor (0.75).
  4.  */
  5. public HashMap() {
  6.     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  7. }

Java

任意指定非負(fù)的容量

還有一點(diǎn)就是Hashtable的initialCapacity 也就是初始容量是是可以是你指定的任何非負(fù)整數(shù)，也就是你給它設(shè)置個0 也可以的

  1. public Hashtable(int initialCapacity) {
  2.     this(initialCapacity, 0.75f);
  3. }
  4.  
  5. public Hashtable(int initialCapacity, float loadFactor) {
  6.     if (initialCapacity < 0)
  7.         throw new IllegalArgumentException("Illegal Capacity: "+
  8.                                            initialCapacity);
  9.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
  10.         throw new IllegalArgumentException("Illegal Load: "+loadFactor);
  11.  
  12.     if (initialCapacity==0)
  13.         initialCapacity = 1;
  14.     this.loadFactor = loadFactor;
  15.     table = new Entry<?,?>[initialCapacity];
  16.     threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  17. }

但是你看一下HashMap 的初始容量就不那么聽話了，默認(rèn)情況下，當(dāng)我們設(shè)置HashMap的初始化容量時，實(shí)際上HashMap會采用第一個大于該數(shù)值的2的冪作為初始化容量(0 1 除外)

  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. }

Java

對比HashMap 的 對null 值的支持

HashTable key value 都不支持null

首先HashMap 是支持null 值做key和value 的，但是HashTable 是不支持的，key 也不支持 value 也不支持

  1. public synchronized V put(K key, V value) {
  2.     // Make sure the value is not null
  3.     if (value == null) {
  4.         throw new NullPointerException();
  5.     }
  6.  
  7.     // Makes sure the key is not already in the hashtable.
  8.     Entry<?,?> tab[] = table;
  9.     int hash = key.hashCode();
  10.     int index = (hash & 0x7FFFFFFF) % tab.length;
  11.     @SuppressWarnings("unchecked")
  12.     Entry<K,V> entry = (Entry<K,V>)tab[index];
  13.     for(; entry != null ; entry = entry.next) {
  14.         if ((entry.hash == hash) && entry.key.equals(key)) {
  15.             V old = entry.value;
  16.             entry.value = value;
  17.             return old;
  18.         }
  19.     }
  20.     addEntry(hash, key, value, index);
  21.     return null;
  22. }

Java

聰明的你們發(fā)現(xiàn)了嗎，上面值檢測了value ==null 則拋出NPE 但是沒有說key 啊，因?yàn)槿绻鹝ey 是null 的話，key.hashCode()則會拋出異常，根本不需要判斷，但是value 就不會拋出來

但是需要注意的實(shí)HashMap 對null 值雖然支持，但是可以從hash值的計算方法中看出，<null,value>的鍵值對，value 會覆蓋的。

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

Java

升級HashTable 使其支持null 做value

大部分代碼都是直接copy 的HashTable，只去掉了value 的空值檢測

  1. public class BuerHashTable<K, V> extends Hashtable<K, V> {
  2.         // ..... 省略了部分代碼，直接copy HashTable 的即可，主要是BuerHashTable.Entry 的定義和構(gòu)造方法
  3.     public synchronized V put(K key, V value) {
  4.  
  5.         // Makes sure the key is not already in the hashtable.
  6.         Entry<?,?> tab[] = table;
  7.         int hash = key.hashCode();
  8.         int index = (hash & 0x7FFFFFFF) % tab.length;
  9.         @SuppressWarnings("unchecked")
  10.         Entry<K,V> entry = (Entry<K,V>)tab[index];
  11.         for(; entry != null ; entry = entry.next) {
  12.             if ((entry.hash == hash) && entry.key.equals(key)) {
  13.                 V old = entry.value;
  14.                 entry.value = value;
  15.                 return old;
  16.             }
  17.         }
  18.  
  19.         addEntry(hash, key, value, index);
  20.         return null;
  21.     }
  22.     private void addEntry(int hash, K key, V value, int index) {
  23.         modCount++;
  24.  
  25.         BuerHashTable.Entry<?,?> tab[] = table;
  26.         if (count >= threshold) {
  27.             // Rehash the table if the threshold is exceeded
  28.             rehash();
  29.  
  30.             tab = table;
  31.             hash = key.hashCode();
  32.             index = (hash & 0x7FFFFFFF) % tab.length;
  33.         }
  34.  
  35.         // Creates the new entry.
  36.         @SuppressWarnings("unchecked")
  37.         BuerHashTable.Entry<K,V> e = (BuerHashTable.Entry<K,V>) tab[index];
  38.         tab[index] = new BuerHashTable.Entry<>(hash, key, value, e);
  39.         count++;
  40.     }
  41. }

Java

接下來，就可以將null 值作為value 存入BuerHashTable 了

  1. BuerHashTable<String, String> buerHashTable = new BuerHashTable<>();
  2. buerHashTable.put("a", null);

Java

對比 HashTable 的繼承關(guān)系

Dictionary

這個類是HashTable特有繼承的，HashMap 是沒有繼承的，但是這個抽象類其實(shí)是沒有多大意義的,因?yàn)樗姆椒ǘ荚贛ap接口中有，其實(shí)這個就是個歷史問題了，因?yàn)镸ap接口是在Java1.2 中才加進(jìn)去的，而Dictionary抽象類在Java1.0中就存在了

  1. public abstract
  2. class Dictionary<K,V> {
  3.     public Dictionary() {
  4.     }
  5.     abstract public int size();
  6.     abstract public boolean isEmpty();
  7.     abstract public Enumeration<K> keys();
  8.     abstract public Enumeration<V> elements();
  9.     abstract public V get(Object key);
  10.     /**
  11.      * @exception  NullPointerException  if the <code>key</code> or
  12.      */
  13.     abstract public V put(K key, V value);
  14.     abstract public V remove(Object key);
  15. }






Java

這個地方的NullPointerException 對應(yīng)的就是HashTable 中put 方法中的null 值檢測

最后一點(diǎn)就是Dictionary 抽象類上的注釋，新的實(shí)現(xiàn)應(yīng)該實(shí)現(xiàn)Map 接口而不是該抽象類

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

其實(shí)HashMap更準(zhǔn)確地說是繼承自AbstractMap類，而不是直接實(shí)現(xiàn)了Map 接口，所以要是Dictionary這個抽象類要是實(shí)現(xiàn)的實(shí)Map 接口，那HashMap和Hashtable 就在繼承關(guān)系上保持一致了

Hashtable

線程安全

其實(shí)HashTable 沒有那么多要說的，比較重要的一點(diǎn)就是線程安全，但是這個線程安全的實(shí)現(xiàn)方式就是所有的操作都加了synchronized關(guān)鍵字，哈哈！ 關(guān)于synchronized 我們后面會說

  1. public synchronized int size() {}
  2. public synchronized boolean isEmpty() {}
  3. public synchronized boolean contains(Object value) {}
  4. public synchronized boolean containsKey(Object key) {}
  5. public synchronized V get(Object key) {}
  6. public synchronized V put(K key, V value) {}
  7. public synchronized V remove(Object key) {}

Java

而HashMap 是線程不安全的

contains方法

HashMap中沒有Hashtable中的contains方法，只有containsValue和containsKey，因?yàn)閏ontains方法容易讓人引起誤解。

Hashtable則保留了contains，containsValue和containsKey三個方法，其中contains和containsValue功能相同。

debug 源碼 put 方法

  1. public synchronized V put(K key, V value) {
  2.     // Make sure the value is not null 確保value 不是null
  3.     if (value == null) {
  4.         throw new NullPointerException();
  5.     }
  6.  
  7.     // Makes sure the key is not already in the hashtable.
  8.     // 這里的英文注釋很有意思啊，就是告訴你確保key 不存在，存在咋地，覆蓋又咋地
  9.     Entry<?,?> tab[] = table;
  10.     // 哈希值的計算不同，HashTable直接使用對象的hashCode。而HashMap重新計算hash值(高16位異或低16位)
  11.     int hash = key.hashCode();
  12.     // 計算下標(biāo) HashMap 是計算key的hash再與tab.length-1進(jìn)行與運(yùn)算；
  13.     // HashTable則是key的hash值與0x7FFFFFFF進(jìn)行與運(yùn)算，然后再對tab.length取模
  14.     // 先hash&0x7FFFFFFF后，再對length取模，與0x7FFFFFFF的目的是為了將負(fù)的hash值轉(zhuǎn)化為正值，因?yàn)閔ash值有可能為負(fù)數(shù)，
         而&0x7FFFFFFF后，只有符號外改變，而后面的位都不變
  15.     int index = (hash & 0x7FFFFFFF) % tab.length;
  16.     @SuppressWarnings("unchecked")
  17.     // 確定 index 位置上的鏈表頭，這里主要是遍歷鏈表找到key 值相等的節(jié)點(diǎn)，然后返回old value，這樣的話就不用添加新值
  18.     // 也就是不用調(diào)用addEntry 方法
  19.     Entry<K,V> entry = (Entry<K,V>)tab[index];
  20.     // 存在key 
  21.     for(; entry != null ; entry = entry.next) {
  22.         if ((entry.hash == hash) && entry.key.equals(key)) {
  23.             V old = entry.value;
  24.             entry.value = value;
  25.             return old;
  26.         }
  27.     }
  28.     // 鏈表中不存在，則添加新值
  29.     addEntry(hash, key, value, index);
  30.     // 返回null 
  31.     return null;
  32. }

Java

  1. private void addEntry(int hash, K key, V value, int index) {
  2.     modCount++;
  3.     Entry<?,?> tab[] = table;
  4.     // 判斷是否要擴(kuò)容
  5.     if (count >= threshold) {
  6.         // Rehash the table if the threshold is exceeded
  7.         rehash();
  8.         tab = table;
  9.         hash = key.hashCode();
  10.         index = (hash & 0x7FFFFFFF) % tab.length;
  11.     }
  12.     // Creates the new entry.
  13.     @SuppressWarnings("unchecked")
  14.     Entry<K,V> e = (Entry<K,V>) tab[index];
  15.     // e 也就是  tab[index] 是這個鏈表的頭結(jié)點(diǎn)， tab[index] = new Entry<>(hash, key, value, e); 也就是將元素添加到鏈表
         的頭部，e 做為new Entry<>(hash,key, value, e)的next 節(jié)點(diǎn)
  16.     tab[index] = new Entry<>(hash, key, value, e);
  17.     count++;
  18. }

Java

這里我們對比一下HashMap 的添加方法,很明顯別人都是添加的鏈表尾部的，因?yàn)镠ashTable 是線程安全的，在這個前提下，使用頭查法性能更好，否則還有遍歷到鏈表的尾部插入

  1. for (int binCount = 0; ; ++binCount) {
  2.     if ((e = p.next) == null) {
  3.         p.next = newNode(hash, key, value, null);
  4.         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  5.             treeifyBin(tab, hash);
  6.         break;
  7.     }
  8.     if (e.hash == hash &&
  9.         ((k = e.key) == key || (key != null && key.equals(k))))
  10.         break;
  11.     p = e;
  12. }

Java

最后我們再看一下擴(kuò)容的方法

  1. @SuppressWarnings("unchecked")
  2. protected void rehash() {
  3.     int oldCapacity = table.length;
  4.     Entry<?,?>[] oldMap = table;
  5.  
  6.     // overflow-conscious code 
  7.     // 擴(kuò)容成2倍+1
  8.     int newCapacity = (oldCapacity << 1) + 1;
  9.     // 這里判斷是否超出了容量限制
  10.     if (newCapacity - MAX_ARRAY_SIZE > 0) {
  11.         if (oldCapacity == MAX_ARRAY_SIZE)
  12.             // Keep running with MAX_ARRAY_SIZE buckets
  13.             return;
  14.         // 最大容量 MAX_ARRAY_SIZE    
  15.         newCapacity = MAX_ARRAY_SIZE;
  16.     }
  17.     // 創(chuàng)建新的數(shù)組
  18.     Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
  19.     modCount++;
  20.     // 更新 threshold
  21.     threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  22.     table = newMap;
  23.     // 數(shù)據(jù)遷移，遍歷數(shù)組
  24.     for (int i = oldCapacity ; i-- > 0 ;) {
  25.             // for 循環(huán)的方式遍歷鏈表
  26.         for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
  27.             Entry<K,V> e = old;
  28.             old = old.next;
  29.             int index = (e.hash & 0x7FFFFFFF) % newCapacity;
  30.             e.next = (Entry<K,V>)newMap[index];
  31.             newMap[index] = e;
  32.         }
  33.     }
  34. }

Java

總結(jié)

  1. 需要注意的是Hashtable的默認(rèn)初始容量大小是11，而HashMap 是16,但是他們的加載因子都是0.75f
  2. HashTable的初始容量可以使任何非負(fù)整數(shù)，但是HashMap會采用第一個大于該數(shù)值的2的冪作為初始化容量(0 1 除外，都是 1)
  3. HashTable的線程安全是完全借助synchronized 的加持
  4. HashTable 的元素是頭插法，也就是插入到鏈表的頭部，因?yàn)镠ashTable 是線程安全的，在這個前提下，使用頭查法性能更好，否則還有遍歷到鏈表的尾部插入
  5. HashTable 是沒有紅黑樹支持的，就是不論鏈表的長度有多長，都不會轉(zhuǎn)化成紅黑樹
  6. 哈希值的計算不同，HashTable直接使用對象的hashCode。而HashMap重新計算hash值(高16位異或低16位)，并且HashMap 支持key 為null 就是在這里的
  7. Hashtable擴(kuò)容時，將容量變?yōu)樵瓉淼?倍加1，而HashMap擴(kuò)容時，將容量變?yōu)樵瓉淼?倍。

你覺得HashTable 還有什么可以改進(jìn)的地方嗎，歡迎討論

和上一節(jié)一樣這里我依然給出這個思考題，雖然我們的說法可能不對，可能我們永遠(yuǎn)也站不到源代碼作者當(dāng)年的高度，但是我們依然積極思考，大膽討論

雖然java 源代碼的山很高，如果你想跨越，至少你得有登山的勇氣，這里我給出自己的一點(diǎn)點(diǎn)愚見，希望各位不吝指教

  1. int hash = key.hashCode();
  2. addEntry(hash, key, value, index);
  3. private void addEntry(int hash, K key, V value, int index) {
  4.         // 記錄修改，快速失敗
  5.     modCount++;
  6.     Entry<?,?> tab[] = table;
  7.     // count 實(shí)際存儲的key-value 數(shù)目，在HashMap 中用size 表示
  8.     if (count >= threshold) {
  9.         // Rehash the table if the threshold is exceeded
  10.         rehash();
  11.         tab = table;
  12.         // 咋地，數(shù)組擴(kuò)容之后key 的hash值會變嗎，你還有重新計算一下
  13.         hash = key.hashCode();
  14.         index = (hash & 0x7FFFFFFF) % tab.length;
  15.     }
  16.     // Creates the new entry.
  17.     @SuppressWarnings("unchecked")
  18.     Entry<K,V> e = (Entry<K,V>) tab[index];
  19.     tab[index] = new Entry<>(hash, key, value, e);
  20.     count++;
  21. }

Java

當(dāng)然這只是小問題，但是也有很多其他小問題，例如求index 時候的計算方式是直接取模，而不是用與運(yùn)算，它最大的問題在設(shè)計上，例如hash值的計算方式就沒有HashMap 設(shè)計的好，還有就是沒有紅黑樹的支持，還有就是線程安全的實(shí)現(xiàn)方式也不高效，所以我們說它好像是遺留類,HashTable 在Java1.0 時代就存在了，而HashMap才是Java1.2才有的

 

 作者：柯廣的網(wǎng)絡(luò)日志

微信公眾號：Java大數(shù)據(jù)與數(shù)據(jù)倉庫