Hashtable

存储结构

数组+链表，没有HashMap的红黑树

put(K key, V value)

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;
}
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中对hash值进行寻址的方法为 hash%数组长度 (与HashMap不同，所以不要求数组长度必须为2的n次方)

遍历table[index]所连接的链表，查找是否已经存在key与需要插入的key值相同的节点，如果存在则直接更新value，并返回旧的value。如果table[index]所连接的链表上不存在相同的key,则通过addEntry()方法将新节点加在链表的开头

get(Object key)

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

get 方法比较简单，就是循环遍历比较，找到就返回

remove(Object key)

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

这个也比较简单，也是循环查找，然后删除节点

性能上分析

1. 计算哈希值上HashMap领先于HashTable
2. HashTable底层是数组加链表。而HashMap底层是数组加链表加红黑树。数据多了红黑树效率遥遥领先
3. HashTable每个暴露的方法都加了synchronized关键字。导致了性能低下。但是保证了线程安全，但是线程安全为什么不用ConcurrentHashMap呢