集合專區---第9集(HashTable)

1 HashTable 結構(jdk 1.80_201)

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
           

2 HashTable特點

1. key不能為null（因為代碼中需要擷取key的hashCode值，不然會報空指針。）
2. value不能為null，因為代碼中做了if判斷，如果為null那就抛出空指針
3. 方法是同步的
4. 效率相對HashMap 慢

3 整體的存儲結構

1. 結構組成：數組+單向連結清單

4 

連結清單節點

private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;
}      

5 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;
}
      

•  方法加了同步鎖。
•  邏輯：
• 根據key找到數組所在的索引
• for循環周遊連結清單，如果發現key相同就覆寫對應的value值，且return 之前key對應的value 值。
• 否則 添加新的元素

6 添加新元素
private void addEntry(int hash, K key, V value, int index) {
    modCount++;//修改Map的此時+1

    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++;
}
      

邏輯：1 判斷是否擴容 . 2 new 一個連結清單節點Entry,且把他的next屬性設定為 數組所在index（根據key得到的索引位置）的第一個連結清單節點。3 新的連結清單節點成為了數組所在index位置的第一個連結清單節點

7 get方法

public synchronized V get(Object key) {//也是同步方法
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;//根據key得到的hash值擷取在數組中的索引
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { //循環該索引所在位置的連結清單結構.
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}      

8 contains 方法（containsValue方法調用的是contains方法，也就是說兩個方法一模一樣的）

public synchronized boolean contains(Object value) {
    if (value == null) {
        throw new NullPointerException();
    }

    Entry<?,?> tab[] = table;
    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;
}      

9 containsKey

public synchronized boolean containsKey(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 true;
        }
    }
    return false;
}      

邏輯：根據key找到hash，根據hash找到數組中的索引index,然後根據index找到連結清單，且循環這個單向連結清單。

結論：

1 HashTabel 會把新的元素添加到索引對應數組所在連結清單的第一個位置，也就是說新的元素不會像HashMap一樣放置再連結清單最後面，而是在最前面。

2 沒有發現紅黑樹結構

3 put,get,contains等方法都是同步方法

4 key,value不能為null

5 用于資料量不大（因為效率慢，資料量大的話插入所需時間會很長），且需要同步的方法。