Hashtable

释放双眼,带上耳机,听听看~!

今天我们来分析一下Hashtable的底层实现。提到Hashtable可能对于有些人来说会比较陌生,因为不经常使用。这是因为Hashtable是很早就有的集合类了,因为它是在JDK1.0版本中存在的。HashMap集合是在Hashtable集合之后才有的。也可以理解为HashMap集合是优化后的Hashtable。所以它们底层的实现方式几乎是一样,但它们也有些不同的地方要注意,并且它们都是用哈希表的方式存储的。既然我们已经掌握了HashMap的底层实现,那么我们在分析Hashtable时会比较容易,所以本篇中将直接分析Hashtable的底层源码,将不在介绍哈希表的相关知识了。还是和其它集合一样,我们还是先看Hashtable的初始化。

  • 初始化
public Hashtable() {
    this(11, 0.75f);
}
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);
}
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;
    }

    @SuppressWarnings("unchecked")
    protected Object clone() {
        return new Entry<>(hash, key, value,
                              (next==null ? null : (Entry<K,V>) next.clone()));
    }

    public K getKey() {
        return 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);
    }

    public String toString() {
        return key.toString()+"="+value.toString();
    }
}

上面源码是Hashtable集合初始化时所调用的方法,也就是我们通过默认无参的构造方法创建Hashtable对象时,就会执行上述代码。因为我们已经分析过HashMap中的源码了,所以在这里我们将不做过多的解释了。我们将重点分析一下Hashtable初始化与HashMap初始化有何不同。

我们在HashMap这篇文章中分析过,在通过无参的构造方法创建HashMap对象时,只会设置HashMap中的加载因子为默认的0.75,并不会执行底层数组的初始化。而在Hashtable中,不但设置了默认的加载因子为0.75,并且已经将底层的数组初始化了。默认初始化的数组大小为为了11。

下面我们看一下Hashtable中的put方法的底层实现逻辑。

public synchronized V put(K key, V value) {
    if (value == null) {
        throw new NullPointerException(); // 如果添加的元素的value值为null则直接抛出异常,这就说明,在Hashtable中不能保存value为null的元素
    }

    Entry<?,?> tab[] = table; // 定义一个Entry类型的数据保存数据
    int hash = key.hashCode(); // 获取key的hash code,也就是调用Object对象中默认的hashCode方法 因为是直接调用hashCode方法,所以在Hashtable中key也不能为空,否则此出将抛空指针异常
    int index = (hash & 0x7FFFFFFF) % tab.length; // 确认数组中要添加元素的位置
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index]; // 获取数组中上面hash code对应的索引位置的Entry类型数据
    for(; entry != null ; entry = entry.next) { // 循环遍历索引位置的链表数据
        if ((entry.hash == hash) && entry.key.equals(key)) { // 判断链表中Entry类型数据的hash code及key与新添加元素的key和hash code是否相同,如果相同则用新元素中的value覆盖原链表中的Entry类型中的value,并返回原链表中Entry类型的value值
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index); // 如果在链表中没有检索到相同的key则将新元素添加到链表中
    return null;
}
private void addEntry(int hash, K key, V value, int index) {
    modCount++;

    Entry<?,?> tab[] = table; // 获取底层数组
    if (count >= threshold) { // 判断是否需要将底层数组进行扩展,也就是执行再散列
        rehash(); // 执行再散列的方法

        tab = table; // 将散列后的数组重新赋值给tab
        hash = key.hashCode(); // 计算新元素key的hash code
        index = (hash & 0x7FFFFFFF) % tab.length; // 重新确认散列后数组中的添加元素的位置
    }

    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index]; // 返回数组中当前索引位置的Entry对象
    tab[index] = new Entry<>(hash, key, value, e); // 创建一个Entry对象保存新添加元素的数据并设置当前Entry对象的后继节点为原数组索引中返回的Entry对象
    count++;
}
protected void rehash() {
    int oldCapacity = table.length; // 获取原数组的长度
    Entry<?,?>[] oldMap = table; // 保存原数组的数据
  
    int newCapacity = (oldCapacity << 1) + 1; // 计算重新扩容后的数组大小 ,按上面执行的算法每次扩容时新数组的大小都为原大小的2倍加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; // 将新创建后的数组赋值给table实例变量
    // 将原数组中的数据添加到新创建的数组中
    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;
        }
    }
}
  • 总结

通过对上面源码的分析,我们可以得出以下Hashtable的特性。

  • 当我们通过无参构造方法创建Hashtable对象时,底层的数组就会执行初始化,并将数组大小设置为默认大小为11,将加载因子设置为默认值0.75
  • Hashtable中不允许保存null元素,无论是key还是value
  • Hashtable不能保存相同的key元素,如果元素的key相同,则将后添加到Hashtable中的元素的value覆盖原Hashtable已经存在的元素的value
  • Hashtable执行再散列时,会创建比原来数组大2倍+1的新数组
  • Hashtable中我们发现方法中添加了同步关键字synchronized,这就说明在Hashtable是线程安全的集合类,在多线程开发时,无需添加额外的同步代码,就可以保证集合的线程安全
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新消息 消息中心
有新私信 私信列表
搜索