【集合】集合基础概念和 List

傷城~ 2022-11-26 08:55 225阅读 0赞

**目录**

一、集合汇总图

二、List、Set、Map、Queue

三、ArrayList 和 LinkedList

3.1 ArrayList

3.2 LinkedList

3.3 ArrayList 和 LinkedList 的对比

3.4 Vector

3.4.1 Vector 介绍

3.4.2 ArrayList 和 Vector 对比

3.5 实现 List 线程安全

--------------------

# 一、集合汇总图 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDE2MzMx_size_16_color_FFFFFF_t_70][]

# 二、List、Set、Map、Queue #

**● List**

List 是一个有序的容器，允许元素重复，可以插入 null，每个元素有索引，适合搜索和修改节点内容。常用的实现类有 ArrayList、LinkedList 和 Vector

**● Set**

Set 是一个无序的容器，不允许元素重复，即只能存入一个 NULL 元素。Set 常见的实现类有 HashSet、LinkedHashSet 和 TreeSet

**● Map**

Map 是一个键值对的集合，其中 Key 是无序且唯一的，但 Value 允许重复。Map 没有继承 Collection 接口，从 Map 中检索数据时，只要给出 Key，就能返回对应的 Value。常见的实现类有 HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

**● Queue**

一种先进先出的无阻塞结构，先进入的节点必须先弹出，是一种线程安全的数据结构。常用于高并发环境，常见的实现类有 BlockQueue、LinkedBlockQueue、SynchrousQueue、ConcurrentLinkedQueue

# 三、ArrayList 和 LinkedList #

## 3.1 ArrayList ##

ArrayList 类实现了一个动态扩容的数组，底层是通过数组实现的，允许快速随机存取。其适用于查找和修改数据，能够直接通过索引位置定位数据，但不适合插入、删除数据，插入和删除会导致数组重新排列。且 ArrayList 是线程不安全的。

**常用方法：**

