摘要：簡介聲明文章均為本人技術筆記，轉載請注明出處聲明和一樣也是散列表，存儲元素也是鍵值對繼承于類類聲明了操作鍵值對的接口方法，實現接口定義鍵值對接口大部分類用修飾，證明是線程安全的基本數據結構鍵值對數組，每個本質上是一個單向鏈表的表頭閾值裝填因
Hashtable簡介
聲明
文章均為本人技術筆記，轉載請注明出處https://segmentfault.com/u/yzwall
Hashtable聲明
public class Hashtable extends Dictionary implements Map, Cloneable, java.io.Serializable
Hashtable和HashMap一樣也是散列表，存儲元素也是鍵值對；
Hashtable繼承于Dictionary類（Dictionary類聲明了操作鍵值對的接口方法），實現Map接口（定義鍵值對接口）；
Hashtable大部分類用synchronized修飾，證明Hashtable是線程安全的；
Hashtable基本數據結構
private transient Entry[] table：鍵值對/Entry數組，每個Entry本質上是一個單向鏈表的表頭
private int threshold：rehash閾值
private float loadFactor：裝填因子
private transient int modCount = 0： Hashtable結構化修改次數，用來實現fail-fast機制；
private transient volatile Set> entrySet：Hastable視圖，鍵值對集合；
private transient volatile Set keySet：Hastable視圖，key集，Hashtable中key不可重復；
private transient volatile Collection values：Hastable視圖，value集合，可重復；
Hashtable中key和value是一對多關系；
鍵值對/Entry
private static class Entry implements Map.Entry {
final int hash;
final K key;
V value;
Entry next;
...
// 計算鍵值對的hashCode
public int hashCode() {
// "^" 按位異或, hash在調用構造器時傳入
return hash ^ Objects.hashCode(value);
}
}
Hash函數
鍵值對
Hashtable方法分析
public synchronized boolean contains(Object value)
public boolean containsValue(Object value)內部調用contains(value);
判斷是否含有該value的鍵值對，在Hashtable中hashCode相同的Entry用鏈表組織，hashCode不同的存儲在Entry數組table中；
// in contains() method.
Entry tab[] = table;
// 查找：遍歷所有Entry鏈表
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;
public synchronized boolean containsKey(Object key)
散列分布策略
int index = (hash & 0x7FFFFFFF) % tab.length;
計算鍵值對的桶位（本質是鍵值對在tab數組中的索引），Hashtable本質上采用除數取余法進行散列分布，模運算效率較低
Hash函數
int hash = key.hashCode() Hashtable直接調用key的hashCode()計算hashCode；
containsKey方法體
Entry tab[] = table;
int hash = key.hashCode();
/**
* 計算index, % tab.length防止數組越界
* index表示key對應entry所在鏈表表頭
*/
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;
public synchronized V get(Object key)：根據指定key查找對應value，查找原理與containsKey相同，查找成功返回value，否則返回null；
public synchronized V put(K key, V value)
設置鍵值對，key和value都不可為null，設置順序:
如果Hashtable含有key，設置(key, oldValue) -> (key, newValue)；
如果Hashtable不含有key, 調用addEntry(...)添加新的鍵值對；
private void addEntry(int hash, K key, V value, int index)
當鍵值對個數超過閾值，先進行rehash然后添加entry，否則直接添加entry；
public synchronized V remove(Object key)
remove操作，計算key所在鏈表表頭table[index]，然后進行單向鏈表的節點刪除操作
public synchronized Object clone()
對Hashtable的淺拷貝操作，淺拷貝所有bucket（單向鏈表組織形式）的表頭；
protected void rehash()
當Hashtable中鍵值對總數超過閾值（容量*裝載因子）后，內部自動調用rehash()增加容量，重新計算每個鍵值對的hashCode;
int newCapacity = (oldCapacity << 1) + 1計算新容量 = 2 * 舊容量 + 1；并且根據新容量更新閾值；
...
for (int i = oldCapacity ; i-- > 0 ;) {
// 拷貝每個Entry鏈表
for (Entry old = (Entry)oldMap[i] ; old != null ; ) {
Entry e = old;
old = old.next;
// 重新計算每個Entry鏈表的表頭索引（rehash）
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
// 開辟鏈表節點
e.next = (Entry)newMap[index];
// 拷貝
newMap[index] = e;
}
}
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66972.html
