1，Java集合Collection接口及List子类

1.1，集合框架简介

• 集合可以看作是一种容器，用来存储对象信息。
• 所有集合类都位于java.util包下，但支持多线程安全的集合类位于java.util.concurrent包下。
• Java集合类主要由两个根接口Collection和Map派生出来的，Collection派生出了三个子接口：List，Set，Queue（Java5新增的队列），因此Java集合大致也可分成List，Set，Queue，Map四种接口体系。
• List代表了有序可重复集合，可直接根据元素的索引来访问；set代表无序不可重复集合，只能根据元素自身来访问；Queue是队列集合；Map代表的是存储key-value对的集合，可根据元素的key来访问value。
• 集合和数组的区别
  1. 数组声明了它容纳的元素的类型，而集合不声明。
  2. 数组是静态的，一个数组实例具有固定的大小，一旦创建了就无法改变容量了。而集合是可以动态扩展容量，可以根据需要动态改变大小，集合提供更多的成员方法，能满足更多的需求。
  3. 数组的存放类型只能是一种（基本类型/引用类型），集合存放的类型可以不是一种（不加泛型时添加的类型是Object）。

1.2，Collection接口和Map接口

• Collection集合框架图

• 

• Map集合框架图

• 

1.3，List接口和简介

• List是有序集合，可以通过下标访问集合中的元素。
• List允许重复值，允许有多个null值。
• List接口是Collection接口的子类。
• List的实现类有LinkedList，ArrayList，Vector，Stack。
• List接口的常用方法：
  1. 增加元素方法：
     • add(Object e)：向集合末尾处，添加指定元素。
     • add(int index,Object e)：向集合指定索引处，添加指定元素，原有元素依次后移。
  2. 删除元素
     • remove(Object e)：将指定元素对象，从集合中删除，返回值为被删除的元素。
     • remove(int index)：将指定索引处的元素，从集合中删除，返回值为被删除的元素。
  3. 替换元素方法
     • set(int index,Object e)：将指定索引处的元素，替换成指定的元素，返回值为替换前的元素。
  4. 查询元素方法
     • get(int index)：获取指定索引处的元素，并返回该元素。

1.4，ArrayList子类和API

• ArrayList是List接口的常用实现类，底层采用数组实现，其容量能自动增长。

• ArrayList特点是随机访问速度快，插入和移除性能较差。

• ArrayList支持null元素。

• ArrayList是有序的。

• ArrayList元素可以重复。

• ArrayList线程不安全。

• ArrayList容量是自动扩容的，其初始容量为10。扩容步骤为：

  1. 找到初始数组。
  2. 创建一个比原数组容量大的新数组。
  3. 数组中的元素搬到新的数组。
  4. 将新的元素也放进新数组，最后将新数组赋给原数组即可。

• ArrayList常用方法

  1. 创建：ArrayList al=new ArrayList();
  2. 添加：add(Object obj);
  3. 查询集合长度：size();
  4. 删除：remove(Object obj); remove(int index);
  5. 清空：clear();
  6. 判断存在：contains(Object obj);
  7. 判断是否为空：isEmpty();
  8. 取交集：retainAll(Collection);
  9. 删交集：removeAll(Collection);

• ArrayList常用方法案例：

import java.util.ArrayList;

public class Test
{
    public static void main(String[] args)
    {
        //创建集合对象
        ArrayList<String> list = new ArrayList<>();
        //添加元素
        list.add("hello");
        list.add("world");
        list.add("java");
        //public E get(int index)：返回指定索引处的元素
        System.out.println("get:" + list.get(0));
        System.out.println("get:" + list.get(1));
        System.out.println("get:" + list.get(2));
        //public int size()：返回集合中的元素个数
        System.out.println("size:" + list.size());
        //public E remove(int index):删除指定索引处的元素，返回被删除的元素
        System.out.println("remove:" + list.remove(0));
        //遍历输出
        System.out.println("size:" + list.size());
        for (String s : list)
        {
            System.out.println(s);
        }
    }
    /*
    * 输出结果
    *   get:hello
        get:world
        get:java
        size:3
        remove:hello
        size:2
        world
        java
    * */
}

