集合

框架关系图：

Collection接口下面有三个子接口：List、Set、Queue。此篇是关于List<E>的简单学习总结。

补充：HashTable父类是Dictionary，不是AbstractMap。

List（有序、可重复）：

List里存放的对象是有序的，同时也是可以重复的，List关注的是索引，拥有一系列和索引相关的方法，查询速度快。因为往list集合里插入或删除数据时，会伴随着后面数据的移动，所有插入删除数据速度慢。

List常用的子类：ArrayList。（面试常问的：Vector、ArrayList、LinkedList之间的区别）。

ArrayList：

public class ArrayList<E> extends AbstractList<E> implements List<E> （继承AbstractList类，实现List接口）

  • 方法摘要（标黄为常用方法）

    Modifier and Type 方法 描述
    void add​(int index, E element)
    在此列表中的指定位置插入指定的元素。
    boolean add​(E e)
    将指定的元素追加到此列表的末尾。
    boolean addAll​(int index, Collection<? extends E> c)
    将指定集合中的所有元素插入到此列表中，从指定的位置开始。
    boolean addAll​(Collection<? extends E> c)
    按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
    void clear​()
    从列表中删除所有元素。
    Object clone​()
    返回此 ArrayList实例的浅拷贝。
    boolean contains​(Object o)
    如果此列表包含指定的元素，则返回 true 。
    void ensureCapacity​(int minCapacity)
    如果需要，增加此 ArrayList实例的容量，以确保它至少能够容纳最小容量参数指定的元素数量。
    void forEach​(Consumer<? super E> action)
    对 Iterable每个元素执行给定的操作，直到所有元素都被处理或动作引发异常。
    E get​(int index)
    返回此列表中指定位置的元素。
    int indexOf​(Object o)
    返回此列表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1。
    boolean isEmpty​()
    如果此列表不包含元素，则返回 true 。
    Iterator<E> iterator​()
    以正确的顺序返回该列表中的元素的迭代器。
    int lastIndexOf​(Object o)
    返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。
    ListIterator<E> listIterator​()
    返回列表中的列表迭代器（按适当的顺序）。
    ListIterator<E> listIterator​(int index)
    从列表中的指定位置开始，返回列表中的元素（按正确顺序）的列表迭代器。
    E remove​(int index)
    删除该列表中指定位置的元素。
    boolean remove​(Object o)
    从列表中删除指定元素的第一个出现（如果存在）。
    boolean removeAll​(Collection<?> c)
    从此列表中删除指定集合中包含的所有元素。
    boolean removeIf​(Predicate<? super E> filter)
    删除满足给定谓词的此集合的所有元素。
    protected void removeRange​(int fromIndex, int toIndex)
    从此列表中删除所有索引为 fromIndex （包括）和 toIndex之间的元素。
    void replaceAll​(UnaryOperator<E> operator)
    将该列表的每个元素替换为将该运算符应用于该元素的结果。
    boolean retainAll​(Collection<?> c)
    仅保留此列表中包含在指定集合中的元素。
    E set​(int index, E element)
    用指定的元素替换此列表中指定位置的元素。
    int size​()
    返回此列表中的元素数。
    void sort​(Comparator<? super E> c)
    根据指定的Comparator引发的顺序排列此列表。
    Spliterator<E> spliterator​()
    在此列表中的元素上创建late-binding和故障快速 Spliterator 。
    List<E> subList​(int fromIndex, int toIndex)
    返回指定的 fromIndex （含）和 toIndex之间的列表部分的视图。
    Object[] toArray​()
    以正确的顺序（从第一个到最后一个元素）返回一个包含此列表中所有元素的数组。
    <T> T[] toArray​(T[] a)
    以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 返回的数组的运行时类型是指定数组的运行时类型。
    void trimToSize​()
    修改这个 ArrayList实例的容量是列表的当前大小。 

