List集合的使用和源码

目录1、List框架图2、List的基本方法3、ArrayList(最常用的)4、Vector线程安全性能差5、LinkedList(链表)6、CopyOnWriteArrayList线程安全性能好总结比较1、List框架图2、List的基本方法以下为List接口的全部方法。在后面的具体实现类中会讲解具体的逻辑public interface ListE extends CollectionE { int size()获取集合大小 boolean isEmpty()判断是否为空 boolean contains(Object o)是否包含某个元素 IteratorE iterator()返回迭代器 Object[] toArray()集合转数组 boolean add(E e)添加元素 boolean remove(Object o)删除元素 boolean addAll(Collection c)批量添加 void clear()清空集合 E get(int index)根据下标获取元素 E set(int index, E element)根据下标修改元素 void add(int index, E element)指定位置插入 E remove(int index)根据下标删除 int indexOf(Object o)查找元素下标 ListE subList(int from, int to)截取子集合 }3、ArrayList(最常用的)数据结构数组是否线程安全否成员变量// 默认初始容量当我们在创建ArrayList时未指定容量大小则初始容量为10 private static final int DEFAULT_CAPACITY 10; // 用于指定容量为 0 时的空数组 private static final Object[] EMPTY_ELEMENTDATA {}; // 用于默认大小的空数组实例无参构造时使用 // 将其与 EMPTY_ELEMENTDATA 区分开是为了知道添加第一个元素时扩容到多少。 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; // ArrayList 的底层存储数组这里可以看到ArrayList的底层数据结构是基于数组实现的 transient Object[] elementData; // non-private to simplify nested class access // 当前数组的实际元素个数 private int size;EMPTY_ELEMENTDATA 和DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的区别可以看后续的add方法这里先简单说下区别- EMPTY_ELEMENTDATAnew ArrayList(0) 使用第一次扩容到 1- DEFAULTCAPACITY_EMPTY_ELEMENTDATAnew ArrayList() 使用第一次扩容到 10目的让 JDK 区分“用户手动设为0”和“默认构造”执行不同扩容策略。常见问题点1、根据add方法可以看到如果不指定初始容量大量数据会频繁扩容性能较差如果我们知道长度预先指定长度可以减少扩容次数。2、线程不安全多线程下会出现数据丢失、越界3、适用场景查询快但是增删慢。删除元素如果元素在数组中间需要将后面所有元素前移。如果增加元素可能出发扩容。常用方法源码解析public ArrayList()ArrayList的无参构造在我们使用ArrayList的无参构造方法时可以看到将当前元素指定为DEFAULTCAPACITY_EMPTY_ELEMENTDATA对象后续扩容时扩容为默认大小10public ArrayList(int initialCapacity)ArrayList有参构造入参为该数组大小public ArrayList(int initialCapacity) { if (initialCapacity 0) { // 如果入参值大于0设置当前集合大小为入参值 this.elementData new Object[initialCapacity]; } else if (initialCapacity 0) { // 如果入参值等于0标记为EMPTY_ELEMENTDATA后续扩容为1 this.elementData EMPTY_ELEMENTDATA; } else { // 小于0报错 throw new IllegalArgumentException(Illegal Capacity: initialCapacity); } }public ArrayList(Collection? extends E c)ArrayList有参构造入参为顶级Collection接口public ArrayList(Collection? extends E c) { // 将入参赋值给elementData elementData c.toArray(); if ((size elementData.length) ! 0) { // 如果入参集合长度不等于0就使用copyOf方法复制为一个新数组赋值到elementData if (elementData.getClass() ! Object[].class) elementData Arrays.copyOf(elementData, size, Object[].class); } else { // 入参集合长度等于0标记为空数组 this.elementData EMPTY_ELEMENTDATA; } }public boolean add(E e)常用的add方法向集合中添加一个元素public boolean add(E e) { // 这个方法是集合进行动态扩容的关键 ensureCapacityInternal(size 1); // Increments modCount!! elementData[size] e; return true; } 调用该方法进行判断 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } 获取此时调用add方法时需要的容量大小 private static int calculateCapacity(Object[] elementData, int minCapacity) { // 如果是等于无参构造中的DEFAULTCAPACITY_EMPTY_ELEMENTDATA这里也就是体现到了DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA的区别。 // 如果是DEFAULTCAPACITY_EMPTY_ELEMENTDATA说明是第一次向集合中添加元素 if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 取默认值和当前数组所需容量大小的最大值返回。这里就可以看到使用了默认长度10 // 可以看到集合不是在new的时候创建容量的而是在第一次add元素时创建容量的 return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { //快速失败机制fail-fast 和迭代器一致性检测 modCount; // 这里判断是否需要扩容如果返回的所需数组大小大于当前数组的长度说明容量不够用了 就需要出发扩容方法来增加容量。 // 因此从这里可以看出来如果我们可以指定集合存放数据的大小就可以使用初始化时设置集合长度避免扩容。 if (minCapacity - elementData.length 0) grow(minCapacity); }实际扩容方法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); }由此我们可以看到数组的扩容是由数组的拷贝实现的public boolean remove(Object o)通过这个源码可以发现当我们移除元素时需要进行for循环一个一个进行比较调用equals比较移除掉后需要将整个数组前移所以他的时间复杂度是O(n)public boolean remove(Object o) { 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; } private void fastRemove(int index) { modCount; int numMoved size - index - 1; if (numMoved 0) System.arraycopy(elementData, index1, elementData, index, numMoved); elementData[--size] null; // clear to let GC do its work }public boolean contains(Object o)这里看到contains方法也是通过for循环遍历对比的性能也较差时间复杂度O(n)public boolean contains(Object o) { return indexOf(o) 0; } public int indexOf(Object o) { if (o null) { for (int i 0; i size; i) if (elementData[i]null) return i; } else { for (int i 0; i size; i) if (o.equals(elementData[i])) return i; } return -1; }4、Vector线程安全性能差数据结构数组是否线程安全是常用方法源码解析我们可以看到他的线程安全是通过synchronized实现的所以性能较差现在已经很少用了public synchronized boolean add(E e) { modCount; ensureCapacityHelper(elementCount 1); elementData[elementCount] e; return true; } public synchronized E remove(int index) { modCount; if (index elementCount) throw new ArrayIndexOutOfBoundsException(index); E oldValue elementData(index); int numMoved elementCount - index - 1; if (numMoved 0) System.arraycopy(elementData, index1, elementData, index, numMoved); elementData[--elementCount] null; // Let gc do its work return oldValue; }5、LinkedList(链表)数据结构链表是否线程安全否成员变量transient int size 0; /** * Pointer to first node. * Invariant: (first null last null) || * (first.prev null first.item ! null) */ transient NodeE first; /** * Pointer to last node. * Invariant: (first null last null) || * (last.next null last.item ! null) */ transient NodeE last;常见问题点1、占用内存比ArrayList多因为每个元素都是一个Node节点需要存储前后节点。2、线程不安全。3、增删快查询慢。增删只需要修改前后节点指针即可查询需要遍历。构造方法public LinkedList() { } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collections * iterator. * * param c the collection whose elements are to be placed into this list * throws NullPointerException if the specified collection is null */ public LinkedList(Collection? extends E c) { this(); addAll(c); }Node对象private static class NodeE { E item; NodeE next; NodeE prev; Node(NodeE prev, E element, NodeE next) { this.item element; this.next next; this.prev prev; } }常用方法源码解析public boolean add(E e)将当前要添加的元素挂在链表最后一个节点public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final NodeE l last; final NodeE newNode new Node(l, e, null); last newNode; if (l null) first newNode; else l.next newNode; size; modCount; }public E get(int index)可以看到是通过遍历获取的性能较差public E get(int index) { checkElementIndex(index); return node(index).item; } NodeE node(int index) { // assert isElementIndex(index); if (index (size 1)) { NodeE x first; for (int i 0; i index; i) x x.next; return x; } else { NodeE x last; for (int i size - 1; i index; i--) x x.prev; return x; } }6、CopyOnWriteArrayList线程安全性能好数据结构数组是否线程安全是核心原理读不加锁、修改时加锁复制常见问题点1、读无锁直接读当前数组2、写加锁 → 复制新数组 → 写完替换引用。所以性能比不加锁差。3、数据有最终一致性不能实时一致。因为读不加锁有可能写正在修改时候被读导致数据不一致。4、内存占用高同一时间存在新旧两个数组代码实现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(); } }总结比较1、日常开发优先用ArrayList2、频繁头尾增删用LinkedList3、高并发读多写少用CopyOnWriteArrayList4、Vector 基本废弃ArrayListLinkedListVectorCopyOnWriteArrayList数据结构动态数组双向链表动态数组写时复制数组查询速度O1OnO1O1增删速度OnO1OnOn(加锁、慢)内存占用小大小高线程安全否否是(synchronized)是(ReentrantLock)扩容机制1.5倍无2倍每次复制新数组适用场景大量查询、少增删频繁增删、少查询基本废弃读多写少