參考資料

一、HashTable

它和HashMap一樣是一個散列鏈表，它的容器是一個數組，而每一個數組中的元素都是一個單向的鏈表。相對于HashMap來說，它是Map的一個同步的實現。它不支持空key的情況。

二、基本參數

DEFAULT_INITIAL_CAPACITY：默認容量
DEFAULT_LOAD_FACTOR：默認的負載因子,表示散列鏈表的使用度，數越大那么使用度越高。
entry：鏈表對象
table：鏈表的容器是一個數組
threshold：臨界點，當達到這個臨界點的時候進行擴容，它等于負載因子*容量大小

二、創(chuàng)建一個HashTable

1.如果容量是0的話會創(chuàng)建一個空的HashTable
2.如果不是0，會根據傳入的容量計算一個n^2的合理容量大小的數組減小碰撞

    public Hashtable(int capacity) {
       
        if (capacity == 0) {
            @SuppressWarnings("unchecked")
            HashtableEntry<K, V>[] tab = (HashtableEntry<K, V>[]) EMPTY_TABLE;
            table = tab;
            threshold = -1; // Forces first put() to replace EMPTY_TABLE
            return;
        }

        if (capacity < MINIMUM_CAPACITY) {
            capacity = MINIMUM_CAPACITY;
        } else if (capacity > MAXIMUM_CAPACITY) {
            capacity = MAXIMUM_CAPACITY;
        } else {
            capacity = Collections.roundUpToPowerOfTwo(capacity);
        }
        makeTable(capacity);
    }

    private HashtableEntry<K, V>[] makeTable(int newCapacity) {
        @SuppressWarnings("unchecked") HashtableEntry<K, V>[] newTable
                = (HashtableEntry<K, V>[]) new HashtableEntry[newCapacity];
        table = newTable;
        threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
        return newTable;
    }

三、HashTable的函數接口

HashTable的重要函數都是同步方法

synchronized void                clear()
synchronized Object              clone()
             boolean             contains(Object value)
synchronized boolean             containsKey(Object key)
synchronized boolean             containsValue(Object value)
synchronized Enumeration<V>      elements()
synchronized Set<Entry<K, V>>    entrySet()
synchronized boolean             equals(Object object)
synchronized V                   get(Object key)
synchronized int                 hashCode()
synchronized boolean             isEmpty()
synchronized Set<K>              keySet()
synchronized Enumeration<K>      keys()
synchronized V                   put(K key, V value)
synchronized void                putAll(Map<? extends K, ? extends V> map)
synchronized V                   remove(Object key)

四、HashTable的插入

1.它是不支持key，value==null的
2.它會根據key的hash值以及數組的長度計算元素在數組中的位置，如果有一樣的元素那么會覆蓋之前的元素
3.如果容量已滿的話那么會進行擴容
4.在數組的當前位置插入元素，如果該位置有元素，將新元素放在首位將并且next指向舊的元素形成鏈表
5.查詢是獲取當前index位置的entry，遍歷entry是否有相同元素。

 public synchronized V put(K key, V value) {
        if (key == null) {
            throw new NullPointerException("key == null");
        } else if (value == null) {
            throw new NullPointerException("value == null");
        }
        int hash = Collections.secondaryHash(key);
        HashtableEntry<K, V>[] tab = table;
        int index = hash & (tab.length - 1);
        HashtableEntry<K, V> first = tab[index];
        for (HashtableEntry<K, V> e = first; e != null; e = e.next) {
            if (e.hash == hash && key.equals(e.key)) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }

        // No entry for key is present; create one
        modCount++;
        if (size++ > threshold) {
            rehash();  // Does nothing!!
            tab = doubleCapacity();
            index = hash & (tab.length - 1);
            first = tab[index];
        }
        tab[index] = new HashtableEntry<K, V>(key, value, hash, first);
        return null;
    }

四、HashTable的查詢

1.根據key的hash值和數組長度計算出元素在數組的index，遍歷entry，查詢符合條件的元素

   public synchronized V get(Object key) {
        int hash = Collections.secondaryHash(key);
        HashtableEntry<K, V>[] tab = table;
        for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                return e.value;
            }
        }
        return null;
    }

五、HashTable的優(yōu)劣

1.首先相對于HashMap它是線程安全的，可以在多線程共享數據
2.因為它的主要方法都加入了synchronized關鍵詞，所以在單一線程上的性能不如HashMap