A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 心弦上的景致 中级黑马   /  2013-4-15 15:07  /  2409 人查看  /  8 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

ArrayList的数据结构是数组
索引查询速度快 但是插入修改速度慢
而且默认长度是10
如果超出长度会自动new一个比原先长度长50%的新数据
那么在自动new一个比原先长度长50%的新数据的时候
在内存中 是如何实现的

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

8 个回复

倒序浏览
我想应该是吧原先数组的最后一个元素带上地址值吧,要不不可能随时都能开辟一个和原先数组相连的空闲的内存段吧
回复 使用道具 举报
本帖最后由 张洪慊 于 2013-4-15 16:44 编辑

你这问题够"狠",哈哈,我查看了下源代码,关键位置分析了下,
如果需要更细节的->你可以去查看源文件:

private transient Object[] elementData;
private int size;
protected transient int modCount = 0;//AbstractList类中
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;


public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }


public ArrayList() {
        this(10);
    }


  private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;//old=10
        int newCapacity = oldCapacity + (oldCapacity >> 1);//newCapacity=10+10/2=15
        if (newCapacity - minCapacity < 0)//15-11>0->不执行
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)//15-Integer.MAX_VALUE - 8<0 不执行
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
       elementData = Arrays.copyOf(elementData, newCapacity);//Arrays类中的方法
    }                                                         //public static <T> T[] copyOf(T[] original,int newLength)
                                                              //将产生一个新的数组:元素是elementData中的元素,长度是newCapacity
                                                              //发现它又重新赋值给了elementData->即elementData指向新数组
private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)//句话当11-10>0时
            grow(minCapacity);//grow(11)->扩充
    }



public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;            //当size=10时,size+1=11
        return true;
    }

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

回复 使用道具 举报
张洪慊 发表于 2013-4-15 16:42
你这问题够"狠",哈哈,我查看了下源代码,关键位置分析了下,
如果需要更细节的->你可以去查看源文件: ...

class文件只能看出一些java更细致的语法逻辑  但是针对内存运算这些还是不明确的

如果没有做过c语言或者玩过汇编 我感觉内存都不是很熟悉
回复 使用道具 举报
心弦上的景致 发表于 2013-4-15 16:44
class文件只能看出一些java更细致的语法逻辑  但是针对内存运算这些还是不明确的

如果没有做过c语言或者 ...

如果你想了解这些,需要更多知识,好像有一本书叫深入分析JVM,当然个人认为,还是先把基础学好->
关于效率,内存神马的->随着知识积累一步步探索.

当然如果你有这个精力和时间的话,可以把必备的基础知识全学了->分析内存等等
回复 使用道具 举报
张洪慊 发表于 2013-4-15 16:47
如果你想了解这些,需要更多知识,好像有一本书叫深入分析JVM,当然个人认为,还是先把基础学好->
关于效率, ...

我朋友说一个数据结构就需要学一年左右  算法啊之类的 我想想都头大
我现在的状态就是遇到什么问题解决什么问题 如果学底层 没精力
回复 使用道具 举报
个人理解如下:原数组的元素在内存中都有自己的地址值,那么数组中存放的应该是地制值,当需要new一个更长的数组时,原数组的地址值会赋给新数组,然后把原数组释放掉,新数组长度是原数组的150%。这是我的理解,如果有正确答案希望分享下。
回复 使用道具 举报
赵海洋 发表于 2013-4-15 18:54
个人理解如下:原数组的元素在内存中都有自己的地址值,那么数组中存放的应该是地制值,当需要new一个更长 ...

暂时没有琢磨出来呢
不过你的解释我感觉有漏洞
不成立
回复 使用道具 举报
它的实现原理是这样;

默认ArrayList 不带参数,初始化数组时比如以下代码:
private transient Object[] elementData;
this.elementData = new Object[10];

大家看一下transient  ,这是设计者不让集合序列化的时候还保持原有数据;

当每次在添加add集合的时候,会判断elementData  的长度是不是超过了当前总长度的一半,现在示例是10,那么就是5;
如果当集合长度超过5,则开辟一个新的扩容数组;
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);(注意右移一位除以2,即加一般容量)

this.elementData = new Object[newCapacity ];

等于说现在巅峰内存是 10(驻留在内存中的数据),和现在开辟的15数据,一共是25;

然后把以前的值Arrays.copyOf(elementData, newCapacity) 复制进新数组,为什么使用Arrays.copyOf,因为其内部实现是  public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,  int length);

评分

参与人数 1技术分 +1 收起 理由
陈丽莉 + 1

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马