本文基于JDK1.7，HashTable是用同步來實作線程安全的Map，使用Hash算法定位
與
HashMap 類似，HashMap是線程不安全的，單線程下效率更高，多線程下 ConcurrentHashMap 可保證線程安全且效率優于HashTableHashtable 概要
- 與HashMap主要差別是Hashtable的put，get方法都是同步的，線程安全，但是性能較差
- key和value都不能為null，HashMap中key與value都可以為 null
- 與HashMap類似，key必須實作hashCode()和equals方法，由于equals判斷前都會先判斷hashCode方法是否相等，兩個equals的對象的hashCode()必須相同，否則在put等方法中不會覆寫
- 與HashMap類似，capacity和loadFactor是影響其性能的兩個關鍵參數。capacity代表桶的個數，初始化initialcapacity為較大值可以減少擴容（rehash，transfer）開銷，但是初始消耗更多空間，且增大了周遊時間（與capacity和size成正比，沒有元素的數組點也需要周遊）開銷。loadFactor代表其空間時間性能交換權衡系數，loadFactor預設為0.75，調大該系數使得空間使用率提高，但是get和put方法的時間性能降低。
- 與HashMap類似，其實作基于數組，用開放定址法解決Hash沖突，每個數組點存儲一個連結清單，當元素個數
size>capacity*loadFactor
- Hashtable疊代器以及其集合視圖（keySet，values）的疊代器都具有fail-fast機制，疊代器被建立後，所有除了疊代器外對集合結構性（插入，删除，更新不是結構修改）的修改都會抛出異常。疊代器通過檢查modCount來判斷是否在疊代過程中出現了結構性的修改。
- Hashtable是線程安全的，其線程安全是基于同步的，如果不需要線程安全建議使用 ，如果需要高并發，建議使用
Hashtable 類頭部
- Hashtable繼承Dictionary，而HashMap繼承AbstractMap。Dictionary隻是提供了虛函數，沒有實作任何方法，AbstractMap實作了豐富的方法，如：equals，toString等。
- HashMap與Hashtable實作的其他接口都是一樣的
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable 主要成員變量
- table數組用來存儲元素連結清單
- count計數元素個數
- threshold 擴容的門檻值
- loadFactor 擴容因子，控制擴容時機（capacity*loadFactor
private transient Entry<K,V>[] table;
private transient int count;
private int threshold;
private float loadFactor;
private transient int modCount = 0;
transient int hashSeed; 構造方法
- 根據initialCapacity，loadFactor，建立table數組，計算threshold
- 根據Map初始化，首先建立二倍于原Map size的table數組，将原有元素transfer到新table中，該過程是同步的
- 與HashMap不同，其容量capacity并不是2的幂次
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);
initHashSeedAsNeeded(initialCapacity);
}
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
public Hashtable() {
this(11, 0.75f);
}
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
public synchronized void putAll(Map<? extends K, ? extends V> t) {
for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
put(e.getKey(), e.getValue());
} 基本節點 Entry
- clone為淺拷貝，沒有建立key和value
- 單連結清單節點除了儲存key和value外，還儲存了指向下一節點的指針next
- 有hash值域
private static class Entry<K,V> implements Map.Entry<K,V> {
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;
}
protected Object clone() {
return new Entry<>(hash, key, value,
(next==null ? null : (Entry<K,V>) next.clone()));
}
// set get方法
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry)o;
return key.equals(e.getKey()) && value.equals(e.getValue());
}
public int hashCode() {
return (Objects.hashCode(key) ^ Objects.hashCode(value));
}
public String toString() {
return key.toString()+"="+value.toString();
}
} Hashtable 中的Holder内部類
- Holder用來加載當虛拟機完全啟動後才初始化的因子
- 由于String類型的key的hashCode方法可能産生更多的hash碰撞，是以JDK7中設定了門檻值，當超過門檻值後使用一種特殊的hashCode計算方法，JDK1.8中已經去除相應機制
- 初始化hashSeed時，首先判斷虛拟機是否完全啟動，然後根據是否使用altHashing決定hashSeed的值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
private static class Holder {
static final int ALTERNATIVE_HASHING_THRESHOLD;
static {
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold"));
int threshold;
try {
threshold = (null != altThreshold)
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
// disable alternative hashing if -1
if (threshold == -1) {
threshold = Integer.MAX_VALUE;
}
if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
} 插入元素 put方法
- 與HashMap最大的差別在于整個put方法是被synchronized包圍的，整個方法是同步的
- 計算key的hash值，如果使用alternative hashing還需要與hashSeed進行抑或，進一步打亂
- 與Integer.maxvalue按位與，確定hash值為正的，對table.length取餘計算index值
- table.index位置可能已有元素（産生hash碰撞），采用頭插法，将元素插入到index位置的頭部
- 如果元素個數超過threshold，進行擴容（rehash()），擴容至原來的2倍多一的大小
- 由于table.length變化，index需要重新計算
- 将原table中的元素transfer到新的table中，将頭插法添加新元素
注意
(e.hash == hash) && e.key.equals(key)
在判斷是插入還是更新時，先判斷hash值是否相等，如果hash值不等，即便equals傳回true也會執行插入操作，而不是更新操作
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
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
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}
private int hash(Object k) {
// hashSeed will be zero if alternative hashing is disabled.
return hashSeed ^ k.hashCode();
}
protected void rehash() {
int oldCapacity = table.length;
Entry<K,V>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<K,V>[] newMap = new Entry[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
boolean rehash = initHashSeedAsNeeded(newCapacity);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
if (rehash) {
e.hash = hash(e.key);
}
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
} 查詢方法 get
- 定位到table指定位置，然後順連結清單查找
- 注意get方法也是同步的，在put方法執行完之前，get方法也需要等待
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;
} 查找算法 containsKey containsValue
- 查詢方法也是同步的，需要等待put方法執行完
- 對key的查詢可以用hash算法直接定位到table數組指定的位置
- 對value的查詢，需要周遊整個table數組和所有連結清單節點，是以時間複雜度是與（capacity和size）成正比
public synchronized boolean containsKey(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 true;
}
}
return false;
}
public boolean containsValue(Object value) {
return contains(value);
}
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
} 删除
- 首先定位到table指定位置
- 注意删除對應位置頭結點時的情況
public synchronized V remove(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index], 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;
} 淺拷貝 clone
- 由于沒有對key和value進行克隆，是以當通過原map修改key和value的屬性時，新map中的key和value也會改變
- 與HashMap不同的是HashMap為對每個節點重建了Entry（同樣沒有克隆key和value），HashTable隻是重建了table中的每個頭結點
public synchronized Object clone() {
try {
Hashtable<K,V> t = (Hashtable<K,V>) super.clone();
t.table = new Entry[table.length];
for (int i = table.length ; i-- > 0 ; ) {
t.table[i] = (table[i] != null)
? (Entry<K,V>) table[i].clone() : null;
}
t.keySet = null;
t.entrySet = null;
t.values = null;
t.modCount = 0;
return t;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
} 視圖 KeySet ValueSet EntrySet
- 視圖是針對于HashTable 的table 進行的操作，與通過HashTable操作效果相同
- 與HashMap不同，contains，remove方法又重新寫了一遍，而在HashMap中是直接調用的HashMap的已有方法，HashMap中的實作更簡潔
private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return getIterator(ENTRIES);
}
public boolean add(Map.Entry<K,V> o) {
return super.add(o);
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry entry = (Map.Entry)o;
Object key = entry.getKey();
Entry[] tab = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry e = tab[index]; e != null; e = e.next)
if (e.hash==hash && e.equals(entry))
return true;
return false;
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
K key = entry.getKey();
Entry[] tab = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index], prev = null; e != null;
prev = e, e = e.next) {
if (e.hash==hash && e.equals(entry)) {
modCount++;
if (prev != null)
prev.next = e.next;
else
tab[index] = e.next;
count--;
e.value = null;
return true;
}
}
return false;
}
public int size() {
return count;
}
public void clear() {
Hashtable.this.clear();
}
} 疊代器
- 由于rehash等因素，疊代次序并不保證不變
- 查找下一個元素算法：如果目前連結清單已經到尾節點，從數組中順次查找下一個非空節點，頭結點作為next()
- 通過模拟枚舉變量KEYS,VALUES,ENTRYS，同時實作了三種視圖的Iterator
- Enumerator是已經被廢棄的疊代元素的方法，相比于Iterator他缺少了remove方法，且方法名更長
- Hashtable同時對這兩種接口進行了适配
private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
Entry[] table = Hashtable.this.table;
int index = table.length;
Entry<K,V> entry = null;
Entry<K,V> lastReturned = null;
int type;
/**
* Indicates whether this Enumerator is serving as an Iterator
* or an Enumeration. (true -> Iterator).
*/
boolean iterator;
/**
* The modCount value that the iterator believes that the backing
* Hashtable should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
protected int expectedModCount = modCount;
Enumerator(int type, boolean iterator) {
this.type = type;
this.iterator = iterator;
}
public boolean hasMoreElements() {
Entry<K,V> e = entry;
int i = index;
Entry[] t = table;
/* Use locals for faster loop iteration */
while (e == null && i > 0) {
e = t[--i];
}
entry = e;
index = i;
return e != null;
}
public T nextElement() {
Entry<K,V> et = entry;
int i = index;
Entry[] t = table;
/* Use locals for faster loop iteration */
while (et == null && i > 0) {
et = t[--i];
}
entry = et;
index = i;
if (et != null) {
Entry<K,V> e = lastReturned = entry;
entry = e.next;
return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
}
throw new NoSuchElementException("Hashtable Enumerator");
}
// Iterator methods
public boolean hasNext() {
return hasMoreElements();
}
public T next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return nextElement();
}
public void remove() {
if (!iterator)
throw new UnsupportedOperationException();
if (lastReturned == null)
throw new IllegalStateException("Hashtable Enumerator");
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
synchronized(Hashtable.this) {
Entry[] tab = Hashtable.this.table;
int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index], prev = null; e != null;
prev = e, e = e.next) {
if (e == lastReturned) {
modCount++;
expectedModCount++;
if (prev == null)
tab[index] = e.next;
else
prev.next = e.next;
count--;
lastReturned = null;
return;
}
}
throw new ConcurrentModificationException();
}
}
} 序列化
- 與HashMap實作相同，key與value分别寫出，在對端逐個讀入Key和value，然後加入新Map進行關聯
- 由于count在可以傳輸得到，是以預先确定了table的容量，減少了擴容的開銷
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
Entry<K, V> entryStack = null;
synchronized (this) {
// Write out the length, threshold, loadfactor
s.defaultWriteObject();
// Write out length, count of elements
s.writeInt(table.length);
s.writeInt(count);
// Stack copies of the entries in the table
for (int index = 0; index < table.length; index++) {
Entry<K,V> entry = table[index];
while (entry != null) {
entryStack =
new Entry<>(0, entry.key, entry.value, entryStack);
entry = entry.next;
}
}
}
// Write out the key/value objects from the stacked entries
while (entryStack != null) {
s.writeObject(entryStack.key);
s.writeObject(entryStack.value);
entryStack = entryStack.next;
}
}
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{
// Read in the length, threshold, and loadfactor
s.defaultReadObject();
// Read the original length of the array and number of elements
int origlength = s.readInt();
int elements = s.readInt();
// Compute new size with a bit of room 5% to grow but
// no larger than the original size. Make the length
// odd if it's large enough, this helps distribute the entries.
// Guard against the length ending up zero, that's not valid.
int length = (int)(elements * loadFactor) + (elements / 20) + 3;
if (length > elements && (length & 1) == 0)
length--;
if (origlength > 0 && length > origlength)
length = origlength;
Entry<K,V>[] newTable = new Entry[length];
threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
count = 0;
initHashSeedAsNeeded(length);
// Read the number of elements and then all the key/value objects
for (; elements > 0; elements--) {
K key = (K)s.readObject();
V value = (V)s.readObject();
// synch could be eliminated for performance
reconstitutionPut(newTable, key, value);
}
this.table = newTable;
} ![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)