ArrayList是什么
ArrayList 是一个容量能动态变化的列表。底层基于数组实现，所以随机访问元素速度较快，但是插入和删除操作比较慢（平均）。ArrayList 的操作不是线程安全的。在多线程中需要借助Collections.synchronizedList() 或者使用 CopyOnWriteArrayList。
ArrayList怎么实现
How to do
如果我们自己需要实现一个动态列表如何去做？需要注意什么？
- 基于数组还是链表
- 提供增删改查功能
- 确保size正确
- 数组如何扩（减）容，什么时候扩（减）容，扩（减）容多大合适
基于数组的一个实现
在add操作时如果size和数组容量相等了，就把数组扩容2倍。
在remove操作时如果size和数组容量的1/4相等了，就把数组减容一半。
public class MyArrayList<E> {
private E[] data; //数组
private int size; //数组实际长度
//默认数组容量为10
public MyArrayList() {
this(10);
}
public MyArrayList(int capacity) {
data = (E[]) new Object[capacity];
}
/**
*
* @param index 添加元素位置
* @param e 添加元素
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Index is Illegal");
}
if (size == data.length) {//数组直接扩容至2倍
resize(2 * size);
}
//从数组最后的元素开始依次后移一位
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
//在index出插入元素
data[index] = e;
//维护size正确
size++;
}
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[i];
data = newData;
}
public E get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Index is Illegal");
}
return data[index];
}
public void set(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Index is Illegal");
}
data[index] = e;
}
public E remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Index is Illegal");
}
E re = data[index];
//从数组index+1处的元素开始依次前移一位
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
//维护size正确
size--;
//最后一位清除数据
data[size] = null;
//减容时注意不能 size==data.length / 2 直接减容
//因为减了之后,add操作又会立马扩容
if(size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return re;
}
// 从数组中删除元素e
public void removeElement(E e) {
int index = find(e);
if (index != -1)
remove(index);
}
public boolean contain(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public int getCapacity() {
return data.length;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("ArrayList: size = %d , capacity = %d\n", size, data.length));
res.append('[');
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size - 1)
res.append(", ");
}
res.append(']');
return res.toString();
}
}
Java的集合框架中的ArrayList如何实现的
源码基于JDK8,摘抄部分源码
增删改查
- 不带容量初始化时，只会指向一个空数组，节约空间
- 在第一次add操作时才会把容量为10的新数组创建出来
- 扩容是当前的1.5倍，overflow-conscious code的解释
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData;
private int size;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//构造方法中先创建一个空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//把index位置空出来
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//如果没有设置初始容量，在第一次add时，就把数组容量变为10
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//确保最小都能扩容到minCapacity
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);
}
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);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
}
RandomAccess, Cloneable, Serializable
RandomAccess接口和三种遍历方式区别
RandomAccess 是 List实现所使用的标记接口，用来表明其支持快速（通常是固定时间）随机访问。此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
例子：Collections.fill() 方法
private static final int FILL_THRESHOLD = 25;
public static <T> void fill(List<? super T> list, T obj) {
int size = list.size();
if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
for (int i=0; i<size; i++)
list.set(i, obj);
} else {
ListIterator<? super T> itr = list.listIterator();
for (int i=0; i<size; i++) {
itr.next();
itr.set(obj);
}
}
}
通过例子能知道，List不同的实现，最优选择的遍历方式也会不一样。实现了RandomAccess接口的可以使用for循环遍历，没实现该接口的选择迭代器方式。
通过一个例子看两种方式的效率
public class RandomAccessTimeTest {
//使用for循环遍历
public static long traverseByLoop(List list){
long startTime = System.currentTimeMillis();
for (int i = 0;i < list.size();i++){
list.get(i);
}
long endTime = System.currentTimeMillis();
return endTime-startTime;
}
//使用迭代器遍历
public static long traverseByIterator(List list){
Iterator iterator = list.iterator();
long startTime = System.currentTimeMillis();
while (iterator.hasNext()){
iterator.next();
}
long endTime = System.currentTimeMillis();
return endTime-startTime;
}
public static void main(String[] args) {
//加入数据
List<String> arrayList = new ArrayList<>();
for (int i = 0;i < 30000;i++){
arrayList.add("" + i);
}
long loopTime = RandomAccessTimeTest.traverseByLoop(arrayList);
long iteratorTime = RandomAccessTimeTest.traverseByIterator(arrayList);
System.out.println("ArrayList:");
System.out.println("for循环遍历时间:" + loopTime);
System.out.println("迭代器遍历时间:" + iteratorTime);
List<String> linkedList = new LinkedList<>();
//加入数据
for (int i = 0;i < 30000;i++){
linkedList.add("" + i);
}
loopTime = RandomAccessTimeTest.traverseByLoop(linkedList);
iteratorTime = RandomAccessTimeTest.traverseByIterator(linkedList);
System.out.println("LinkedList:");
System.out.println("for循环遍历时间:" + loopTime);
System.out.println("迭代器遍历时间:" + iteratorTime);
}
}
result：
-
ArrayList: for循环遍历时间:3 -
ArrayList: 迭代器遍历时间:4 -
LinkedList: for循环遍历时间:3614 -
LinkedList: 迭代器遍历时间:3
第三种遍历方式是：foreach ，底层实现是迭代器
ArrayList删除元素的几种方式
下面4种删除元素方式，1,2是错误的。3,4正确。
remove1 在删除过程中list.size()在不断变化，部分元素不能遍历到。导致删除不完整。解决方式是用remove3采用倒叙遍历。
remove2使用foreach遍历元素。list.remove()时modCount的值会变化，但是在
Iterator.next()过程中会通过checkForComodification()方法检查modCount值，如果不一致就会触发ConcurrentModificationException
remove4是使用Iterator的正确方式，使用Iterator.remove删除元素
public class TestArrayListRemove {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("2");
list.add("2");
list.add("1");
list.add("2");
list.add("2");
remove4(list);
for (int i = 0; i < list.size(); i++) {
System.out.printf("list:" + list.get(i) + "\t");
}
}
//result: list:2 list:1 list:2
private static void remove1(ArrayList<String> list) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals("2")) {
list.remove(i);
}
}
}
//result: ConcurrentModificationException
private static void remove2(ArrayList<String> list) {
for (String s : list) {
if (s.equals("2")) {
list.remove(s);
}
}
}
//result: list:1
private static void remove3(ArrayList<String> list) {
for (int i = list.size() - 1; i >= 0; i--) {
if (list.get(i).equals("2")) {
list.remove(i);
}
}
}
//result: list:1
private static void remove4(ArrayList<String> list) {
Iterator<String> itr = list.iterator();
while (itr.hasNext()) {
String s = itr.next();
if (s.equals("2")) {
itr.remove();
}
}
}
}
Cloneable
了解浅拷贝和深拷贝的区别，
在ArrayList.clone()出来的list和原list里面的每个元素实际指向的相同对象。
如果需要完成复制一份新的数据，需要遍历并复制里面的元素。
//ArrayList.clone()
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
//只复制有效数据
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
//Test Result:
//list1 name:w age:100
//list1 name:s age:12
//list2 name:w age:100
//list2 name:s age:12
public static void main(String[] args) {
Person p1 = new Person("w", 10);
Person p2 = new Person("s", 12);
ArrayList<Person> list1 = new ArrayList<>();
list1.add(p1);
list1.add(p2);
ArrayList<Person> list2 = (ArrayList<Person>) list1.clone();
p1.age=100;
for (Person person : list1) {
System.out.println("list1"+ "\t"+"name:" + person.name + "\t" + "age:" + person.age);
}
for (Person person : list2) {
System.out.println("list2"+ "\t"+"name:" + person.name + "\t" + "age:" + person.age);
}
}
Serializable
希望能通过这三个问题深入理解Serializable
-
ArrayList为什么自己实现了序列化？好处是什么？ -
elementData用transient声明的作用是什么？ - 自己实现序列化了,JVM调用自定义序列化流程是怎样的？
private static final long serialVersionUID = 8683452581122892189L;
transient Object[] elementData;
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
