- ArrayList
- 底层结构就是Object[] 数组,该数组特点是可以存储任意类型的对象,向上转型,在使用时需要向下转型为实际的类型
Object[] o = new Object[2];
o[0] = new String("ss");
o[1] = new Integer(1);
boolean b =(o[0] instanceof String); //true
boolean b2 =(o[1] instanceof String); //false
boolean b3 =(o[1] instanceof Integer); //true
Integer i = (Integer) o[1]; // need cast when using
- 初始容量是10,如果添加时超过容量时,每次扩容为1.5倍
- ArrayList有 Itr内部类,实现Iterator接口,每次调用iterator()方法时,返回new Itr()
- ArrayList实现 RandomAccess 接口,实现随机访问查找,使用index查询的时间复杂度是o1
- remove() 实际上调用复制数组方法,时间复杂度On
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;
}
- LinkedList
- 数据结构是双向队列,有first和last Node
- 其中Node是静态内部类,有prev 和 next 两个指针
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
-
队列的最常用方法:
-- offer(E e) 调用 add()/addLast() 最终调用 linkLast()
-- poll() 首先判断Node first 是否为空,空的话返回null,不为空调用removeFirst()
-- peek() 和poll类型,允许返回null -
栈的最常用方法:
-- push(E e) 调用 addFirst() 最终调用 linkFirst()
-- pop() 直接调用 removeFirst() 头结点为空,报异常 因此调用前需要确保 LinkedList非空
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
- get(int index) 调用 node(int index) 时间复杂度为On
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
- CopyOnWriteArrayList
- 位于java.util.concurrent 包下
- 是线程安全类,主要使用了ReentrantLock, array 前加了 volatile 修饰
/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();
/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;
- 写入之前加锁,并且在写入过程中先使用临时数组保存修改好的数组,然后使用setArray方法修改array变量,保证写的原子性
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1); // 增加临时数组修改数据
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock(); // 使用完之后务必释放锁
}
}
- 删除时和写入类似,都采用 加锁+新建临时数组
public E remove(int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
E oldValue = get(elements, index);
int numMoved = len - index - 1;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
} finally {
lock.unlock();
}
}
- get(int index) 无须加锁,如果在get时其他线程正在修改 array,get方法虽然得不到最新的值,但是不会阻塞线程的执行。
- CopyOnWrite并发容器用于读多写少的并发场景。比如白名单,黑名单,商品类目的访问和更新场景,假如我们有一个搜索网站,用户在这个网站的搜索框中,输入关键字搜索内容,但是某些关键字不允许被搜索。这些不能被搜索的关键字会被放在一个黑名单当中,黑名单每天晚上更新一次。当用户搜索时,会检查当前关键字在不在黑名单当中,如果在,则提示不能搜索