Java Hashtable類源碼解析

老生常談的問題——Hashtable和HashMap有什麼差別

大家一般都能說出幾條，比如Hashtable是線程安全的，不支援null作為key和value值等等。那麼，要仔細了解這個問題還是直接從Hashtable的源碼入手。

先列一下我找到的差別：

繼承類不同，Hashtable繼承的是Dictionary這是一個廢棄類，而HashMap繼承的是AbstractMap
産生時間不同，Hashtable自JDK1.0版本就有了，而HashMap是JDK1.2才加入的，同時Hashtable可能因為曆史原因并不是我們習慣的駝峰法命名的
Hashtable比HashMap多提供了elments()方法用于傳回此Hashtable中的value的枚舉
Hashtable既不支援null key也不支援null value
Hashtable的預設大小是11，擴大的邏輯是*2+1，對于給定大小不會做擴充。而HashMap是16，擴大時*2，初始大小會轉換成恰好大于等于的2的指數次幂
Hashtable中的周遊操作是從高位開始的，而HashMap是從低位開始
Hashtable處理沖突元素時插入到連結清單頭部，而HashMap是插入到連結清單尾部
Hashtable的hashcode方法計算所有entry的hashcode總和，HashMap沒有這樣的方法，同時HashMap在計算hash值時會用高位右移16位與低位異或來打散散列值，避免位與操作造成沖突過多
Hashtable每一次定位都要做一次完整的除法取餘數，而HashMap使用的是與數組大小-1的位與計算，效率高很多
Hashtable的方法都加上了synchronized是線程安全的方法，而HashMap不是，是以單線程時前者額外開銷很大。JDK8以後Hashtable也用了modCount來保證在周遊過程中其他線程修改對象的fast-fail機制。但是，即使是多線程環境下，依然應該優先選擇對HashMap進行一些特殊處理而不是用Hashtable，因為所有方法都加上synchronized的程式并發性很差。實際上就我個人經驗而言，在一些特定的具體情況下，比如大規模寫入key值連續資料（出自今年的第四屆阿裡中間件性能挑戰賽複賽題），連結清單法解決沖突性能可能不如開放位址法，即使加上了紅黑樹。是以說對于一些對極緻壓榨性能的情況下，适當的可以抛棄一些通用的集合而嘗試自由發揮造輪子。

首先從最上方的注釋中可以看到Hashtable自JDK1.0版本就有了，而HashMap是JDK1.2才加入的。觀察一下類的聲明，我們可以看到他們繼承的類也是不同的，Hashtable繼承的是Dictionary,Dictionary這個類從注釋上寫着已經是obsolete被廢棄了，是以連帶Hashtable也基本不用了。Hashtable也有元素個數，數組大小，負載因子這些屬性，不用元素個數用的是count不是size。也是使用連結清單法來解決沖突。

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

構造函數可以看出預設大小是11，同時初始大小給定多少初始數組就多大，不會做擴充到2的指數次幂這樣的操作。threshold=initialCapacity*loadFactor這點和HashMap相同。

public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry<?,?>[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

    public Hashtable() {
        this(11, 0.75f);
    }

contains這個方法是從表尾開始向前搜尋的，同時也沒有使用==

來比較

public synchronized boolean contains(Object value) {
        if (value == null) {
            throw new NullPointerException();
        }

        Entry<?,?> tab[] = table;
        for (int i = tab.length ; i-- > 0 ;) {
            for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
                if (e.value.equals(value)) {
                    return true;
                }
            }
        }
        return false;
    }

從containsKey可以看出，Hashtable的index計算邏輯是使用key.hashCode()的後31位然後除以tab.length取餘數。HashMap的那種按位與的操作僅當操作數低位全是1時才等價為取餘操作，也就是2的指數次幂-1才可成立，這樣做計算速度比除法快很多，不過沖突數量會增加，是以加入了一些打散的設計比如hashCode高位與低位異或。

public synchronized boolean containsKey(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return true;
            }
        }
        return false;
    }

擴充方法rehash的擴大方式是舊數組大小*2+1，而HashMap是*2，要重新計算每一個的index是以效率低，同時沖突時将後面的元素插入到前面元素的前一位，是以會改變順序

protected void rehash() {
        int oldCapacity = table.length;
        Entry<?,?>[] oldMap = table;

        // overflow-conscious code
        int newCapacity = (oldCapacity << 1) + 1;//新大小=舊大小*2+1
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];//建立一個新的數組

        modCount++;
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;

        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;//重新計算每一個元素的index
                e.next = (Entry<K,V>)newMap[index];//前後元素有沖突時，後面的元素插入到前面元素的前面
                newMap[index] = e;
            }
        }
    }

對于插入結點同樣要先檢查是否存在key值相同的點，存在則不插入，然後檢查是否需要擴充數組，插入時如果發生沖突，也是将要插入的元素放在連結清單的首位，而putVal方法是放入尾部的。同時，可以看到Hashtable是

不支援null作為key或value值的

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {//value為null直接報錯
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();//若key為null這裡會報錯
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }
    private void addEntry(int hash, K key, V value, int index) {
        modCount++;

        Entry<?,?> tab[] = table;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }

Hashtable的

hashcode方法計算所有entry的hash值總和

public synchronized int hashCode() {
        int h = 0;
        if (count == 0 || loadFactor < 0)
            return h;  // Returns zero

        loadFactor = -loadFactor;  // Mark hashCode computation in progress
        Entry<?,?>[] tab = table;
        for (Entry<?,?> entry : tab) {
            while (entry != null) {
                h += entry.hashCode();
                entry = entry.next;
            }
        }

        loadFactor = -loadFactor;  // Mark hashCode computation complete

        return h;
    }

elements這個方法是Hashtable多出來的，

傳回所有value值的枚舉

public synchronized Enumeration<V> elements() {
        return this.<V>getEnumeration(VALUES);
    }

我們可以注意到，Hashtable的方法都加上了synchronized，他們是線程安全的，但是對于本身是線程安全的情況就會大幅度影響性能，JDK8開始引入modCount來作為fast-fail機制，防止其他線程的非synchronzied方法對Hashtable進行修改。

Java Hashtable類源碼解析

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method