java - ArrayList的数组扩容是如何考虑溢出的?
阿神
阿神 2017-04-18 09:38:39
0
3
803

这段代码是java1.8种util.ArrayList中关于数组扩容的一段代码, 上面有一行//overflow-conscious code. 说明下面的代码是对溢出进行考虑的代码 ,但是我花了好多时间在上面仍没有想清楚他是如何避免溢出的, 以及如何在newCapacity溢出的情况下工作的, 望指点迷津

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); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
阿神
阿神

闭关修行中......

全員に返信 (3)
小葫芦

当数组要溢出的时候,就加上数组的1/2,然后和数组最大的常量进行比对,如果超出数组的最大size,就新申请一个Integer.MAX_VALUE的数组,然后把之前旧数组复制过来。
其中最难理解的是>>1,其实相当于除以2。

いいねを押す+0
    小葫芦

    写个简单的例子,楼主调试一下就知道了

    public static void main(String[] args) { int oldCapacity = Integer.MAX_VALUE - 16; System.out.println(oldCapacity); int minCapacity = Integer.MAX_VALUE - 15; int maxSize = Integer.MAX_VALUE - 8; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - maxSize > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: System.out.println(newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > Integer.MAX_VALUE - 8) ? Integer.MAX_VALUE : Integer.MAX_VALUE - 8; }

    int newCapacity = oldCapacity + (oldCapacity >> 1);这句执行后如果超过int的最大值那么newCapacity会是一个负数,这个需要了解一下数字二进制的加减原理。

    下面这四句就是针对newCapacity溢出变成负数的时候的处理

    if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - maxSize > 0) newCapacity = hugeCapacity(minCapacity);
    いいねを押す+0
      伊谢尔伦

      我想你是说在多线程操作同一个arraylist吧,这时候刚好凑巧出现了长度溢出问题,问题是arraylist本来就不是线程安全的,正确的做法是去用 java.util.concurrent 里的 CopyOnWriteArrayList

      いいねを押す+0
        最新のダウンロード
        詳細>
        ウェブエフェクト
        公式サイト
        サイト素材
        フロントエンドテンプレート
        私たちについて 免責事項 Sitemap
        PHP中国語ウェブサイト:福祉オンライン PHP トレーニング,PHP 学習者の迅速な成長を支援します!