JDK源码阅读(5)：HashTable类阅读笔记

public class Hashtable
    extends Dictionary
    implements Map, Cloneable, java.io.Serializable {
    ...
}

HashMap只实现了Map接口，而HashTable还继承了Dictionary类。但实际上Dictionary类只是一个历史遗留问题，任何新的键值对集合都只需要实现Map接口。

public Hashtable() {
    this(11, 0.75f);
}

HashTable的默认容量是11，默认负载因子是0.75。HashMap的这两个值分别是16和0.75。

在阅读到HashTable的构造函数时，我看到了一个奇怪的构造函数：

Hashtable(Void dummy) {}

首先，在参数列表中出现了一个我从来没见过的类：Void类。我们进入查看这个类的定义。

package java.lang;


public final class Void {

    
    @SuppressWarnings("unchecked")
    public static final Class TYPE = (Class) Class.getPrimitiveClass("void");

    
    private Void() {}
}

可以看到，Void类是一个final类，同时只有一个私有的构造函数。显然，这个类既不可以被继承，也不可以被实例化。在doc中我们得知，这是一个占位符类，用于保存对表示Java关键字void的Class对象的引用。

我们可以想到，假如将Void类作为一个方法的返回类型，这意味着这个方法只能返回null。

public Void f(){
    ...
}

那么在这里作为参数的Void类又起到怎样的功能呢？继续阅读构造方法上方的doc，我们发现，这个函数是供java.util.Properties类使用的，Properties类中有下面这个构造函数。

private Properties(Properties defaults, int initialCapacity) {
    // use package-private constructor to
    // initialize unused fields with dummy values
    super((Void) null);
    map = new ConcurrentHashMap<>(initialCapacity);
    this.defaults = defaults;

    // Ensure writes can't be reordered
    UNSAFE.storeFence();
}

Properties类是HashTable类的子类，在这个构造函数中它调用了HashTable中包级私有的构造方法。如果没有这个super语句的话，就会默认调用父类HashTable的无参构造函数，但显然，这是没有必要的。通过在HashTable中添加一个伪构造方法供Properties类调用，可以避免这种无必要的开销。

这里顺便说明一下Properties类。

• Properties类表示一组持久的属性。表示一个持久的属性集，属性列表中每个键及其对应值都是一个字符串。

• Properties 类被许多 Java 类使用。例如，在获取环境变量时它就作为 System.getProperties() 方法的返回值。

• Properties 定义如下实例变量.这个变量持有一个 Properties 对象相关的默认属性列表。

  Properties defaults;
  

HashTable中为几乎所有业务方法都添加了synchronized关键字，实现了线程安全。

public synchronized int size() {...}
public synchronized boolean isEmpty() {...}
public synchronized V put(K key, V value) {...}
public synchronized V get(Object key) {...}
public synchronized V remove(Object key) {...}

public synchronized Enumeration keys() {
    return this.getEnumeration(KEYS);
}

public synchronized Enumeration elements() {
    return this.getEnumeration(VALUES);
}

返回了键集合和值集合的枚举。

private  Enumeration getEnumeration(int type) {
    if (count == 0) {
        return Collections.emptyEnumeration();
    } else {
        return new Enumerator<>(type, false);
    }
}

下面是作为HashTable类内部类的枚举类

private class Enumerator implements Enumeration, Iterator {
    final Entry[] table = Hashtable.this.table;
    int index = table.length;
    Entry entry;
    Entry lastReturned;
    final int type;

    
    final boolean iterator;

    
    protected int expectedModCount = Hashtable.this.modCount;

    Enumerator(int type, boolean iterator) {
        this.type = type;
        this.iterator = iterator;
    }

    public boolean hasMoreElements() {
        ...
    }

    @SuppressWarnings("unchecked")
    public T nextElement() {
        Entry et = entry;
        int i = index;
        Entry[] t = table;
        
        while (et == null && i > 0) {
            et = t[--i];
        }
        entry = et;
        index = i;
        if (et != null) {
            Entry e = lastReturned = entry;
            entry = e.next;
            return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
        }
        throw new NoSuchElementException("Hashtable Enumerator");
    }

    // Iterator methods
    public boolean hasNext() {
        return hasMoreElements();
    }

    public T next() {
        if (Hashtable.this.modCount != expectedModCount)
            throw new ConcurrentModificationException();
        return nextElement();
    }

    public void remove() {
        ...
    }
}

int index = (hash & 0x7FFFFFFF) % tab.length;

hash & 0x7FFFFFFF是为了保证hash值是一个正数，即二进制下第一位是0。

然后直接对length取模。

protected void rehash() {
    int oldCapacity = table.length;
    Entry[] oldMap = table;

    // 扩容逻辑：乘二加一
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // 原容量就满了，则直接返回
            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 old = (Entry)oldMap[i] ; old != null ; ) {
            Entry e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry)newMap[index];
            newMap[index] = e;
        }
    }
}

该方法会增加哈希表的容量并在内部重新组织哈希表。当哈希表中的键数超过此哈希表的容量*负载因子时，将自动调用此方法。扩容的逻辑是容量*2+1。

下面的方法用于向表中假如键值对，在put等方法中都有调用。

private void addEntry(int hash, K key, V value, int index) {
    Entry tab[] = table;
        if (count >= threshold) {
            // 先调用rehash()
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry e = (Entry) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        modCount++;
}