List
ArrayList
扩容原理
源码
/**
* The maximum size of array to allocate. 数组可以分配的最大空间
* Some VMs reserve some header words in an array. 一些虚拟机会保存一些头文字在数组中
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit 试图分配最大空间将会导致内存溢出（因为需要的数组容量大于了虚拟机的限制）
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Default initial capacity. 初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 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) {
int minExpand = (elementData != EMPTY_ELEMENTDATA)
// any size if real element table
? 0
// larger than default for empty table. It's already supposed to be
// at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
/**
* int newCapacity = oldCapacity + (oldCapacity >> 1);
* 新容量为原来的1.5倍
*/
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();
//如果大于MAX_ARRAY_SIZE（Integer.MAX_VALUE - 8）
//返回Interger的最大值0x7fffffff(2147483647)
//否则返回MAX_ARRAY_SIZE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}2017.03.05 新增
ArrayList新增元素
ArrayList的初始容量为10
那么在添加10个元素之后，再添加第11个元素的时候会进行依次扩容
所涉及到的源码
//客户端调用的add方法
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}//上面函数的第一步，确保容量可以容纳下新加的元素
private void ensureCapacityInternal(int minCapacity) {
//修改次数加1，因为是添加，所以修改次数+1
modCount++;
// 如果添加这个元素会导致数组溢出
if (minCapacity - elementData.length > 0)
grow(minCapacity);//增加最小的容量
}
//grow()
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //1.5倍
if (newCapacity - minCapacity < 0) //防止溢出int型，溢出之后是负数
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //如果新的容量大于数组系统默认容量
newCapacity = hugeCapacity(minCapacity);
// 拷贝原来的数组至新开辟空间的数组内，是一个native方法
elementData = Arrays.copyOf(elementData, newCapacity);
}//hugeCapacity
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // int型溢出
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;//int类型和数组系统默认容量取最大
}//java中默认最大为（2^31-1）-8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;set方法
set方法设置固定下标位置为指定的元素。
public E set(int index, E e) {
//判断下标是否在数组范围内，如果不在 会抛出下标溢出边界异常IndexOutOfBoundsException();
rangeCheck(index);
E oldValue = ArrayList.this.elementData(offset + index);
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}像是remove这种方法
这是种什么方法呢
remove(int index)
remove(Object o)
既能根据下标删除，又能根据元素删除，乍一看没什么关系吧，
仔细想一想好像没什么问题
但是int与Integer有什么不一样。。。
如果是删除Integer方法必须要手动包装int
根据对象删除的时候只会删除第一个
public boolean remove(Object o) {
//如果是null 不能调用equals方法，如果是对象可以调用equals方法
//先找出下标再删除
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//fastremove与根据下标删除，与下面的方法仅仅少了一步rangeCheck 不知为何不使用此方法。
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
}
根据下标删除
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;//需要移位的元素个数
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//调用native方法通过复制内存块来复制数组
elementData[--size] = null; // 手动设置gc
return oldValue;
}
2017.12.16 新增
部分注意项
| 方法 | 注意点 |
|---|---|
| 扩容 | 1.5倍,使用system.arraycopy(),是一个native方法，通过复制内存空间的方式来实现数组拷贝 |
特殊问题
复制某个ArrayList到另一个ArrayList
- 使用ArrayList构造方法，比如：ArrayList myObject = new ArrayList(myTempObject)浅拷贝;
- 使用Collection的copy方法,通过迭代器的方式一个一个的设值，浅拷贝
- 序列化和反序列化，深拷贝
public class ArrayListCopyTest {
public static void main(String[] args) throws IOException, ClassNotFoundException {
User u1 = new User("user1", 12);
User u2 = new User("user2", 13);
User u3 = new User("user3", 14);
User u4 = new User("user4", 15);
User u5 = new User("user5", 15);
User u6 = new User("user6", 15);
User u7 = new User("user7", 15);
User u8 = new User("user8", 15);
List<User> userSrc = new ArrayList<>();
userSrc.add(u1);
userSrc.add(u2);
userSrc.add(u3);
userSrc.add(u4);
List<User> userDest = new ArrayList<>(4);
userDest.add(u5);
userDest.add(u6);
userDest.add(u7);
userDest.add(u8);
// 浅拷贝
Collections.copy(userDest, userSrc);
System.out.println(userDest.get(0) == u1);
u1.setName("new_user1");
System.out.println(userDest.get(0).getName());
System.out.println(userSrc.get(0).getName());
for (User user : userDest) {
System.out.println(user.getName());
}
// 浅拷贝2
List<User> userDest2 = new ArrayList<>(userSrc);
System.out.println(userDest2.get(0) == userSrc.get(0));
// 序列化方式 拷贝,这只是jdk的一种格式 还有很多种，比如json/ protobuff
ByteArrayOutputStream bos = new ByteArrayOutputStream();
ObjectOutputStream os = new ObjectOutputStream(bos);
os.writeObject(userSrc);
os.flush();
os.close();
byte[] userSrcByte = bos.toByteArray();
ByteArrayInputStream bis = new ByteArrayInputStream(userSrcByte);
ObjectInputStream is = new ObjectInputStream(bis);
List<User> userDest3 = (List<User>) is.readObject();
System.out.println(userDest3.get(0));
System.out.println(userDest3.get(0).getName());
System.out.println(userDest3.get(0) == userSrc.get(0));
bos.close();
}
}
当传递ArrayList到某个方法中，或者某个方法返回ArrayList，什么时候要考虑安全隐患？如何修复安全违规这个问题呢？
- 首先要判空
- 复制一个新数组的备份，方式原来的数组中的引用改变导致当前的线程安全。
与linkedList的区别
随机读写测试
public class ListCompare {
public static final int N = 10000000;
public static void main(String[] args) {
Random random = new Random();
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < N; i++) {
arrayList.add(1);
}
for (int i = 0; i < N; i++) {
linkedList.add(1);
}
System.out.println("初始化ArrayList与LinkList成功");
long begin1 = System.currentTimeMillis();
randomGetAndSet(random, arrayList);
long end1 = System.currentTimeMillis();
System.out.println("ArrayList: " + (end1 - begin1) + " ms");
long begin2 = System.currentTimeMillis();
randomGetAndSet(random, linkedList);
long end2 = System.currentTimeMillis();
System.out.println("LinkedList: " + (end2 - begin2) + " ms");
}
private static void randomGetAndSet(Random random, List<Integer> list) {
for (int i = 0; i < N; i++) {
if (i % 10000 == 0) {
System.out.println("--------------我还活着-----------------");
}
if (random.nextBoolean()) {
list.set(random.nextInt(N), 10);
} else {
list.get(random.nextInt(N));
}
}
}
}
顺序读写的情况下，明显是ArrayList快，因为相对于O（1）的读取速度，和每次都是O（n）的读取速度。ArrayList的扩容导致的system.arraycopy()的性能可以忽略
如果是大数量顺序写的话LinkedList 明显要比ArrayList快，因为它不需要扩容。当然如果每一次都能预知到ArrayList的初始容量的话，复杂度也是一样的。
顺序读的话两种数据结构复杂度是O(n)