Java Hashtable機(jī)制深入了解

更新時(shí)間：2022年09月19日 14:07:21 作者：π大星的日常

HashTable是jdk 1.0中引入的產(chǎn)物，基本上現(xiàn)在很少使用了，但是會(huì)在面試中經(jīng)常被問到。本文就來帶大家一起深入了解一下Hashtable，需要的可以參考一下

概述

HashTable是jdk 1.0中引入的產(chǎn)物，基本上現(xiàn)在很少使用了，但是會(huì)在面試中經(jīng)常被問到，你都知道嗎：

HashTable底層的實(shí)現(xiàn)機(jī)制是什么？
HashTable的擴(kuò)容機(jī)制是什么？
HashTable和HashMap的區(qū)別是什么？

介紹和使用

和HashMap一樣，Hashtable也是一個(gè)散列表，它存儲(chǔ)的內(nèi)容是鍵值對(duì)(key-value)映射, 重要特點(diǎn)如下:

存儲(chǔ)key-value鍵值對(duì)格式
是無序的
底層通過數(shù)組+鏈表的方式實(shí)現(xiàn)
通過synchronized關(guān)鍵字實(shí)現(xiàn)線程安全
key、value都不可以為null（為null時(shí)將拋出NullPointerException）

以上是Hashtable的類結(jié)構(gòu)圖：

實(shí)現(xiàn)了Map接口，提供了鍵值對(duì)增刪改查等基礎(chǔ)操作
繼承了Dictionary字典類，Dictionary是聲明了操作"鍵值對(duì)"函數(shù)接口的抽象類。
實(shí)現(xiàn)了Cloneable接口，實(shí)現(xiàn)數(shù)據(jù)的淺拷貝
實(shí)現(xiàn)了Serializable接口，標(biāo)記Hashtable支持序列化

使用案例：

@Test
    public void test() {
        Hashtable<String, String> table=new Hashtable<>();
        Hashtable<String, String> table1=new Hashtable<>(16);
        Hashtable<String, String> table2=new Hashtable<>(16, 0.75f);
        table.put("T1", "1");
        table.put("T2", "2");
        System.out.println(table);
        // 報(bào)空指針異常
        table.put(null, "3");
    }

運(yùn)行結(jié)果：

核心機(jī)制

實(shí)現(xiàn)機(jī)制

和HashMap相似，Hashtable底層采用數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)，根據(jù)key找到數(shù)組對(duì)應(yīng)的桶，相同的key通過鏈表維護(hù)，當(dāng)數(shù)組桶的使用到達(dá)閾值后，會(huì)進(jìn)行動(dòng)態(tài)擴(kuò)容。但是和HashMap不同的是，鏈表不會(huì)轉(zhuǎn)換為紅黑樹。

擴(kuò)容機(jī)制

擴(kuò)容機(jī)制依賴兩個(gè)成員變量，初始容量和加載因子。他們可以通過構(gòu)造函數(shù)設(shè)置。

容量是值哈希表中桶的數(shù)量，初始容量就是哈希表創(chuàng)建時(shí)的容量。當(dāng)容量達(dá)到閾值的時(shí)候，會(huì)進(jìn)行擴(kuò)容操作，每次擴(kuò)容是原來容量的2倍加1，然后重新為hashtable中的每個(gè)元素重新分配桶的位置。

那閾值是多少呢，Hashtable的閾值，用于判斷是否需要調(diào)整Hashtable的容量，等于"Hashtable當(dāng)前的容量*加載因子"。

通常，默認(rèn)加載因子是 0.75, 這是在時(shí)間和空間成本上尋求一種折衷。加載因子過高雖然減少了空間開銷，但同時(shí)也增加了查找某個(gè)條目的時(shí)間。

源碼解析

成員變量

// 內(nèi)部采用Entry數(shù)組存儲(chǔ)鍵值對(duì)數(shù)據(jù)，Entry實(shí)際為單向鏈表的表頭
private transient Entry<?,?>[] table;
// HashTable里鍵值對(duì)個(gè)數(shù)
private transient int count;
// 擴(kuò)容閾值，當(dāng)超過這個(gè)值時(shí)，進(jìn)行擴(kuò)容操作，計(jì)算方式為：數(shù)組容量*加載因子
private int threshold;
// 加載因子
private float loadFactor;
// 修改次數(shù)，用于快速失敗機(jī)制
private transient int modCount = 0;

Entry的數(shù)據(jù)結(jié)構(gòu)如下：

private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;
    protected Entry(int hash, K key, V value, Entry<K,V> next) {
        this.hash = hash;
        this.key =  key;
        this.value = value;
        this.next = next;
    }
    ......
}

Entry是單向鏈表節(jié)點(diǎn)，next指向下一個(gè)entry

構(gòu)造函數(shù)

// 設(shè)置指定容量和加載因子，初始化HashTable
public Hashtable(int initialCapacity, float loadFactor) {
    // 非法參數(shù)校驗(yàn)
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                          initialCapacity);
    // 非法參數(shù)校驗(yàn)
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    if (initialCapacity==0)
        // 容量最小為1
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    // 初始化數(shù)組
    table = new Entry<?,?>[initialCapacity];
    // 初始擴(kuò)容閾值
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
// 設(shè)置指定容量初始HashTable，加載因子為0.75
public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}
// 手動(dòng)指定數(shù)組初始容量為11，加載因子為0.75
public Hashtable() {
    this(11, 0.75f);
}

put方法

