数据结构 - HashTable

简介

Hashtable和HashMap一样也是散列表，存储元素也是键值对，Hashtable继承于Dictionary类（Dictionary类声明了操作键值对的接口方法），实现Map接口（定义键值对接口），Hashtable大部分类用synchronized修饰，证明Hashtable是线程安全的

HashTable 类

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

Hashtable继承于Dictionary抽象类

Dictionary 抽象类

public abstract class Dictionary<K,V>

Dictionary 构造函数

public Dictionary() {
}

Dictionary 的方法

abstract public int size();
abstract public boolean isEmpty();
abstract public Enumeration<K> keys();
abstract public Enumeration<V> elements();
abstract public V get(Object key);
abstract public V put(K key, V value);
abstract public V remove(Object key);

Dictionary类，顾名思义，就是字典类，算是早期的Map，不过该类基本上已经废弃了。为什么废弃呢，大致看下Dictionary的源码就知道了。除了常规的get，put请求外，还提供了一些遍历的方法，返回的是Enumeration类型。而Enumeration接口其实算是被Iterator替换了，因为Iterator提供的功能更多，更方便。

HashTable 属性

// 节点数组，每一个Entry代表了一个键值对
private transient Entry<?,?>[] table;
// 容器中包含Entry键值对的数量
private transient int count;
// 阈值，大于这个阈值时需要调整容器容量
private int threshold;
// 加载因子
private float loadFactor;

HashTable 构造函数

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)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

调用此构造函数，初始化时会创建数组；Hashtable跟HashMap不同，HashMap数组长度必须是2的N此幂，而Hashtable没此要求，只要是正int值就行；HashMap初始化时不会创建数组，而Hashtable初始化时就创建数组。

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

此构造函数写死了加载因子0.75

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

此构造函数写死了初始长度为11。

HashTable 添加

public synchronized V put(K key, V value) {
    // 注意value不能为空值（HashMap的value可以放空值）
    if (value == null) {
        throw new NullPointerException();
    }
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // 查找元素是否已经在table中，存在就返回原entry的value
    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;
}

(hash & 0x7FFFFFFF) % tab.length，可以看出Hashtable也是通过取余方式确定key所在的槽，由于Hashtable数组长度不是2的N次幂所以只能使用%方式取余，并且Hashtable也没有使用扰动函数混合键hashCode高低位。addEntry 方法如下

private void addEntry(int hash, K key, V value, int index) {
    modCount++;
    Entry<?,?> tab[] = table;
    if (count >= threshold) {
        // 如果超过阈值，则重新刷新表
        rehash();
        tab = table;
        // 通过key的hashcode计算位置
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }
    // 创建新的entry并插入
    Entry<K,V> e = (Entry<K,V>) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

hash碰撞时使用链表解决，并没有红黑树，公共方法上都有synchronized关键字

HashTable 扩容方法

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;
    // 扩容为原来的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];
    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;
            // 重新根据hash计算index
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

原来数组长度为11，那么扩容一次后长度为：11*2+1=23，迁移数组时也没办法像HashMap一样比较高位加上原长等于新槽，而是重新计算所在槽。

HashTable 删除

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    // 确定所在槽
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // 取出链表
    Entry<K,V> e = (Entry<K,V>)tab[index];
    // 头不为空遍历查找
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
            // 删除key节点
            if (prev != null) {
                prev.next = e.next;
            } else {
                tab[index] = e.next;
            }
            count--;
            V oldValue = e.value;
            e.value = null;
            // 返回删除的节点值
            return oldValue;
        }
    }
    return null;
}

HashTable 清空

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

HashTable 重要内部类

Entry<K,V> 类

private static class Entry<K,V> implements Map.Entry<K,V>

Entry<K,V> 属性

// 键hash值
final int hash;
// 键
final K key;
// 值
V value;
// 下一个节点
Entry<K,V> next;

Entry<K,V> 构造函数

protected Entry(int hash, K key, V value, Entry<K,V> next) {
    // 设置hash值
    this.hash = hash;
    // 设置键
    this.key =  key;
    // 设置value
    this.value = value;
    // 设置下一个节点
    this.next = next;
}

Entry<K,V> 方法

public K getKey() {
    return key;
}

获取当前实体key

public V getValue() {
    return value;
}

获取当前实体值

public V setValue(V value) {
    if (value == null)
        throw new NullPointerException();
    V oldValue = this.value;
    this.value = value;
    return oldValue;
}

设置当前实体新值

public boolean equals(Object o) {
    if (!(o instanceof Map.Entry))
        return false;
    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
    return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
            (value==null ? e.getValue()==null : value.equals(e.getValue()));
}

比较键和值是否都一样

public int hashCode() {
    return hash ^ Objects.hashCode(value);
}

Entry的hashCode是键的hash跟值的hashCode取异或

数据结构 - HashTable

原文：https://www.cnblogs.com/yuanjiangnan/p/12620788.html