阅读 638

深度解析Hashtable

什么是hashtable

HashTable同样是基于哈希表实现的,其实类似HashMap,只不过有些区别,HashTable同样每个元素是一个key-value对,其内部也是通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长。

HashTable比较古老, 是JDK1.0就引入的类,而HashMap 是 1.2 引进的 Map 的一个实现。

HashTable 是线程安全的,能用于多线程环境中。Hashtable同样也实现了Serializable接口,支持序列化,也实现了Cloneable接口,能被克隆。

Hashtable成员变量

private transient Entry[] table;  
// Hashtable中元素的实际数量  
private transient int count;  
// 阈值,用于判断是否需要调整Hashtable的容量(threshold = 容量*加载因子)  
private int threshold;  
// 加载因子  
private float loadFactor;  
// Hashtable被改变的次数  
private transient int modCount = 0;  
复制代码

table是一个Entry[]数组类型,而Entry实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Entry数组中的。 

count是Hashtable的存储大小,是Hashtable保存的键值对的数量。

threshold是Hashtable临界值,也叫阀值,如果Hashtable到达了临界值,需要重新分配大小。阀值 = 当前数组长度✖负载因子。默认的Hashtable中table的大小为11,负载因子的默认值为0.75。

loadFactor是负载因子, 默认为75%。

modCount指的是Hashtable被修改或者删除的次数总数。用来实现“fail-fast”机制的(也就是快速失败)。所谓快速失败就是在并发集合中,其进行迭代操作时,若有其他线程对其进行结构性的修改,这时迭代器会立马感知到,并且立即抛出ConcurrentModificationException异常,而不是等到迭代完成之后才告诉你(你已经出错了)。

Hashtable的基本原理

从下面的代码中我们可以看出,Hashtable中的key和value是不允许为空的,当我们想要想Hashtable中添加元素的时候,首先计算key的hash值,然

后通过hash值确定在table数组中的索引位置,最后将value值替换或者插入新的元素,如果容器的数量达到阈值,就会进行扩充。

源码分析

构造方法

    //默认构造函数,容量为11,负载因子是0.75
    public Hashtable() {
        this(11, 0.75f);
    }
    //用指定初始容量和默认的加载印在(0.74)构造一个空的哈希表。
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }
    //用指定初始容量和指定加载因子构造一个新的空哈希表。其中initHashSeedAsNeeded方法用于初始化
    hashSeed参数,其中hashSeed用于计算key的hash值,它与key的hashCode进行按位异或运算。
    这个hashSeed是一个与实例相关的随机值,主要用于解决hash冲突:

    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,获得大小为initialCapacity的table数组  
    //这里是与HashMap的区别之一,HashMap中table
        table = new Entry[initialCapacity];
    //计算阀值    
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    //初始化HashSeed值   
     initHashSeedAsNeeded(initialCapacity);
    }

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

put方法

public synchronized V put(K key, V value) {//这里方法修饰符为synchronized,所以是线程安全的。
        // 确保value不为null  
        if (value == null) {
            throw new NullPointerException();//value如果为Null,抛出异常
        }
        Entry tab[] = table;

        //计算key的hash值,确认在table[]中的索引位置  

        int hash = hash(key);
        //hash里面的代码是hashSeed^key.hashcode(),null.hashCode()会抛出异常,所以这就解释了
        Hashtable的key和value不能为null的原因。

        int index = (hash & 0x7FFFFFFF) % tab.length;
        //获取数组元素下标,先对hash值取正,然后取余。
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                //迭代index索引位置,如果该位置处的链表中存在一个一样的key,则替换其value,返回旧值  
                V old = e.value;
                e.value = value;
                return old;
            }
        }

        modCount++;//修改次数。
        if (count >= threshold) {//键值对的总数大于其阀值
            rehash();//在rehash里进行扩容处理
            tab = table;
            hash = hash(key);
            //hash&0x7FFFFFFF是为了避免负值的出现,对newCapacity求余是为了使index
            在数组索引范围之内
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
        //在索引出插入一个新的节点
        Entry<K,V> e = tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        //容器中元素+1  ;  
        count++;
        return null;
    }
private int hash(Object k) {
        // hashSeed will be zero if alternative hashing is disabled.
        return hashSeed ^ k.hashCode();//在1.8的版本中,hash就直接为k.hashCode了。
    }
复制代码

 put方法的流程是:计算key的hash值,根据hash值获得key在table数组中的索引位置,然后迭代该key处的Entry链表(我们暂且理解为链表),若该链表中存在一个这个的key对象,那么就直接替换其value值即可,否则在将改key-value节点插入该index索引位置处。

当程序试图将一个key-value对放入HashMap中时,程序首先根据该 key的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry的 value,但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部 

get方法

 public synchronized V get(Object key) {
//没有什么特殊性,就是加了一个synchronized,就是根据index来遍历索引处的单链表。
        Entry tab[] = table;
        int hash = hash(key);
        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;
    }
复制代码

 相对于put方法,get方法就会比较简单,处理过程就是计算key的hash值,判断在table数组中的索引位置,然后迭代链表,匹配直到找到相对应key的value,若没有找到返回null。、

rehash方法

HashTable的扩容操作,在put方法中,如果需要向table[]中添加Entry元素,会首先进行容量校验,如果容量已经达到了阀值,HashTable就会进行扩容处理rehash()

protected void rehash() {  
        int oldCapacity = table.length;  
        //元素  
        Entry<K,V>[] oldMap = table;  
  
        //新容量=旧容量 * 2 + 1  
        int newCapacity = (oldCapacity << 1) + 1;  
        if (newCapacity - MAX_ARRAY_SIZE > 0) { 
        //这里的最大值和HashMap里的最大值不同,这里Max_ARRAY_SIZE的是
        因为有些虚拟机实现会限制数组的最大长度。 
            if (oldCapacity == MAX_ARRAY_SIZE)  
                return;  
            newCapacity = MAX_ARRAY_SIZE;  
        }  
          
        //新建一个size = newCapacity 的HashTable  
        Entry<K,V>[] newMap = new Entry[];  
  
        modCount++;  
        //重新计算阀值  
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);  
        //重新计算hashSeed  
        boolean rehash = initHashSeedAsNeeded(newCapacity);  
  
        table = newMap;  
        //将原来的元素拷贝到新的HashTable中  
        for (int i = oldCapacity ; i-- > 0 ;) {  
            for (Entry<K,V> old = oldMap[i] ; old != null ; ) {  
                Entry<K,V> e = old;  
                old = old.next;  
  
                if (rehash) {  
                    e.hash = hash(e.key);  
                }  
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;  
                e.next = newMap[index];  
                newMap[index] = e;  
            }  
        }  
    }  复制代码

 在这个rehash()方法中我们可以看到容量扩大两倍+1,同时需要将原来HashTable中的元素一一复制到新的HashTable中,这个过程是比较消耗时间的,同时还需要重新计算hashSeed的,毕竟容量已经变了。:比如初始值11、加载因子默认0.75,那么这个时候阀值threshold=8,当容器中的元素达到8时,HashTable进行一次扩容操作,容量 = 8 * 2 + 1 =17,而阀值threshold=17*0.75 = 13,当容器元素再一次达到阀值时,HashTable还会进行扩容操作,一次类推。

关注下面的标签,发现更多相似文章
评论