// 方法synchronized修飾，線程安全
public synchronized V put(K key, V value) {
    // 如果value為空，直接空指針
    if (value == null) {
        throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    // 得到key的哈希值
    int hash = key.hashCode();
    // 得到該key存在到數(shù)組中的下標(biāo)
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    // 得到該下標(biāo)對(duì)應(yīng)的Entry
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // 如果該下標(biāo)的Entry不為null，則進(jìn)行鏈表遍歷
    for(; entry != null ; entry = entry.next) {
        // 遍歷鏈表，如果存在key相等的節(jié)點(diǎn)，則替換這個(gè)節(jié)點(diǎn)的值，并返回舊值
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    // 如果數(shù)組下標(biāo)對(duì)應(yīng)的節(jié)點(diǎn)為空，或者遍歷鏈表后發(fā)現(xiàn)沒有和該key相等的節(jié)點(diǎn)，則執(zhí)行插入操作
    addEntry(hash, key, value, index);
    return null;
}
private void addEntry(int hash, K key, V value, int index) {
    // 修改次數(shù)+1
    modCount++;
    Entry<?,?> tab[] = table;
    // 判斷是否需要擴(kuò)容
    if (count >= threshold) {
        // 如果count大于等于擴(kuò)容閾值，則進(jìn)行擴(kuò)容
        rehash();
        tab = table;
        // 擴(kuò)容后，重新計(jì)算該key在擴(kuò)容后table里的下標(biāo)
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }
    // Creates the new entry.
    @SuppressWarnings("unchecked")
    // 采用頭插的方式插入，index位置的節(jié)點(diǎn)為新節(jié)點(diǎn)的next節(jié)點(diǎn)
    // 新節(jié)點(diǎn)取代inde位置節(jié)點(diǎn)
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    // count+1
    count++;
}

擴(kuò)容rehash源碼如下：

protected void rehash() {
    // 暫存舊的table和容量
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;
    // 新容量為舊容量的2n+1倍
    int newCapacity = (oldCapacity << 1) + 1;
    // 判斷新容量是否超過最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        // 如果舊容量已經(jīng)是最大容量大話，就不擴(kuò)容了
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        // 新容量最大值只能是MAX_ARRAY_SIZE
        newCapacity = MAX_ARRAY_SIZE;
    }
    // 用新容量創(chuàng)建一個(gè)新Entry數(shù)組
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    // 模數(shù)+1
    modCount++;
    // 重新計(jì)算下次擴(kuò)容閾值
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    // 將新Entry數(shù)組賦值給table
    table = newMap;
    // 遍歷數(shù)組和鏈表，進(jìn)行新table賦值操作
    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()方法中我們可以看到容量擴(kuò)大兩倍+1，同時(shí)需要將原來HashTable中的元素，重新計(jì)算索引位置一一復(fù)制到新的Hashtable中，這個(gè)過程是比較消耗時(shí)間的。
Hashtable的索引求值公式是： hash&0x7FFFFFFF%newCapacity。hash&0x7FFFFFF是為了保證正數(shù)，因?yàn)閔ashCode的值有可能為負(fù)值。

get方法

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    // 獲取key對(duì)應(yīng)的index
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    // 遍歷鏈表，如果找到key相等的節(jié)點(diǎn)，則改變前繼和后繼節(jié)點(diǎn)的關(guān)系，并刪除相應(yīng)引用，讓GC回收
    Entry<K,V> e = (Entry<K,V>)tab[index];
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
            if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}

remove方法

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    // 獲取key對(duì)應(yīng)的index
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    // 遍歷鏈表，如果找到key相等的節(jié)點(diǎn)，則改變前繼和后繼節(jié)點(diǎn)的關(guān)系，并刪除相應(yīng)引用，讓GC回收
    Entry<K,V> e = (Entry<K,V>)tab[index];
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
            if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}

總結(jié)

本文主要講解了Hashtable的基本功能和源碼解析，雖然Hashtable本身不常用了，但是它的直接子類Properties目前還在被大量使用當(dāng)中，所以學(xué)習(xí)它還是有一定價(jià)值的。下面在總結(jié)下Hashtable和HashMap的區(qū)別：

線程是否安全：HashMap是線程不安全的，HashTable是線程安全的；HashTable內(nèi)部的方法基本都經(jīng)過 synchronized修飾; 如果想要線程安全的Map容器建議使用ConcurrentHashMap,性能更好。
對(duì)Null key 和Null value的支持：HashMap中，null可以作為鍵，這樣的鍵只有一個(gè)，可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為null；HashTable中key和value都不能為null，否則拋出空指針異常；

初始容量大小和每次擴(kuò)充容量大小的不同：

創(chuàng)建時(shí)如果不指定容量初始值，Hashtable默認(rèn)的初始大小為11，之后每次擴(kuò)容，容量變?yōu)樵瓉淼?n+1。HashMap默認(rèn)的初始化大小為16。之后每次擴(kuò)充，容量變?yōu)樵瓉淼?倍；
創(chuàng)建時(shí)如果給定了容量初始值，那么Hashtable會(huì)直接使用你給定的大小，而HashMap會(huì)將其擴(kuò)充為2的冪次方大小。

底層數(shù)據(jù)結(jié)構(gòu)：JDK1.8及以后的HashMap在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長度大于閾值（默認(rèn)為 8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時(shí)間，Hashtable沒有這樣的機(jī)制。

到此這篇關(guān)于Java Hashtable機(jī)制深入了解的文章就介紹到這了,更多相關(guān)Java Hashtable內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: