和 HashMap 一樣,Hashtable 也是一個(gè)散列表,它存儲的內(nèi)容是鍵值對。
Hashtable 在 Java 中的定義為:
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable{}
從源碼中,我們可以看出,Hashtable 繼承于 Dictionary 類,實(shí)現(xiàn)了 Map, Cloneable, java.io.Serializable接口。其中Dictionary類是任何可將鍵映射到相應(yīng)值的類(如 Hashtable)的抽象父類,每個(gè)鍵和值都是對象(源碼注釋為:The Dictionary
class is the abstract parent of any class, such as Hashtable
, which maps keys to values. Every key and every value is an object.)。但在這一點(diǎn)我開始有點(diǎn)懷疑,因?yàn)槲也榭戳薍ashMap以及TreeMap的源碼,都沒有繼承于這個(gè)類。不過當(dāng)我看到注釋中的解釋也就明白了,其 Dictionary 源碼注釋是這樣的:NOTE: This class is obsolete. New implementations should implement the Map interface, rather than extending this class. 該話指出 Dictionary 這個(gè)類過時(shí)了,新的實(shí)現(xiàn)類應(yīng)該實(shí)現(xiàn)Map接口。
Hashtable是通過"拉鏈法"實(shí)現(xiàn)的哈希表。它包括幾個(gè)重要的成員變量:table, count, threshold, loadFactor, modCount。
關(guān)于變量的解釋在源碼注釋中都有,最好還是應(yīng)該看英文注釋。
/**
* The hash table data.
*/
private transient Entry<K,V>[] table;
/**
* The total number of entries in the hash table.
*/
private transient int count;
/**
* The table is rehashed when its size exceeds this threshold. (The
* value of this field is (int)(capacity * loadFactor).)
*
* @serial
*/
private int threshold;
/**
* The load factor for the hashtable.
*
* @serial
*/
private float loadFactor;
/**
* The number of times this Hashtable has been structurally modified
* Structural modifications are those that change the number of entries in
* the Hashtable or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the Hashtable fail-fast. (See ConcurrentModificationException).
*/
private transient int modCount = 0;
Hashtable 一共提供了 4 個(gè)構(gòu)造方法:
public Hashtable(int initialCapacity, float loadFactor)
: 用指定初始容量和指定加載因子構(gòu)造一個(gè)新的空哈希表。useAltHashing 為 boolean,其如果為真,則執(zhí)行另一散列的字符串鍵,以減少由于弱哈希計(jì)算導(dǎo)致的哈希沖突的發(fā)生。public Hashtable(int initialCapacity)
:用指定初始容量和默認(rèn)的加載因子 (0.75) 構(gòu)造一個(gè)新的空哈希表。public Hashtable()
:默認(rèn)構(gòu)造函數(shù),容量為 11,加載因子為 0.75。public Hashtable(Map<? extends K, ? extends V> t)
:構(gòu)造一個(gè)與給定的 Map 具有相同映射關(guān)系的新哈希表。/**
* Constructs a new, empty hashtable with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hashtable.
* @param loadFactor the load factor of the hashtable.
* @exception IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive.
*/
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
useAltHashing = sun.misc.VM.isBooted() &&
(initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
}
/**
* Constructs a new, empty hashtable with the specified initial capacity
* and default load factor (0.75).
*
* @param initialCapacity the initial capacity of the hashtable.
* @exception IllegalArgumentException if the initial capacity is less
* than zero.
*/
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
/**
* Constructs a new, empty hashtable with a default initial capacity (11)
* and load factor (0.75).
*/
public Hashtable() {
this(11, 0.75f);
}
/**
* Constructs a new hashtable with the same mappings as the given
* Map. The hashtable is created with an initial capacity sufficient to
* hold the mappings in the given Map and a default load factor (0.75).
*
* @param t the map whose mappings are to be placed in this map.
* @throws NullPointerException if the specified map is null.
* @since 1.2
*/
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
put 方法的整個(gè)流程為:
我在下面的代碼中也進(jìn)行了一些注釋:
public synchronized V put(K key, V value) {
// Make sure the value is not null確保value不為null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
//確保key不在hashtable中
//首先,通過hash方法計(jì)算key的哈希值,并計(jì)算得出index值,確定其在table[]中的位置
//其次,迭代index索引位置的鏈表,如果該位置處的鏈表存在相同的key,則替換value,返回舊的value
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
//如果超過閥值,就進(jìn)行rehash操作
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
//將值插入,返回的為null
Entry<K,V> e = tab[index];
// 創(chuàng)建新的Entry節(jié)點(diǎn),并將新的Entry插入Hashtable的index位置,并設(shè)置e為新的Entry的下一個(gè)元素
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}
通過一個(gè)實(shí)際的例子來演示一下這個(gè)過程:
假設(shè)我們現(xiàn)在Hashtable的容量為5,已經(jīng)存在了(5,5),(13,13),(16,16),(17,17),(21,21)這 5 個(gè)鍵值對,目前他們在Hashtable中的位置如下:
http://wiki.jikexueyuan.com/project/java-collection/images/hashtable1.png" alt="圖1" />
現(xiàn)在,我們插入一個(gè)新的鍵值對,put(16,22),假設(shè)key=16的索引為1.但現(xiàn)在索引1的位置有兩個(gè)Entry了,所以程序會對鏈表進(jìn)行迭代。迭代的過程中,發(fā)現(xiàn)其中有一個(gè)Entry的key和我們要插入的鍵值對的key相同,所以現(xiàn)在會做的工作就是將newValue=22替換oldValue=16,然后返回oldValue=16.
http://wiki.jikexueyuan.com/project/java-collection/images/hashtable2.png" alt="圖2" />
然后我們現(xiàn)在再插入一個(gè),put(33,33),key=33的索引為3,并且在鏈表中也不存在key=33的Entry,所以將該節(jié)點(diǎn)插入鏈表的第一個(gè)位置。
http://wiki.jikexueyuan.com/project/java-collection/images/hashtable3.png" alt="圖3" />
相比較于 put 方法,get 方法則簡單很多。其過程就是首先通過 hash()方法求得 key 的哈希值,然后根據(jù) hash 值得到 index 索引(上述兩步所用的算法與 put 方法都相同)。然后迭代鏈表,返回匹配的 key 的對應(yīng)的 value;找不到則返回 null。
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}
Hashtable 有多種遍歷方式:
//1、使用keys()
Enumeration<String> en1 = table.keys();
while(en1.hasMoreElements()) {
en1.nextElement();
}
//2、使用elements()
Enumeration<String> en2 = table.elements();
while(en2.hasMoreElements()) {
en2.nextElement();
}
//3、使用keySet()
Iterator<String> it1 = table.keySet().iterator();
while(it1.hasNext()) {
it1.next();
}
//4、使用entrySet()
Iterator<Entry<String, String>> it2 = table.entrySet().iterator();
while(it2.hasNext()) {
it2.next();
}