The Wayback Machine - https://web.archive.org/web/20201011105057/https://github.com/Snailclimb/JavaGuide/issues/428
Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Arraylist源码分析,扩容大小既不是1.5倍,也不是1.5倍加1,这个要看原数组大小的奇偶来判定 #428

Open
cmy1997 opened this issue Aug 7, 2019 · 4 comments
Labels

Comments

@cmy1997
Copy link

@cmy1997 cmy1997 commented Aug 7, 2019

No description provided.

@wangzitiansky
Copy link

@wangzitiansky wangzitiansky commented Oct 11, 2019

能详细说一下嘛

@cmy1997
Copy link
Author

@cmy1997 cmy1997 commented Oct 12, 2019

@jinyahuan
Copy link
Contributor

@jinyahuan jinyahuan commented Oct 17, 2019

最好自己提个pr,版主可能没时间改--
你这个描述也不对,应该是1.5倍后的向下取整。

移位我把源码搞过来,源码里说明了 有符号右移相当于除以2就懂了,10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

    /**
     * ArrayList扩容的核心方法。
     */
    private void grow(int minCapacity) {
       //elementData为保存ArrayList数据的数组
       ///elementData.length求数组长度elementData.size是求数组中的元素个数
        // oldCapacity为旧容量,newCapacity为新容量
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位,其效果相当于oldCapacity /2,
        //我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍,
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当作数组的新容量,
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //再检查新容量是否超出了ArrayList所定义的最大容量,
        //若超出了,则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE,
        //如果minCapacity大于MAX_ARRAY_SIZE,则新容量则为Interger.MAX_VALUE,否则,新容量大小则为 MAX_ARRAY_SIZE。
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
@tonglinshuo
Copy link

@tonglinshuo tonglinshuo commented Feb 6, 2020

int newCapacity = oldCapacity + (oldCapacity >> 1);

源码是对原数组进行移位操作,新数组容量等于[旧数组容量+旧数组容量 右移一位 ],奇偶不同,二进制最后一位不同,移位后容量就不同

 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    } 
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants
You can’t perform that action at this time.