ArrayList类的ensureCapacity方法如下:
(此方法被ArrayList的Add方法调用)public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}这行代码的意义是什么?
int newCapacity = (oldCapacity * 3)/2 + 1;
为什么扩大到原来大小的1.5倍+1?
为什么不直接+1呢,难道考虑到定义List的人一般都要扩大2次以上吗?
(此方法被ArrayList的Add方法调用)public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}这行代码的意义是什么?
int newCapacity = (oldCapacity * 3)/2 + 1;
为什么扩大到原来大小的1.5倍+1?
为什么不直接+1呢,难道考虑到定义List的人一般都要扩大2次以上吗?
则(oldCapacity * 3) / 2 = 1,
所以要加1,
为什么不扩大到1.5倍,因为不想执行浮点运算
sun的有些源码,实在让人捉摸不透~~
本人也有个不懂的地方:
inputStream 是面向字节流的,那为什么它的read()返回 0 到 255 范围内的 int 值。而不直接返回byte型。
read()有个约定,就是达到流的结尾时返回-1
如果返回类型是byte,那么-1究竟是代表结束了呢?还是byte -1呢?注:如果返回int,那么如果达到结尾就返回-1,如果byte -1,那么会返回 255
其实这些信息在ArrayList的注释信息就解释的很清楚了。楼主可以仔细看看注释信息,不要光看代,呵呵。
我也没看清楚,很简单拉,内存分配是很耗时的操作,不可能一次+1,如果add 1000次,岂不是要分配内存1000次,并且还要copy? 至于为什么是1。5倍,可能是有统计数据支持的,不过,如果预先知道要add很多次,可以预先设定一个大的capacity
则(oldCapacity * 3) / 2 = 1,
所以要加1,
=====================(oldCapacity * 3) / 2 = 1 然后 +1 不正好是2 了吗?
正好达到了List.size()=1扩大一个变成2,和1+1=2没啥区别了,
我是想知道为啥一次要多扩大不少,一楼能否自己讲一下“所以要加1”的理由,谢谢。--------------
楼上几位朋友分析的很有道理,但是我感觉有 add 1000次的机会,
为什么就没有只add 1次的机会呢?平时用到的List我感觉add多数是用循环加的,
但是次数如果按照1000次的说法,那么数据动辄几万条,也有几万条的可能啊,
那为什么只增加到1.5倍呢?要效率的话,何不多加一些,虽然倍数增加是几何级的,
但是仍然感觉对于1000条数据显得慢了一些,我就是想不太明白,
然后欢迎各路高手前来讨论哈,我先谢了。
necessary, to ensure that it can hold at least the number of elements
specified by the minimum capacity argument.
the minimum capacity argumentcapacity是根据什么得出来的呢?
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity.
*/
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = (E[])new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}
the minimum capacity argument:(最小容量参数)
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
最小容量参数 是指this(10)中10,也就是指:
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list.
* @exception IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = (E[])new Object[initialCapacity];
}
也就是指public ArrayList(int initialCapacity)中的int initialCapacity
思考,但是,就算是今天的开放源码的库实现,也并不是说每一段程序,甚至每一行代码都是精华来的,很多
都是很简单很普通的思路,具体实现时甚至有点随意性的,就像这个newCapacity = (oldCapacity * 3)/2 + 1; 也可以写成
newCapacity = (oldcapacity+1) * 2你也许会说,这样扩容岂不是太快?如果只执行小量的add,岂不是很浪费空间?是的,但是,在需要大量add
操作但又不能明确知道具体需求容量的时候,第二个实现就明显提高性能,因为他减少了分配和复制数组的次数。
关键是,当你认为capacity是性能的瓶颈时,你可以直接设置目标capacity,而不是依赖它自动扩容,这样可以
避免若干次不必要的扩容操作
额外的空间开销来自于,申请的空间多于需要的空间。从时间效率上分析,应该尽量减少扩充的次数。所以,一次扩充的越多越好。
而从空间效率上分析,应该尽量“按需扩充”,需要多少个元素就扩充多少个位置,一次扩充一个当然是最省空间的。可以看出,这两个效率因素是互相矛盾的,不能片面地追求任何一个。
并且实际上,时间效率总是优先于空间效率而被考虑的,所以,一次扩充一个是不可能的。
而一次扩充50%,应该是兼顾各个因素的一个结果。就像楼上有人说的,这可能确有统计数字支持。随着容器的不断扩充,它本身的体积在不断增大,显然,如果按它的某个倍数来扩充,这个扩充速度会越来越快。而每次扩充0.5倍,而不是一倍,又在某种程度上限制了这种扩充速度。Vector就是一次扩充一倍。既然ArrayList是Vector的“改进版本”,那么,就一定有它的优势。
如果你没有更好的做法,那么就相信java的开发团队吧。by the way,那段英文注释是段废话,没有解释这个问题。
----------------------------------------------------------------------------------------------
“回楼上的
read()有个约定,就是达到流的结尾时返回-1
如果返回类型是byte,那么-1究竟是代表结束了呢?还是byte -1呢? 注:如果返回int,那么如果达到结尾就返回-1,如果byte -1,那么会返回 255”=============================================================================================
为什么byte -1,会返回255,byte不也可以有负数值吗?