前言
面試官問ConcurrentHashMap和HashTable的區(qū)別谋国，當(dāng)時(shí)很緊張前痘，就回答了HashTable的方法都加上了synchronized關(guān)鍵字苛萎，吞吐量沒有ConcurrentHashMap高洞翩，現(xiàn)在悔的腸子都青了焊虏。
1.增加元素 put方法
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 = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
當(dāng)放進(jìn)的value等于null的時(shí)候港令，就拋出空指針異常啥容。這就是“著名的”HashTable不可以放null指針锈颗，而HashMap可以把null當(dāng)成value的論述。
如果要放入的桶tab[index]這個(gè)坑位上已經(jīng)有人占了咪惠，就先遍歷一遍击吱，如果存在哈希沖突，那么就把舊值換成新值遥昧。
如果沒有tab[index]這個(gè)坑位沒有被占用覆醇，或者說沒有發(fā)生哈希沖突，那么就調(diào)用addEntry方法炭臭。
1.1 肩負(fù)重任的addEntry方法
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
第一步永脓，如果HashTable中的元素?cái)?shù)量大于閥值的話，就擴(kuò)容徽缚，并重新定位index憨奸。
第二步，與HashMap不同凿试，HashTable會把新放入的節(jié)點(diǎn)作為鏈表頭部排宰。
1.2 擴(kuò)容
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] 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<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
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;
}
}
}
第一步，確認(rèn)新的桶容量newCapacity那婉，是原來的二倍+1
第二部板甘，將原來桶的頭節(jié)點(diǎn)賦值到新的桶中，當(dāng)然了详炬，要重新計(jì)算index盐类，計(jì)算index的方法與put一樣。
由于沒有使用紅黑樹這一數(shù)據(jù)結(jié)構(gòu)呛谜，擴(kuò)容方法顯的十分簡單在跳。
2.查詢 get方法
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
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 (V)e.value;
}
}
return null;
}
定位index，然后遍歷鏈表隐岛，找到返回相應(yīng)的值猫妙，找不到就返回null。
get方法的思路和HashMap基本方法是比較一致的
3.刪除元素 remove方法
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
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;
}
確認(rèn)了對應(yīng)的位置之后聚凹，就按照在鏈表中刪除節(jié)點(diǎn)的辦法來刪除該節(jié)點(diǎn)割坠。
如果是頭結(jié)點(diǎn)的話，prev就是null妒牙，只需更換頭結(jié)點(diǎn)就好tab[index] = e.next;
如果不是頭結(jié)點(diǎn)彼哼，這個(gè)時(shí)候prev已經(jīng)不是null了，prev的next指針指向要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)就好（有可能是null）
如果沒有對應(yīng)key要?jiǎng)h除的節(jié)點(diǎn)湘今，也沒關(guān)系敢朱，返回null就好。
在這里，也不用考慮TreeNode帶來的影響蔫饰。
結(jié)尾
雖然HashTable給方法都加上了synchronized關(guān)鍵字修飾琅豆，但是在組合使用HashTable的api的時(shí)候，還是有可能出現(xiàn)異常的篓吁，具體可以參考《Java并發(fā)編程實(shí)戰(zhàn)》
面試無處不留坑茫因，平時(shí)真的要多寫多看多總結(jié)！
