1 概述

HashTable继承自抽象类Dictionary，并实现了Map接口，实际上，Map接口就是用来代替Dictionary
是一个线程安全的Map
key和value均不允许为null
为了正确使用Hashtable存取key-value对，用作key的类必须实现hashcode()和equals()方法
初始化用的 initial capacity 和 load factory(默认为0.75) 会影响HashTable的性能

2 底层实现

五个私有变量
- transient Entry[] table HashTable实际维护的容器，一个Entry数组
- transient int count 容器存储key-value对的总数
- int threshold 扩容标志，当容器的size()大于这个值时，会进行rehash操作——扩容并重新组织table
- float loadFactor 扩容因子，扩容相关
- transient int modCount = 0 一个标志，每次修改容器内容modCount就会自增，主要用于遍历时判断是否容器是否在被其他对象修改，如果modeCount在遍历时发生变化，就会抛出异常
初始化
- 基本的构造器HashTable(int initialCapacity, float loadFactor)，
  table实际是HashTable里一个静态私有类Entry<K, V>数组，Entry<K, V> 实现了Map.Entry<K, V> 接口

public Hashtable(int initialCapacity, float loadFactor) {
    // 1. 判断参数是否合法
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    // 2. 如果传入的初始容量为 0 时，设为 1
    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    // 3. 开辟一个初始容量为 initialCapacity的数组
    table = new Entry<?,?>[initialCapacity];
    // 计算触发扩容的容量
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

HashTable(int initialCapacity) 默认 loadFactory 为 0.75
HashTable() 默认 initialCapacity 为 11， loadFactory 为 0.75
HashTable(Map map) 默认 initialCapacity 为 max(2*map.size(),11), loadFactory 为0.75
静态私有类 Entry<K, V>，不难看出实际上这是一个单向链表

private static class Entry<K,V> implements Map.Entry<K,V> {
    final 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;
    }
    // 其他实现 Map.Entry<K, V>接口的代码
}

put(key, 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; // hash & 0x7FFFFFFF 保证了index不会是负数
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index]; 
    for(; entry != null ; entry = entry.next) {
        // 遍历链表, 查看是否已存在相同的key, hash相等，且 equals 返回true
        if ((entry.hash == hash) && entry.key.equals(key)) {
            // 匹配到相同的key，替换value，并返回原value
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }   
    // 不存在这个key，直接添加，并返回null
    addEntry(hash, key, value, index);
    return null;
}

private void addEntry(int hash, K key, V value, int index) {
    Entry<?,?> tab[] = table;
    // 首先查看容量是否符合扩容的要求
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        // 调用rehash方法， 并重新组织table
        rehash();

        tab = table;
        hash = key.hashCode();
        // 因为扩容了， 所以需要重新计算 index
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    // 把新的Entry设置为单向链表的开始节点
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
    modCount++;
}

扩容算法 rehash()

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;
    /**
     *确定新容量
     * 1. 假定newCapactity = oldCapacity * 2 + 1
     * 2. 如果假定的newCapacity大于数组允的许最大长度Integer.MAX_VALUE-8, 
     *    a. 如果原长oldCapacity等于允许的最大长度， 无法扩容了， 跳出该方法不进行扩容
     *    b. 日过不相等，直接将扩容目标值设置为数组允许的最大长度
     */
    // 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
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;
    // 将已有的key-value对放到新的数组中，完成扩容
    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;
        }
    }
}

get(Object key) 实际上就是put(key,value)中的一段

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

3 总结

HashTable的主要方法都使用synchronized关键字修饰来保证其线程安全
底层使用哈希表实现
因为有 HashMap 和 ConcurrentMap的存在，被用得很少，但是我们常用的Properties类是通过继承HashTable来实现的