• ArrayList线程非安全

import java.util.ArrayList;
import java.util.List;
import java.util.UUID;

public class Test
{
    public static void main(String[] args)
    {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < 30; i++)
        {
            new Thread(new Runnable()
            {
                @Override
                public void run()
                {
                    list.add(UUID.randomUUID().toString().substring(1, 8));
                    System.out.println(list);
                }
            }).start();
        }
    }
    /*
     * Exception in thread "Thread-8" Exception in thread "Thread-13" Exception in thread "Thread-19" Exception in thread "Thread-25" Exception in thread "Thread-27" Exception in thread "Thread-28" java.util.ConcurrentModificationException
     * */
}

• ArrayList执行遍历快，添加删除慢

import java.util.ArrayList;

/*
 * 执行遍历
 * */
public class Test
{
    static long execTime(ArrayList lists)
    {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < lists.size(); i++)
        {
            lists.get(i);
        }
        long endTime = System.currentTimeMillis();
        return endTime - startTime;
    }

    public static void main(String[] args)
    {
        ArrayList<Object> arrayList = new ArrayList<>();
        for (int i = 0; i < 50000; i++)
        {
            arrayList.add(i);
        }
        long time = execTime(arrayList);
        System.out.println("ArrayList执行遍历的时间：" + time);
    }
    /*
     * 输出结果
     * ArrayList执行遍历的时间：2
     * */
}

import java.util.ArrayList;

public class Test1
{
    static long execTime(ArrayList list)
    {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 50000; i++)
        {
            list.add(0, i);
        }
        long endTime = System.currentTimeMillis();
        return endTime - startTime;
    }

    public static void main(String[] args)
    {
        ArrayList<Object> list = new ArrayList<>();
        long time = execTime(list);
        System.out.println("ArrayList执行添加的时间：" + time);
    }
    /*
     * 输出结果
     * ArrayList执行添加的时间：92
     * */
}

1.5，LinkedList子类和API

• LinkedList底层的数据结构是基于双向循环链表。

• LinkedList是有序，可以重复，非同步的。

• LinkedList最经常使用的两种数据结构：栈和队列。

• LinkedList和ArrayList区别：

  1. 时间复杂度
     • 对于随机访问，ArrayList通过索引快速定位元素位置，而LinkedList需要对列表中元素挨个查找，所以ArrayList快于LinkedList。
     • 对于删除插入操作，ArrayList需要对数组重新排序，而且在数组装满的时候要将所有的数组重新装入一个新的数组，LinkedList只需添加一项Entry对象，所以LinkedList快于ArrayList。
  2. 空间复杂度
     • LinkedList需要更多的内存，因为ArrayList的每个索引的位置是实际的数据，而LinkedList中的每个节点中存储的是实际的数据和前后节点的位置。

• LinkedList底层是双向链表

• 

• LinkedList常用方法案例：

import java.util.LinkedList;

public class Test
{
    public static void main(String[] args)
    {
        //创建集合LinkedList对象
        LinkedList<Object> linkedList = new LinkedList<>();
        //添加元素
        linkedList.add("hello");
        linkedList.add("world");
        linkedList.add("java");
        //添加到第一个位置
        linkedList.addFirst("android");
        System.out.println(linkedList);
        linkedList.addLast("harmonyos");
        System.out.println(linkedList);
        System.out.println(linkedList.removeFirst());
        System.out.println(linkedList.removeLast());
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
        System.out.println(linkedList);
    }
    /*
    * 输出结果
    *   [android, hello, world, java]
        [android, hello, world, java, harmonyos]
        android
        harmonyos
        hello
        java
        [hello, world, java]
    * */
}

• LinkedList栈的特性：

import java.util.LinkedList;

public class Test
{
    public static void main(String[] args)
    {
        LinkedList<Object> linkedList = new LinkedList<>();
        linkedList.push(10);
        linkedList.push(20);
        linkedList.push(30);
        linkedList.push(40);
        while (!linkedList.isEmpty())
        {
            System.out.println(linkedList.pop());
        }
    }
    /*
    * 由输出结果得知栈的数据结构是 后进先出
    *   40
        30
        20
        10
    * */
}