<table> 
 <tbody> 
  <tr> 
   <td><strong>修饰符和返回类型</strong></td> 
   <td><strong>方法名和参数</strong></td> 
   <td><strong>方法描述</strong></td> 
  </tr> 
  <tr> 
   <td>void</td> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html#add-int-E-" rel="nofollow">add</a>(int&nbsp;index,&nbsp;<a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html" rel="nofollow">E</a>&nbsp;element)</td> 
   <td>将指定元素插入此列表中的指定位置</td> 
  </tr> 
  <tr> 
   <td>boolean</td> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html#add-E-" rel="nofollow">add</a>(<a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html" rel="nofollow">E</a>&nbsp;e)</td> 
   <td>将指定的元素追加到此列表的末尾</td> 
  </tr> 
  <tr> 
   <td>abstract&nbsp;<a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html" rel="nofollow">E</a></td> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html#get-int-" rel="nofollow">get</a>(int&nbsp;index)</td> 
   <td>返回此列表中指定位置的元素。</td> 
  </tr> 
  <tr> 
   <td>int</td> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html#indexOf-java.lang.Object-" rel="nofollow">indexOf</a>(<a href="https://docs.oracle.com/javase/9/docs/api/java/lang/Object.html" rel="nofollow">Object</a>&nbsp;o)</td> 
   <td>返回此列表中第一次出现的指定元素的下标，如果此列表不包含该元素，则返回-1。</td> 
  </tr> 
  <tr> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/Iterator.html" rel="nofollow">Iterator</a>&lt;<a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html" rel="nofollow">E</a>&gt;</td> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html#iterator--" rel="nofollow">iterator</a>()</td> 
   <td>以适当的顺序返回此列表中元素的迭代器。</td> 
  </tr> 
  <tr> 
   <td>int</td> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html#lastIndexOf-java.lang.Object-" rel="nofollow">lastIndexOf</a>(<a href="https://docs.oracle.com/javase/9/docs/api/java/lang/Object.html" rel="nofollow">Object</a>&nbsp;o)</td> 
   <td>返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回-1。</td> 
  </tr> 
  <tr> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html" rel="nofollow">E</a></td> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html#remove-int-" rel="nofollow">remove</a>(int&nbsp;index)</td> 
   <td>删除此列表中指定位置的元素。</td> 
  </tr> 
  <tr> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html" rel="nofollow">E</a></td> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html#set-int-E-" rel="nofollow">set</a>(int&nbsp;index,&nbsp;<a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html" rel="nofollow">E</a>&nbsp;element)</td> 
   <td>使用指定的元素替换此列表中指定位置的元素</td> 
  </tr> 
  <tr> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/List.html" rel="nofollow">List</a>&lt;<a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html" rel="nofollow">E</a>&gt;</td> 
   <td><a href="https://docs.oracle.com/javase/9/docs/api/java/util/AbstractList.html#subList-int-int-" rel="nofollow">subList</a>(int&nbsp;fromIndex, int&nbsp;toIndex)</td> 
   <td>返回一个新的集合，新集合元素是从原集合的<code>fromIndex（包含自身）到</code><code>toIndex（不包含自身）之间的元素</code>。</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>asList(T[] t)</td> 
   <td>数组转 List</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>toArray()</td> 
   <td>List 转数组</td> 
  </tr> 
 </tbody> 
</table>

**示例代码：**

public class TestArrayList {
        public static void main(String[] args) {
    
            List<String> list = new ArrayList<>();
            // 添加元素
            list.add("hello world");
            list.add("super man");
            list.add("good nice");
    
            // 获取元素
            System.out.println("get(0) = " + list.get(0));
    
            // 插入元素
            System.out.println("============ 插入元素 ============");
            list.add(1, "monday");
    
            // 迭代器遍历数组
            System.out.println("\n============ 迭代器遍历 ============");
            Iterator<String> iterator = list.iterator();
            while (iterator.hasNext()) {
                System.out.println(iterator.next());
            }
    
            // 替换第一个元素为 lowest
            list.set(0, "lowest");
    
            // 返回最后一次出现的元素的索引
            System.out.println(list.lastIndexOf("good nice"));
            System.out.println(list.indexOf("good nice"));
    
            // 删除第二个元素
            list.remove(1);
    
            System.out.println("\n============ 数组分割 ============");
            List<String> arrList = list.subList(0, 2);
            Iterator<String> iterator1 = arrList.iterator();
            while (iterator1.hasNext()) {
                System.out.println(iterator1.next());
            }
        }
    }

## 3.2 LinkedList ##

LinkedList 类实现了一个双向链表，可以对链表的头尾进行插入和删除操作。与 ArrayList 相比，LinkedList 更适合插入和删除。但 LinkedList 是线程不安全的。

**常用方法：**

**示例代码：**

public class StackTest {
        public static void main(String[] args) {
            LinkedList<String> list = new LinkedList<>();
    
            // 向头部添加元素
            list.addFirst("tom");
            list.addFirst("jerry");
    
            // 向尾部添加元素
            list.addLast("jack");
            list.addLast("petter");
    
            // 获取首尾元素
            System.out.println(list.getFirst());
            System.out.println(list.getLast());
    
            // 迭代器
            System.out.println("\n============ 迭代器遍历 ============");
            Iterator<String> iterator = list.iterator();
            while (iterator.hasNext()) {
                System.out.println(iterator.next());
            }
    
            // 移除第一个节点并返回被删除的这个元素
            System.out.println(list.removeFirst());
            // 移除最后一个节点并返回被删除的这个元素
            System.out.println(list.removeLast());
        }
    }

## 3.3 ArrayList 和 LinkedList 的对比 ##

**● 数据结构不同**

ArrayList 是用动态数组实现的，而 LinkedList 的本质是双向链表

**● 随机访问效率**

ArrayList 支持 RandomAccess 接口，能够以下标形式直接访问数据，速度更快。而 LinkedList 是一个链表，必须从头部或从尾部移动指针顺序查找

**● 插入和删除效率**

ArrayList 能够快速在末尾添加或删除数据，但在其他位置插入或删除数据效率不如 LinkedList，因为要重新调整数组的结构。而 LinkedList 能够通过调整指针指向，快速插入或删除节点

**● 线程安全**

ArrayList 和 LinkedList 都是不同步的，不保证线程安全

## 3.4 Vector ##

### 3.4.1 Vector 介绍 ###

Vector 和 ArrayList 大致相同，但 Vector 实现了方法同步，是线程安全的。实现方式是在内部使用了 synchronized 关键字。

由于实现了方法同步，效率不如 ArrayList

查看源码，可以发现 Vector 对关键的几个方法加上了 synchronized 关键字

![20200807232020769.png][]

![20200807232031869.png][]

### 3.4.2 ArrayList 和 Vector 对比 ###

**● 线程安全**

ArrayList 是非线程安全的，而 Vector 是线程安全的，它的关键方法都加上了 synchronized 关键字

**● 性能**

Vector 中增加了锁机制，性能不如 ArrayList

**● 扩容**

ArrayList 和 Vector 都会动态扩容，但 ArrayList 每次增加 50%，而 Vector 每次增加一倍

## 3.5 实现 List 线程安全 ##

即使存在 Vector 实现了线程安全，但其性能较差，还有其他更高效的方式实现线程安全

**● Collections.SynchronizedList**

SynchronizedList是Collections类的静态内部类，它能把所有 List 接口的实现类包装成线程安全的List，比 Vector 有更好的扩展性和兼容性。但在实际测试中，由于 Vector 和 Collections.SynchronizedList 都使用了 synchronizedList，实际两者性能没有相差很大。

**使用方式：**

List<String> list = Collections.synchronizedList(new ArrayList<>());

但注意，使用迭代器时需要开发者自己上锁，若骨架同步代码，则会在迭代中，其他的线程对容器的 add 或 remove 也会影响这个迭代效果。故需要在迭代代码外部加上 synchronized

synchronized (lists) {
    	
    	//获取迭代器
    	Iterator<String> iterator = synlist.iterator();
    	//遍历
    	while (iterator.hasNext()) {
    		System.out.println(iterator.next());
    	}
    }

● **CopyOnWriteArrayList**

Copy - On - Write ，可以知道，当写操作(add、remove、set)发生时，会进行 copy 操作，而读操作是读的复制前的旧容器，是无锁的，适用于写操作较少，读操作较多的情况。

可以看到写操作，使用 Arrays.copyOf() 来实现数组复制，是十分消耗性能的，故写操作效率较差

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDE2MzMx_size_16_color_FFFFFF_t_70 1][]

**缺点：**

由于 CopyOnWriteArrayList 的缺点较明显，一般较少使用，缺点有：

**内存占用高：**每次写操作都要将原容器拷贝一份，数据量大时，对内存压力大，且引起频繁 GC

**无法保证实时性：**由于 CopyOnWriteArrayList 的读操作是对旧容器，而写操作是对新容器，实现了读写分离，但无法保证读和写的强一致性。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDE2MzMx_size_16_color_FFFFFF_t_70]: /images/20221124/0c8d3e1f522e4c44a9a5a9e83a19b6c4.png
[20200807232020769.png]: /images/20221124/7d967410a03b458d871fe6b81a86d1b3.png
[20200807232031869.png]: /images/20221124/8ed0a2397baa43b0affcb58d8c6b4c88.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDE2MzMx_size_16_color_FFFFFF_t_70 1]: /images/20221124/0137dcaad6274b729adb84466fc8aeb5.png