深度解析Hashtable

Hashtable成员变量

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

从下面的代码中我们可以看出，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;
    }

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还会进行扩容操作，一次类推。