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