jdk1.7扩容源码

//参数 newCapacity 为新数组的大小
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, initHashSeedAsNeeded(newCapacity));//将数组元素转移到新数组里面
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阈值
}
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {//遍历数组
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);//重新计算每个元素在数组中的索引位置
            e.next = newTable[i]; // 添加是链表头添加
            newTable[i] = e; // 将元素放在链上
            e = next;//访问下一个 Entry 链上的元素
        }
    }
}

jdk1.7这里呢e.next = newTable[i]; 这一行代码我迷糊了很久,画图才清晰点
这个是头插法,

e.next = newTable[i];
newTable[i] = e;
这两行代码并不冲突


原本数组长度是2,扩容后变为4, 索引为1 的位置挂了个链表,三个元素(实际上是kv键值对,这里用hash值来代替了)。
假设rehash的计算是取模!

第一次循环(while中的涉及链表的部分)

e=11
int i= 3
e.next=newTab[3] //此时由于还是newTab的处女航,newTab[3] 还没有值,也就为null
newTab[3] = e // e也就是11,11->null

第二次循环

e=7
int i= 3  // 它将挂在那个索引位置所在的链表上
e.next=newTab[3] //此时newTab[3] 已经被探索过,有值了,此时newTab[3] = 11, 也就是e.next=11,
newTab[3] = e // e也就是7,7->11  newTab[3]是7

第三次循环

e=5;
int i= 1;
e.next=newTab[1] //此时newTab[1] 的处女航,原为null;
newTab[1] = e // e也就是5,newTab[1]也就是5;

参考文档:链接1

分类: java

站点统计

  • 文章总数:315 篇
  • 分类总数:20 个
  • 标签总数:193 个
  • 运行天数:1147 天
  • 访问总数:26862 人次

浙公网安备33011302000604

辽ICP备20003309号