Hashtable源码解析

1、本文主要内容

• Hashtable简介
• Hashtable源码剖析
• 总结

今天来总结下 Hashtable，Hashtable是一个线程安全的容器，它实现了Map接口，使用键值对形式来保存元素。

2、Hashtable简介

Hashtable与HashMap类似，都是以键值对形式存储元素，但它与HashMap最大的差别即是，Hashtable线程安全，而HashMap非线程安全。而且它们各自的父类也不一样，但都实现了Map接口

另外Hashtable求元素索引的方式与HashMap稍有不同，或者可以说方法较为粗糙。

3、Hashtable源码剖析

public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {

/**
 * The hash table data.
 */
//存储数据所用的数组，存储的是entry对象，键值对
private transient Entry[] table;

/**
 * The total number of entries in the hash table.
 */
//存储数据的个数，size方法的返回值
private transient int count;

/**
 * The table is rehashed when its size exceeds this threshold.  (The
 * value of this field is (int)(capacity * loadFactor).)
 *
 * @serial
 */
//超过这个数就重新hash，要扩容
private int threshold;

/**
 * The load factor for the hashtable.
 *
 * @serial
 */
//加载因子
private float loadFactor;

/**
 * The number of times this Hashtable has been structurally modified
 * Structural modifications are those that change the number of entries in
 * the Hashtable or otherwise modify its internal structure (e.g.,
 * rehash).  This field is used to make iterators on Collection-views of
 * the Hashtable fail-fast.  (See ConcurrentModificationException).
 */
//Hashtable结构性改变的次数
private transient int modCount = 0;

/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1421746759512286392L;

public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);

    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry[initialCapacity];
    threshold = (int)(initialCapacity * loadFactor);
}

public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}

//注意Hashtable默认的数组长度是11
public Hashtable() {
    this(11, 0.75f);
}

public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}

//返回当前已存储元素的个数，注意加的同步锁，同步锁为当前的Hashtable对象
public synchronized int size() {
    return count;
}

//查看当前Hashtable是否为空，有没有存储元素
public synchronized boolean isEmpty() {
    return count == 0;
}

//查看是否包含某个值，同样是同步
public synchronized boolean contains(Object value) {
    if (value == null) {
        throw new NullPointerException();
    }

    Entry tab[] = table;
    //因为Hashtable和HashMap一样，都是使用数组链表的形式来存储数据，如果某个key的hash值一样
    //则数组的索引处将有一个链表，所以需要进行两重循环
    for (int i = tab.length ; i-- > 0 ;) {
        for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
            if (e.value.equals(value)) {
                return true;
            }
        }
    }
    return false;
}

public boolean containsValue(Object value) {
    return contains(value);
}

//查看是否包含某个key，线程安全
public synchronized boolean containsKey(Object key) {
    Entry tab[] = table;
    int hash = key.hashCode();
    //注意它和Hashmap不一样的地方，直接拿hash值与 0x7FFFFFFF 相与，
    //意味着hash值只丢弃第1位，其它位全部保留，再将值对tab.length求余，得到索引位置
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return true;
        }
    }
    return false;
}

//获取某个key下的值
public synchronized V get(Object key) {
    Entry tab[] = table;
    int hash = key.hashCode();
    //同样的求索引方式，因为是数组链表，所以还需要一次循环来遍历可能存在的链表，得到最终值
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return e.value;
        }
    }
    return null;
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

//重新hash
protected void rehash() {
    //保存旧的数组以及旧数组的长度
    int oldCapacity = table.length;
    Entry[] oldMap = table;

    // overflow-conscious code
    //扩大数组的长度，2倍加1，同时保证新数组长度不超过最大值
    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];
    //改变次数加1，同时重新计算threshold值，并为table赋新值
    modCount++;
    threshold = (int)(newCapacity * loadFactor);
    table = newMap;
    //两重循环遍历旧数组中的所有元素，重新计算索引值，因为数组的长度变化了，索引值也会不一样
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;
            //重新计算的索引值 
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            //构成链表，新的元素总是在链表的表头，它的next指向旧的链表头
            e.next = newMap[index];
            newMap[index] = e;
        }
    }
}

//线程安全地保存新元素
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;
    //根据已经得到的index值，查看此处可能存在的链表，如果有hash值和key完全一样的元素，则直接替换成新元素
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

    modCount++;
    //如果count值大于threshold，则数组扩容重新hash
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();
        tab = table;
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    //如果不是对已经元素的更新值，则将新元素放在链表头位置，并且将它的next指向之前的老的链表头节点
    Entry<K,V> e = tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
    return null;
}

//线程安全删除对象
public synchronized V remove(Object key) {
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    //计算得到索引，然后从链表处遍历
    for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            //如果hash值相等并且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;
}

public synchronized void putAll(Map<? extends K, ? extends V> t) {
    for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
        put(e.getKey(), e.getValue());
}

//清空所有数组
public synchronized void clear() {
    Entry tab[] = table;
    modCount++;
    for (int index = tab.length; --index >= 0; )
        tab[index] = null;
    count = 0;
}
}

4、总结

其实源码非常简单，目前为止已经分析了多个java容器，只要一查源码，发现其并不神秘，只需要我们都看源码，则它背后的原理就都清楚了。

后续本博还会继续总结set接口，以及各种阻塞队列，分析阻塞的原理等等