用法：

     public static void main(String[] args) {

         ArrayList<String> list = new ArrayList<String>();

         System.out.println(list.isEmpty());// 方法：isEmpty​()，如果此列表不包含元素，则返回 true。

         list.add(0, "A");// 方法：add​(int index, E element),在此列表中的指定位置插入指定的元素。给第一个位置加元素：A

         list.add(1, "B");// 给第二个位置加元素：B

         list.add("C");//方法：add​(E e), 将指定的元素追加到此列表的末尾。 继续追加元素：C

         list.add("D");//继续追加元素：D

         // 此时遍历一下，看看list的值是否成功加入。

         for (String value : list) {// 方法：forEach​(Consumer<? super E> action),对Iterable每个元素执行给定的操作，直到所有元素都被处理或动作引发异常。注意：此时使用Iterator迭代器遍历数值。

             System.out.println(value);//输出：A B C D，成功加入数值

         }

         System.out.println(list.size());//方法：size​() 返回此列表中的元素数。

         System.out.println(list.isEmpty());// 此时再用方法判断一下，因为已经有值所以返回False

         System.out.println(list.contains("A"));// 方法：contains​(Object o)，如果此列表包含指定的元素，则返回 true 。

         System.out.println(list.get(2));// 方法： get​(int index) 返回此列表中指定位置的元素。

         System.out.println(list.indexOf("B"));// 方法：indexOf​(Object o) 返回此列表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1。

         System.out.println(list.indexOf("E"));// 此时返回：-1

         System.out.println("--------分割线--------");

         list.remove(2);// 方法：remove​(int index) 删除该列表中指定位置的元素。

         // 此时遍历一下，看看list的值是否成功删除。

         for (String value : list) {

             System.out.println(value);

         }

         System.out.println("--------分割线--------");

         list.remove("D");// 方法：remove​(Object o) 从列表中删除指定元素的第一个出现（如果存在）。

         // 此时遍历一下，看看list的值是否成功删除。

         /*注意List中的remove方法不能和foreach（）连用，因为foreach使用Iterator迭代，和list中的方法无法识别，

         如果用list.remove()删除元素，会导致list数值和长度大小都发生改变，但此时Iterator无法知道此时，于是就会报错：ConcurrentModificationException*/

         for (String value : list) {

             System.out.println(value);

         }

         System.out.println("--------分割线--------");

         //为了后面演示方法，此时再假如几个值

         list.add("C");

         list.add("D");

         list.add("e");

         for (String value : list) {

             System.out.println(value);

         }

         System.out.println("--------分割线--------");

         list.set(4, "E");

         for (String value : list) {

             System.out.println(value);

         }

     }

补充一：ArrayList底层其实是动态数组，长度可变，源代码如下：

 private static final Object[] EMPTY_ELEMENTDATA = {};

 public boolean add(E e) {

         ensureCapacityInternal(size + 1);  // Increments modCount!!

         elementData[size++] = e;

         return true;

     }

     public void add(int index, E element) {

         rangeCheckForAdd(index);

         ensureCapacityInternal(size + 1);  // Increments modCount!!

         System.arraycopy(elementData, index, elementData, index + 1, size - index);

         elementData[index] = element;

         size++;

     }

补充二：ArrayList初始容量是：10，超过这个容量会扩容，扩容规则为：数组需要最小容量+（数组需要最小容量/2），即扩容 1.5倍，源代码如下：

     private static final int DEFAULT_CAPACITY = 10;

     public boolean add(E e) {

         ensureCapacityInternal(size + 1);

         elementData[size++] = e;

         return true;

     }

     private void ensureCapacityInternal(int minCapacity) {

         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

         }

         ensureExplicitCapacity(minCapacity);

     }

     private void ensureExplicitCapacity(int minCapacity) {

         modCount++;

         if (minCapacity - elementData.length > 0)

             grow(minCapacity);

     }

     private void grow(int minCapacity) {

         int oldCapacity = elementData.length;

         int newCapacity = oldCapacity + (oldCapacity >> 1);

         if (newCapacity - minCapacity < 0)

             newCapacity = minCapacity;

         if (newCapacity - MAX_ARRAY_SIZE > 0)

             newCapacity = hugeCapacity(minCapacity);

         elementData = Arrays.copyOf(elementData, newCapacity);

     }

ArrayList、Vector、LinkedList：

Linkedlist：

Linkedlist和ArrayList、Vector不一样的地方是，Linkedlist不是采用数组结构，而是链状结构，着重操作首位元素和末位元素，源代码如下：

     transient Node<E> first;

     transient Node<E> last;

     public void addFirst(E e) {

         linkFirst(e);

     }

     private void linkFirst(E e) {

         final Node<E> f = first;

         final Node<E> newNode = new Node<>(null, e, f);

         first = newNode;

         if (f == null)

             last = newNode;

         else

             f.prev = newNode;

         size++;

         modCount++;

     }

     public void addLast(E e) {

         linkLast(e);

     }

     void linkLast(E e) {

         final Node<E> l = last;

         final Node<E> newNode = new Node<>(l, e, null);

         last = newNode;

         if (l == null)

             first = newNode;

         else

             l.next = newNode;

         size++;

         modCount++;

     }

因为LinkedList着重操作首尾元素，所以增和删相对来说比较高效，而ArrayList和Vector底层是动态数组，存在数组索引（index），所以改和查比较高效。

Vector（已过期，基本不再使用）：