• LinkedList执行遍历慢，增加和删除快

import java.util.LinkedList;

public class Test
{
    static long execTime(LinkedList list)
    {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 50000; i++)
        {
            list.add(0, i);
        }
        long endTime = System.currentTimeMillis();
        return endTime - startTime;
    }

    public static void main(String[] args)
    {
        LinkedList<Object> list = new LinkedList<>();
        long time = execTime(list);
        System.out.println("LinkedList执行添加的时间：" + time);
    }
    /*
     * 输出结果
     * LinkedList执行添加的时间：9
     * */
}

import java.util.LinkedList;

public class Test1
{
    static long execTime(LinkedList 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 void main(String[] args)
    {
        LinkedList<Object> list = new LinkedList<>();
        for (int i = 0; i < 50000; i++)
        {
            list.add(i);
        }
        long time = execTime(list);
        System.out.println("LinkedList执行遍历的时间：" + time);
    }
    /*
     * 输出结果
     * LinkedList执行遍历的时间：1567
     * */
}

1.6，Vector子类和API

• Vector类称作向量类，它实现了动态数组，用于元素数量变化的对象数组。

• Vector集合也是以0开始的下标表示元素的开始。

• 当Vector对象创建后，数组的元素个数会随着Vector集合中元素个数的增大和减少而自动变化。

• Vector类中的大多数方法是同步的，使用synchronized修饰的，Vector是线程安全的。

• Vector类常用操作方法：

  1. boolean add(Object e)将指定元素添加到此向量的末尾。
  2. Object remove(int index)删除指定索引位置的元素，并返回删除后的元素。
  3. Object set(int index,Object element)修改当前集合中制定索引位置的元素，返回被替换的旧元素。
  4. int size()返回当前集合中存储几个元素。
  5. boolean isEmpty()判断当前集合中元素个数是否为0.
  6. Object get(int index)查询指定位置的元素。
  7. Object[] toArray()把集合对象转换为Object数组。

• Vector类常用操作案例：

import java.util.Enumeration;
import java.util.Vector;

public class Test
{
    public static void main(String[] args)
    {
        Vector<Object> vector = new Vector<>();

        vector.add("hello");
        vector.add("world");
        vector.add("java");

        for (int i = 0; i < vector.size(); i++)
        {
            String s = (String) vector.get(i);
            System.out.println(s);
        }
        System.out.println("-------------");
        for (Enumeration enumeration = vector.elements(); enumeration.hasMoreElements(); )
        {
            String s = (String) enumeration.nextElement();//返回的是实现类的对象
            System.out.println(s);
        }
    }
    /*
    * 输出结果
    *   hello
        world
        java
        -------------
        hello
        world
        java
    * */
}

1.7，Stack栈和操作

• Stack是栈，它的特性是：先进后出，后进先出。

• Java工具包中的Stack是继承于Vector的，意味着Vector拥有的属性和功能，Stack都拥有。

• Stack底层实际上也是通过数组去实现的，具体操作如下：

  1. 执行push时（将元素推入栈中），是通过将元素追加的数组的末尾中。
  2. 执行peek时（取出栈顶元素，不执行删除），是返回数组末尾的元素。
  3. 执行pop时（取出栈顶元素，并将该元素从栈中删除），是取出数组末尾的元素，然后将该元素从数组中删除。

• Stack栈的操作案例

import java.util.Stack;

class MyObj
{
    Integer id;
    String name;

