欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java Hashtable機制深入了解

 更新時間:2022年09月19日 14:07:21   作者:π大星的日常  
HashTable是jdk 1.0中引入的產(chǎn)物,基本上現(xiàn)在很少使用了,但是會在面試中經(jīng)常被問到。本文就來帶大家一起深入了解一下Hashtable,需要的可以參考一下

概述

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

  • HashTable底層的實現(xiàn)機制是什么?
  • HashTable的擴容機制是什么?
  • HashTable和HashMap的區(qū)別是什么?

介紹和使用

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

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

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

  • 實現(xiàn)了Map接口,提供了鍵值對增刪改查等基礎(chǔ)操作
  • 繼承了Dictionary字典類,Dictionary是聲明了操作"鍵值對"函數(shù)接口的抽象類。
  • 實現(xiàn)了Cloneable接口,實現(xiàn)數(shù)據(jù)的淺拷貝
  • 實現(xiàn)了Serializable接口,標記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);
        // 報空指針異常
        table.put(null, "3");
    }

運行結(jié)果:

核心機制

實現(xiàn)機制

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

擴容機制

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

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

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

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

源碼解析

成員變量

// 內(nèi)部采用Entry數(shù)組存儲鍵值對數(shù)據(jù),Entry實際為單向鏈表的表頭
private transient Entry<?,?>[] table;
// HashTable里鍵值對個數(shù)
private transient int count;
// 擴容閾值,當(dāng)超過這個值時,進行擴容操作,計算方式為:數(shù)組容量*加載因子
private int threshold;
// 加載因子
private float loadFactor;
// 修改次數(shù),用于快速失敗機制
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é)點,next指向下一個entry

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

// 設(shè)置指定容量和加載因子,初始化HashTable
public Hashtable(int initialCapacity, float loadFactor) {
    // 非法參數(shù)校驗
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                          initialCapacity);
    // 非法參數(shù)校驗
    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];
    // 初始擴容閾值
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
// 設(shè)置指定容量初始HashTable,加載因子為0.75
public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}
// 手動指定數(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ù)組中的下標
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    // 得到該下標對應(yīng)的Entry
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // 如果該下標的Entry不為null,則進行鏈表遍歷
    for(; entry != null ; entry = entry.next) {
        // 遍歷鏈表,如果存在key相等的節(jié)點,則替換這個節(jié)點的值,并返回舊值
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    // 如果數(shù)組下標對應(yīng)的節(jié)點為空,或者遍歷鏈表后發(fā)現(xiàn)沒有和該key相等的節(jié)點,則執(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;
    // 判斷是否需要擴容
    if (count >= threshold) {
        // 如果count大于等于擴容閾值,則進行擴容
        rehash();
        tab = table;
        // 擴容后,重新計算該key在擴容后table里的下標
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }
    // Creates the new entry.
    @SuppressWarnings("unchecked")
    // 采用頭插的方式插入,index位置的節(jié)點為新節(jié)點的next節(jié)點
    // 新節(jié)點取代inde位置節(jié)點
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    // count+1
    count++;
}

擴容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)是最大容量大話,就不擴容了
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        // 新容量最大值只能是MAX_ARRAY_SIZE
        newCapacity = MAX_ARRAY_SIZE;
    }
    // 用新容量創(chuàng)建一個新Entry數(shù)組
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    // 模數(shù)+1
    modCount++;
    // 重新計算下次擴容閾值
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    // 將新Entry數(shù)組賦值給table
    table = newMap;
    // 遍歷數(shù)組和鏈表,進行新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()方法中我們可以看到容量擴大兩倍+1,同時需要將原來HashTable中的元素,重新計算索引位置一一復(fù)制到新的Hashtable中,這個過程是比較消耗時間的。
  • Hashtable的索引求值公式是: hash&0x7FFFFFFF%newCapacityhash&0x7FFFFFF是為了保證正數(shù),因為hashCode的值有可能為負值。

get方法

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    // 獲取key對應(yīng)的index
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    // 遍歷鏈表,如果找到key相等的節(jié)點,則改變前繼和后繼節(jié)點的關(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對應(yīng)的index
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    // 遍歷鏈表,如果找到key相等的節(jié)點,則改變前繼和后繼節(jié)點的關(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é)下Hashtable和HashMap的區(qū)別:

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