Vector和ArrayList，LinkedList不同的地方是，Vector是线程安全的List，因为它源代码中的方法基本都加上了关键词synchronized：

     public synchronized void addElement(E obj) {

         modCount++;

         ensureCapacityHelper(elementCount + 1);

         elementData[elementCount++] = obj;

     }

     public synchronized void insertElementAt(E obj, int index) {

         modCount++;

         if (index > elementCount) {

             throw new ArrayIndexOutOfBoundsException(index

                                                      + " > " + elementCount);

         }

         ensureCapacityHelper(elementCount + 1);

         System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);

         elementData[index] = obj;

         elementCount++;

     }

     public synchronized boolean removeElement(Object obj) {

         modCount++;

         int i = indexOf(obj);

         if (i >= 0) {

             removeElementAt(i);

             return true;

         }

         return false;

     }

     public synchronized E set(int index, E element) {

         if (index >= elementCount)

             throw new ArrayIndexOutOfBoundsException(index);

         E oldValue = elementData(index);

         elementData[index] = element;

         return oldValue;

     }

     public synchronized E get(int index) {

         if (index >= elementCount)

             throw new ArrayIndexOutOfBoundsException(index);

         return elementData(index);

     }

有没有其他线程安全的List？

1、java.util.Collections.SynchronizedList

        public static <T> List<T> synchronizedList (List < T > list) {

             return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(list) : new SynchronizedList<>(list));

         }

         SynchronizedList(List < E > list) {

             super(list);

             this.list = list;

         }

         public E get ( int index){

             synchronized (mutex) {

                 return list.get(index);

             }

         }

         public E set ( int index, E element){

             synchronized (mutex) {

                 return list.set(index, element);

             }

         }

         public void add ( int index, E element){

             synchronized (mutex) {

                 list.add(index, element);

             }

         }

         public E remove ( int index){

             synchronized (mutex) {

                 return list.remove(index);

             }

         }

1、Collection是集合的根接口，Collections是一个Java.util 包下的工具类。

2、Collections.synchronizedList返回的List和Vector一样，在方法上都有synchronized关键字加了锁，让线程变得安全，但同时性能会下降。

2、CopyOnWriteArrayList

CopyOnWriteArrayList是Java1.5加入的一个线程安全的变体ArrayList ，其中所有可变操作（ add ， set ，等等）通过对底层数组的最新副本实现。实现方法是：先复制一份List，然后上锁，然后进行增删改查的操作，操作过后再解锁。

     private transient volatile Object[] array;

     final Object[] getArray () {

             return array;

         }

     public CopyOnWriteArrayList() {

             setArray(new Object[0]);

         }

     public CopyOnWriteArrayList(E[]toCopyIn){

             setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));

         }

         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 set ( int index, E element){

             final ReentrantLock lock = this.lock;

             lock.lock();

             try {

                 Object[] elements = getArray();

                 E oldValue = get(elements, index);

                 if (oldValue != element) {

                     int len = elements.length;

                     Object[] newElements = Arrays.copyOf(elements, len);

                     newElements[index] = element;

                     setArray(newElements);

                 } else {

                     // Not quite a no-op; ensures volatile write semantics

                     setArray(elements);

                 }

                 return oldValue;

             } 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();

             }

         }

         public E get ( int index){

             final ReentrantLock lock = l.lock;

             lock.lock();

             try {

                 rangeCheck(index);

                 checkForComodification();

                 return l.get(index + offset);

             } finally {

                 lock.unlock();

             }

         }

最新文章

  1. VS2015墙内创建ionic2 【利用nrm更换源，完美！】
  2. SQL实用
  3. 一步一步开发Game服务器（三）加载脚本和服务器热更新（二）完整版
  4. socket的IO多路复用
  5. jquery工具方法parseJSON
  6. PHP try catch
  7. reshape2包--R高效数据处理包
  8. jsformat插件
  9. Corelocation及地图控件学习笔记
  10. Jquery 学习一
  11. [HIHO1051]补提交卡（枚举，贪心）
  12. 【spring教程之二】spring注射剂xml构造方法参数
  13. 【转】PHP代码审计
  14. 点击按钮，缩放图片（img.width、img.style.width、img.offsetWidth）
  15. 点击滚动图片JS部分代码以及css设置注意事项
  16. Ubuntu下解压压缩文件
  17. 关于data()获取不到得原因
  18. java 不定长参数
  19. Luogu P3168 [CQOI2015]任务查询系统
  20. Aspects源码解析（转载）

热门文章

  1. FFMPEG学习----遍历所支持的封装格式
  2. Spring基础(一)_控制反转(IOC)
  3. ubuntu+mysql+php+apache2+wordpress建站全记录
  4. jQuery初学者笔记 一
  5. sublime: javascript/css 的格式化
  6. caffe 指定GPU
  7. XDOJ
  8. layui父子页面方法互调
  9. 快速应用开发（RAD）平台 - 20 年的演进
  10. Spring Boot2 系列教程(三十二)Spring Boot 整合 Shiro