Java 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%newCapacity
。hash&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?ServLet創(chuàng)建一個項目的基本步驟
Servlet是Server Applet的簡稱,是運行在服務(wù)器上的小程序,用于編寫Java的服務(wù)器端程序,它的主要作用是接收并響應(yīng)來自Web客戶端的請求,下面這篇文章主要給大家介紹了關(guān)于JAVA?ServLet創(chuàng)建一個項目的基本步驟,需要的朋友可以參考下2024-03-03JAVA中關(guān)于Long類型返回前端精度丟失問題處理辦法
這篇文章主要介紹了后端JavaBean的id屬性從Long類型改為雪花算法后出現(xiàn)的精度丟失問題,解決方案包括將id字段類型改為字符串或使用Jackson序列化方式,需要的朋友可以參考下2024-11-11jackson在springboot中的使用方式-自定義參數(shù)轉(zhuǎn)換器
這篇文章主要介紹了jackson在springboot中的使用方式-自定義參數(shù)轉(zhuǎn)換器,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-10-10SpringBoot使用?Sleuth?進行分布式跟蹤的過程分析
Spring Boot Sleuth是一個分布式跟蹤解決方案,它可以幫助您在分布式系統(tǒng)中跟蹤請求并分析性能問題,Spring Boot Sleuth是Spring Cloud的一部分,它提供了分布式跟蹤的功能,本文將介紹如何在Spring Boot應(yīng)用程序中使用Sleuth進行分布式跟蹤,感興趣的朋友一起看看吧2023-10-10Java Swing實現(xiàn)餐廳點餐系統(tǒng)源碼(收藏版)
這篇文章主要介紹了Java Swing實現(xiàn)餐廳點餐系統(tǒng)源碼,本文給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-02-02