前言

Hashtable 不知道是否还会有人再使用， 不过作为 Java 容器的成员， 所以还是有必要看看呢。
通过对源码的阅读， 发现所有操作都是加了锁的， 所以说是线程安全的， 但是效率也好低， 其内部实现跟 HashMap 的差不多， 只不过跟 HashMap 存储结果不同， Hashtable 没有红黑树了， 如果碰撞了直接插入到了位置的最前面。

源码分析

关键的成员变量

1
2
3
4
5
6
7
private transient Entry<?,?>[] table;

private transient int count;

private int threshold;

private float loadFactor;

看到了没， 跟 HashMap 的几乎一模一样， 至于各个变量的作用就在过多结束了。
我们看下节点的结构

1
2
3
4
5
6
private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;
}

可以看到这个玩意是一个单链表无疑了。

构造方法

1
2
3
4
5
public Hashtable(int initialCapacity, float loadFactor) {
    this.loadFactor = loadFactor;
    table = new Entry<?,?>[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

看到了没， 这个没有像 HasMap 那样需要对阈值进行算法 2 的次幂， 直接是通过 initialCapacity * loadFactor 进行计算啦。

新增数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}

看上面的插入代码， 其实很容易分析， 第一呢我们发现其方法加上了锁， 第二我们看插入逻辑， 先找到其是否已经存在， 存在的话， 就直接替换数据即可， 如果没有找到的话就 addEntry 进行数据插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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++;
}

插入数据的就要考虑到其容器大小了， 可以看到如果存放的数据超过或者等于了阈值就进行了 rehash 方法进行扩容， 这个其实跟 HashMap 中的 resize 作用差不多。 扩容完毕后就直接进行了新建和保存了。 可以看到其保存的逻辑是 ab[index] = new Entry<>(hash, key, value, e); 在 index 出直接放入了新的数据， 然后把之前当前的位置的数据拼接在了其后面拉链， 也就是当前数据插入到了当前链的起点， 其中大概链图
原有的数据
a
b -> b1 -> b2-> null
c
在 b 处插入了 B 数据， 其结构就会变成如下
a
B -> b -> b1 -> b2 -> null
c
OK 我们看下 Hashtable 的扩容 rehash。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // 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 = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

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

哈哈看到了没， 比 HashMap 的 resize 简单太多了， 仅仅是容器 * 2, 然后阈值在根据当前扩容后的容器进行计算。 最后在把老的数据放到新的扩容后的数据中完事。