初始容量大小和每次擴充容量大小的不同:

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

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

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

相關(guān)文章

  • 利用Java對PDF文件進行電子簽章的實戰(zhàn)過程

    利用Java對PDF文件進行電子簽章的實戰(zhàn)過程

    隨著電子賬單、回單、通知、合同的流行,電子文檔的可信度變得非常重要,為防止非法篡改,確保文檔的權(quán)威性,我們可以對PDF進行電子簽章,這篇文章主要給大家介紹了關(guān)于如何利用Java對PDF文件進行電子簽章的相關(guān)資料,需要的朋友可以參考下
    2021-07-07
  • Java線程的停止實現(xiàn)原理詳解

    Java線程的停止實現(xiàn)原理詳解

    這篇文章主要介紹了Java線程的停止實現(xiàn)原理,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)吧
    2023-01-01
  • Mockito如何mock靜態(tài)方法問題

    Mockito如何mock靜態(tài)方法問題

    本文介紹了如何在Mockito 3.4.0版本及以上版本中mock靜態(tài)方法,包括如何在pom文件中添加相關(guān)jar包、如何使用Mockito.mockStatic(Class mockClass)方法以及注意事項等
    2025-02-02
  • Spring MVC 擴展和 SSM 框架整合步驟詳解

    Spring MVC 擴展和 SSM 框架整合步驟詳解

    在前端頁面后后臺交互的過程中,需要一種格式清晰、高效且兩端都可以輕松使用的數(shù)據(jù)格式做交互的媒介,JSON正可以滿足這一需求,下面學(xué)習(xí)使用Spring MVC 框架處理JSON數(shù)據(jù),感興趣的朋友一起看看吧
    2024-08-08
  • JAVA?ServLet創(chuàng)建一個項目的基本步驟

    JAVA?ServLet創(chuàng)建一個項目的基本步驟

    Servlet是Server Applet的簡稱,是運行在服務(wù)器上的小程序,用于編寫Java的服務(wù)器端程序,它的主要作用是接收并響應(yīng)來自Web客戶端的請求,下面這篇文章主要給大家介紹了關(guān)于JAVA?ServLet創(chuàng)建一個項目的基本步驟,需要的朋友可以參考下
    2024-03-03
  • JAVA中關(guān)于Long類型返回前端精度丟失問題處理辦法

    JAVA中關(guān)于Long類型返回前端精度丟失問題處理辦法

    這篇文章主要介紹了后端JavaBean的id屬性從Long類型改為雪花算法后出現(xiàn)的精度丟失問題,解決方案包括將id字段類型改為字符串或使用Jackson序列化方式,需要的朋友可以參考下
    2024-11-11
  • Java優(yōu)雅的關(guān)閉線程池的方法

    Java優(yōu)雅的關(guān)閉線程池的方法

    本文主要介紹了Java如何優(yōu)雅的關(guān)閉線程池,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-06-06
  • jackson在springboot中的使用方式-自定義參數(shù)轉(zhuǎn)換器

    jackson在springboot中的使用方式-自定義參數(shù)轉(zhuǎn)換器

    這篇文章主要介紹了jackson在springboot中的使用方式-自定義參數(shù)轉(zhuǎn)換器,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-10-10
  • SpringBoot使用?Sleuth?進行分布式跟蹤的過程分析

    SpringBoot使用?Sleuth?進行分布式跟蹤的過程分析

    Spring Boot Sleuth是一個分布式跟蹤解決方案,它可以幫助您在分布式系統(tǒng)中跟蹤請求并分析性能問題,Spring Boot Sleuth是Spring Cloud的一部分,它提供了分布式跟蹤的功能,本文將介紹如何在Spring Boot應(yīng)用程序中使用Sleuth進行分布式跟蹤,感興趣的朋友一起看看吧
    2023-10-10
  • Java Swing實現(xiàn)餐廳點餐系統(tǒng)源碼(收藏版)

    Java Swing實現(xiàn)餐廳點餐系統(tǒng)源碼(收藏版)

    這篇文章主要介紹了Java Swing實現(xiàn)餐廳點餐系統(tǒng)源碼,本文給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-02-02

最新評論