HashTable源碼閱讀

本文基于JDK1.8 >讀完本文預計需要15分鐘

摘要

想必HashTable大家都不會陌生（雖然現在不推薦用它了，推薦ConCurrentHashMap），但我們說起HashMap很自然的就會想到HashTable，也經常拿它兩做對比。

大部分人想到的第一點就是：HashMap線程不安全，HashTable線程安全！看源碼會發現HashTable的所有方法都是synchronized修飾，看到這個我們就知道原因了。我們先來看一遍HashTable的源碼，它兩的源碼對比着看，效果更佳。我們篇幅按一樣的順序寫便于對比觀看。HashMap源碼閱讀

首先我們了解到 HashMap繼承自AbstractMap實作的是Map接口，而HashTable繼承自Dictionary實作的是Map接口。不幸的是Dictionary已經被棄用。

主要的不同點：
- 線程安全： HashMap線程不安全 <--> HashTable線程安全
- 實作方式： HashMap用數組+連結清單+紅黑樹 <--> HashTable用數組+連結清單
- 預設初始容量： HashMap是16 <--> HashTable是11
- key是否可為null: HashMap可以允許存在一個為null的key和任意個為null的value <--> HashTable中的key和value都不允許為null

關鍵變量：

//内部存放的鍵值對數組
    private transient Entry<?,?>[] table;

    //存放的鍵值對的數量
    private transient int count;

    //擴容的門檻值
    private int threshold;

    //加載因子
    private float loadFactor;

四個構造方法：

//構造方法1
    //用指定的初始容量，加載因子搞一個空的hash表
    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);
    }

    //構造方法2
    //用指定的初始容量與預設的加載因子0.75搞一個空的hash表
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    //構造方法3
    //空參構造 預設使用這個 預設初始容量11（HashMap是16），加載因子0.75調用構造方法1搞一個新的hash表
    public Hashtable() {
        this(11, 0.75f);
    }

    //構造方法4
    //傳入一個map搞一個與此map具用相同映射的新hash表
    public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }

對四個構造方法簡單總結一下,與HashMap看起來十分相似啊，但有所差別：

構造函數并不像HashMap用的是一種懶加載的方式（用到的時候才去初始化），而是咔，一上來就給你先整一個新的空Hash表在那放着。
預設初始容量：HashMap是16，HashTable是11。

主要方法

hashtable->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;
        }

我們拎出來containsKey()方法舉例說明：

HashTable中沒有像HashMap一樣搞一個專門的hash()方法，它直接調用了Object提供的本地方法hashCode();

int hash = key.hashCode()，在HashTable中都是以這種方式擷取hashCode

hashtable->put()

以下是源代碼（帶注釋）：

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

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        //按位與左右保證得到整數 再取模避免超過長度
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        //如果存在相同的key則周遊連結清單把那個key對應的value換成新的value
        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);
        //把表中容量加1
        count++;
    }

那麼我們來總結一下put方法：

對value判空，hashtable不允許key、value為空
根據key的hashCode值找到對應的索引
如果存在相同的key則周遊連結清單把那個key對應的value換成新的value
判斷表中鍵值對數量是否大于門檻值

是，調用rehash()方法擴容
直接把鍵值對插到哈希槽（連結清單第一位）

hashtable->get()

public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        //尋址
        int index = (hash & 0x7FFFFFFF) % tab.length;
        //周遊連結清單取出key對應的value
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

那麼我們來總結一下get()方法：

根據key的hashCode值找到對應索引，周遊連結清單取值

hashtable->rehash()

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

        // overflow-conscious code
        //新的初始容量是舊表容量的2倍+1
        int newCapacity = (oldCapacity << 1) + 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;
                e.next = (Entry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }
    }

總結一下rehash()方法：

求出新的容量（舊容量2倍+1）
判斷是否達到最大容量
根據新容量初始化一個新表
求出新的門檻值
把舊表中的資料遷移到新表

我想這會閱讀結束之後應該對HashTable有了一定的認識，希望能在面試或者工作中幫到您！

參考文獻

JDK1.7&JDK1.8 源碼。
Java Code Geeks，HashMap performance improvements in Java 8，2014。
部落格園，Java 集合系列10之 HashMap詳細介紹(源碼解析)和使用示例, 2013。
美團技術團隊 Java 8系列之重新認識HashMap, 2016。

Hongchen閑談

放一張去年的照片【忽略腿毛】，這是我去打羽毛球随手拍的一張照片，當時是出門去球館。我高中時期常打，但是上大學這個羽毛球就荒廢了，來北京之後就沒個運動愛好了。

恰好，我看合租的室友天天拎個拍擱客廳晃悠。于是，我讓他拉上我，準備重新給撿起來玩一玩，還是得把這身體鍛煉好了，否則，怎麼扛得住996呢【狗頭】。

稍作思考，還是需要發展一下自己的體育愛好，畢竟運動之後的快感還是有的。怕自己長時間躺着刷抖音之後的精神空洞【狗頭】。

HashTable源碼閱讀

摘要

關鍵變量：

四個構造方法：

主要方法

hashtable->hashCode()

hashtable->put()

hashtable->get()

hashtable->rehash()

參考文獻

Hongchen閑談

感謝閱讀

繼續閱讀

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