    public MyObj(Integer id, String name)
    {
        this.id = id;
        this.name = name;
    }
}

public class Test
{
    public static void main(String[] args)
    {
        System.out.println("Integer 类型：");
        Stack<Object> st = new Stack<>();
        st.push(1);
        st.push(2);
        System.out.println("添加元素之后，栈顶元素：" + st.peek() + "，是否为空：" + st.isEmpty() + "，栈1内所有元素：" + st);
        st.pop();
        st.pop();
        System.out.println("移除元素之后");
        System.out.println("是否为空：" + st.empty());

        System.out.println();
        System.out.println("自定义类型：");
        Stack<MyObj> stack = new Stack<>();
        stack.push(new MyObj(3, "自定义对象3"));
        stack.push(new MyObj(4, "自定义对象4"));
        System.out.println("添加元素之后，栈顶元素：" + stack.peek().name + "，是否为空：" + stack.empty());
        stack.pop();
        stack.pop();
        System.out.println("移除元素之后");
        System.out.println("是否为空：" + stack.empty());
    }
    /*
    * 输出结果
    *   Integer 类型：
        添加元素之后，栈顶元素：2，是否为空：false，栈1内所有元素：[1, 2]
        移除元素之后
        是否为空：true
        
        自定义类型：
        添加元素之后，栈顶元素：自定义对象4，是否为空：false
        移除元素之后
        是否为空：true
    * */
}

1.8，Collections工具类及API

• Collections是一个操作Set，List，Map等集合的工具类。

• Collections中提供了一系列静态的方法对集合元素进行排序，查询和修改等操作，还提供了对集合对象设置不可变，对集合对象实现同步控制等方法。

• Collections中常用方法，都是静态方法：

  1. reverse(List)：反转List中元素的顺序。
  2. shuffle(List)：对List集合元素进行随机排序。
  3. sort(List)：根据元素的自然顺序对指定List集合元素按升序排序。
  4. swap(List,int,int)：将指定List集合中的 i 处元素和 j 处元素进行交换。
  5. int frequency(Collection,Object)：返回指定集合中指定元素的出现次数。
  6. void copy(List dest,List src)：将src中的内容复制到dest中。
  7. boolean replaceAll(List list,Object oldVal,Object newVal)：使用新值替换List对象的所有旧值。

• Collections的工具类方法案例：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Test
{
    public static void exec()
    {
        List list = new ArrayList<>();
        list.add(123);
        list.add(43);
        list.add(765);
        list.add(765);
        list.add(-97);
        list.add(0);

        Collections.reverse(list);
        System.out.println(list);//[0, -97, 765, 765, 43, 123]

        Collections.shuffle(list);
        System.out.println(list);//[-97, 0, 123, 765, 43, 765]

        Collections.sort(list);
        System.out.println(list);//[-97, 0, 43, 123, 765, 765]

        Collections.swap(list, 1, 2);
        System.out.println(list);//[-97, 43, 0, 123, 765, 765]

        int frequency = Collections.frequency(list, 123);
        System.out.println(list);//[-97, 43, 0, 123, 765, 765]
        System.out.println(frequency);//1
    }

    public static void main(String[] args)
    {
        exec();
    }
}

• Collections的工具类方法案例：

import java.util.ArrayList;
import java.util.List;
import java.util.UUID;

public class Test
{
    public static void main(String[] args)
    {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < 30; i++)
        {
            new Thread(() ->
            {
                list.add(UUID.randomUUID().toString().substring(0, 4));
                System.out.println(list);
            }).start();
        }
    }
    /*
     * ArrayList线程不安全
     * Exception in thread "Thread-0" Exception in thread "Thread-7" Exception in thread "Thread-17" Exception in thread "Thread-27" Exception in thread "Thread-23" Exception in thread "Thread-29" java.util.ConcurrentModificationException
     * */
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.UUID;

public class Test1
{
    public static void main(String[] args)
    {
        List<String> list = Collections.synchronizedList(new ArrayList<>());
        for (int i = 0; i < 50; i++)
        {
            new Thread(() ->
            {
                list.add(UUID.randomUUID().toString().substring(0, 4));
                System.out.println(list);
            }, String.valueOf(i)).start();
        }
    }
    /*
    * 通过Collections的同步安全方法，保证ArrayList线程安全
    *   [81bb, 7b5d]
        [81bb, 7b5d, cc8d, cfa2, b294, e02c, 6938]
        [81bb, 7b5d, cc8d, cfa2, b294, e02c]
        [81bb, 7b5d, cc8d, cfa2, b294, e02c, 6938, 212f, b53a, 1431]
        [81bb, 7b5d, cc8d]
    * */
}