Welcome to

Vcode

首页 / Java / 关于昨天被问到的HashMap 中的rehash

关于昨天被问到的HashMap 中的rehash

说实话 昨天第一次听到这玩意 连续被问了2遍,最后只能尴尬收场。


这就要提到HashMap中的扩容机制resize():

  1. 什么时候扩容?

    当向容器添加元素的时候,会判断当前容器的元素个数,如果大于等于阈值---即当前数组的长度乘以加载因子的值的时候,就要自动扩容。

    扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然Java里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。


void addEntry(int hash, K key, V value, int bucketIndex) {  
    //size:The number of key-value mappings contained in this map.  
    //threshold:The next size value at which to resize (capacity * load factor)  
    //数组扩容条件:1.已经存在的key-value mappings的个数大于等于阈值  
    //             2.底层数组的bucketIndex坐标处不等于null  
    if ((size >= threshold) && (null != table[bucketIndex])) {  
        resize(2 * table.length);//扩容之后,数组长度变了  
        hash = (null != key) ? hash(key) : 0;//为什么要再次计算一下hash值呢?  
        bucketIndex = indexFor(hash, table.length);//扩容之后,数组长度变了,在数组的下标跟数组长度有关,得重算。  
    }  
    createEntry(hash, key, value, bucketIndex);  
}  


/** 
 * 这地方就是链表出现的地方,有2种情况 
 * 1,原来的桶bucketIndex处是没值的,那么就不会有链表出来啦 
 * 2,原来这地方有值,那么根据Entry的构造函数,把新传进来的key-value mapping放在数组上,原来的就挂在这个新来的next属性上了 
 */  
void createEntry(int hash, K key, V value, int bucketIndex) {  
    HashMap.Entry<K, V> e = table[bucketIndex];  
    table[bucketIndex] = new HashMap.Entry<>(hash, key, value, e);  
    size++;  

}

resize的源码(这里使用1.7的jdk,虽然8加入了红黑树,但是区别不大)

 void resize(int newCapacity) {   //传入新的容量
        Entry[] oldTable = table;    //引用扩容前的Entry数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
            threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
            return;
        }
 
        Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
        transfer(newTable);                         //!!将数据转移到新的Entry数组里
        table = newTable;                           //HashMap的table属性引用新的Entry数组
        threshold = (int) (newCapacity * loadFactor);//修改阈值

}

这里就是使用一个容量更大的数组来代替已有的容量小的数组,transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

void transfer(Entry[] newTable) {
        Entry[] src = table;                   //src引用了旧的Entry数组
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
            Entry<K, V> e = src[j];             //取得旧Entry数组的每个元素
            if (e != null) {
                src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
                do {
                    Entry<K, V> next = e.next;
                    int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置
                    e.next = newTable[i]; //标记[1]
                    newTable[i] = e;      //将元素放在数组上
                    e = next;             //访问下一个Entry链上的元素
                } while (e != null);
            }
        }

}

static int indexFor(int h, int length) {
    return h & (length - 1);
}



--未完


本文暂无评论

发表评论

您的电子邮件地址不会被发布。

>> <<