Hashtable

概述

Hashtable作为早期的集合，在非并发的情况下，Hashtable已经基本被HashMap取代。而在有同步需求的时候，也可以使用效率更高的ConcurrentHashMap，而不是每个方法都用synchronize修饰的Hashtable。但同时，Hashtbale相对于HashMap与ConcurrentHashMap的来说，实现非常简单。通过Hashtable。我们可以大致了解java中散列表实现的基本原理，为HashMap与ConcurrentHashMap的学习打下基础。

顾名思义，Hashtable是散列表的一种的实现。与List相比，Hashtable的特点是可以存储key-value键值对,并且通过key来快速访问键值对。是不是很像通过下标访问对应元素的数组？与数组相比，Hashtable的优势在于key可以为任意类型。如果数组的下标可以是任意对象，我们可以这样实现一个简易的Hashtable：

public class SimpleHashtable{
    Object[] table=new Object[16];

    void put(Object key,Object obj){
        table[key]=obj;
    }

    Object get(Object key){
        return table[key];
    }
}

不过，java中数组的下标只能是int。那么，如果我们找到一种方法，可以让所有类型的key都映射到int呢？这种方法，通常被称为散列函数。最明显的散列函数恐怕就是hashcode了：

public class SimpleHashtable{
    Object[] table=new Object[16];

    void put(Object key,Object obj){
        table[hash(key)]=obj;
    }

    Object get(Object key){
        return table[hash(key)];
    }

    int hash(Object obj){
        // 将hashcode映射成下标
        int index=obj.hashcode()%table.length;
        return index;
    }
}

但是在SimpleHashtable中，如果数组下标重复了（a.hashcode()==b.hashcode()），新值将会覆盖旧值。这种情况叫做散列冲突，可以利用链表来解决（如下）。用链表解决的方法叫做称为拉链法。采取拉链法，除了可以处理散列冲突，还可以避免最大数组容量2^31-1所带来限制:

public class SimpleHashtable{
    // 数组中每个元素都是一个list
    // 用Entry来存储键值对
    List<Entry>[] table=new List<Entry>[16];

    // 添加元素的时候加入下标对应的list中
    void put(Object key,Object obj){
        table[hash(key)].add(new Entry(key,obj));
    }

    // 获取的时候，遍历list寻找相等Entry
    Object get(Object key){
        for(Entry entry:table[hash(key)]){
            if(entry.key.equals(key)){
                return entry;
            }
        }
    }

    int hash(Object obj){
        // 将hashcode映射成下标
        int index=obj.hashcode()%table.length;
        return index;
    }

    // 存储键值对的结构
    class Entry{
        Object key;
        Object value;
    }
}

注意到，SimpleHashtable中的table容量只有16。当SimpleHashtable的元素远远超过16时，get方法的效率将会大大降低，所需时间逐渐逼近于遍历list，远远超过了table[i]。所以，类似于ArrayList，SimpleHashtable需要有一个方法扩容table，来降低散列冲突，减少遍历list的机会与时间。

public class SimpleHashtable{
    List<Entry>[] table=new List<Entry>[16];
    // 元素数量
    int size;
    // 元素数量大于threshold时，扩容table
    int threshold;

    void put(Object key,Object obj){
        table[hash(key)].add(new Entry(key,obj));
        size++;
        // 元素数量大于threshold时，扩容table，并重新进行散列
        if(size>threshold){
            rehash();
        }
    }

    Object get(Object key){
        for(Entry entry:table[hash(key)]){
            if(entry.key.equals(key)){
                return entry;
            }
        }
    }

    int hash(Object obj){
        int index=obj.hashcode()%table.length;
        return index;
    }

    void rehash(){
        // 构建新table
        // 重新散列元素至新table
        // 设置下一次扩容的threshold
    }

    class Entry{
        Object key;
        Object value;
    }
}

至此，SimpleHashtable便大体完成了。有了SimpleHashtable作为铺垫，理解Hashtable便容易许多。

get/put

首先是get方法，很简单：

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    // 根据hashcode获得对应下标
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // 遍历entry list寻找key值对应元素
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

接着是put方法，有点长，但也很容易理解：

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;
    // 根据hashcode获得对应下标
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // 遍历entry list判断key是否已存在,若存在，则替换原值
    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) {
    Entry<?,?> tab[] = table;
    // 元素数量超过threshold，进行再散列
    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];
    // 添加新的Entry结点:将新结点添加到e之前
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
    modCount++;
}

// 类似于一个LinkedList的结点
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;
    }
}

rehash

在addEntry方法中，我们看到Hashtable使用count与threshold字段，来判断是否需要进行再散列。而Hashtable也有SimpleHashtable中rehash()的几大步骤：构建新table、重新散列元素至新table、设置下一次扩容的threshold。

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

    /* 构建新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 */

    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    // table指向新数组
    table = newMap;

    /* 重新散列元素至新table */

    // 遍历原table
    for (int i = oldCapacity ; i-- > 0 ;) {
        // 遍历Entry链表，重新散列元素
        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;

            // 没有相同index时，e.next=null,table[index]=e
            // 已有相同index时，e.next=table[index],table[index]=e
            // 也就是新Entry作为table[index]:Entry链表的头结点
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

遍历

遍历散列表是非常常见的操作，和Map差不多的三种遍历方式（key、value、entry）无需多言，除此之外，Hashtable还可以通过Enumeration遍历key或者value：

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

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

Hashtable并没有提供通过Enumeration遍历entry的方法，不过有意思的是，Enumerator的实现中却可以返回entry:

private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
    public T nextElement() {
        // ...
        if (et != null) {
            Entry<?,?> e = lastReturned = entry;
            entry = e.next;
            // 可以返回key/value/entry
            return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
        }
        throw new NoSuchElementException("Hashtable Enumerator");
    }
}

为什么已经实现，却没有相应的api呢？我们来看看Enumerator实现的Iterator方法：

private class Enumerator<T> implements Enumeration<T>, Iterator<T> {

    // Iterator methods

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

原来Iterator的next方法也是使用nextElement()实现的，所以返回的entry是为了支持通过Iterator遍历entry。

ci饭，碎觉，输入，输出

Hashtable

概述

导航

get/put

rehash

遍历