Java 集合

Question

Java 的 java.util 包主要提供了以下四种类型的集合：

• List：一种有序列表的集合
• Set：一种保证没有重复元素的集合
• Map：一种通过键值（key-value）查找的映射表集合
• Queue: 先进先出（FIFO：First In First Out）的有序表

Java 访问集合总是通过统一的方式——迭代器（Iterator）来实现，它最明显的好处在于无需知道集合内部元素是按什么方式存储的，
ListIterator 是一个更强大的 Iterator 子类型，它只能由各种 List 类生成。 Iterator 只能向前移动，而 ListIterator 可以双向移动。

List

ArrayList

ArrayList 在内部使用了数组来存储所有元素。可以看作是能够自动增长容量的数组。例如，一个 ArrayList 拥有 5 个元素，实际数组大小为 6（即有一个空位）

LinkedList

通过链表实现了 List 接口。在 LinkedList 中，它的内部每个元素都指向下一个元素

LinkedList 是一个双链表,在添加和删除元素时具有比 ArrayList 更好的性能.但在 get 与 set 方面弱于 ArrayList.当然,这些对比都是指数据量很大或者操作很频繁(当插入的数据量很小时，两者区别不太大，当插入的数据量大时，大约在容量的 1/10 之前，LinkedList 会优于 ArrayList，在其后就劣与 ArrayList，且越靠近后面越差)

CopyOnWriteArrayList

juc 中提供的在并发编程中读多写少的场景下的 list 实现, 原理是任何修改操作，如 add、set、remove，都会拷贝原数组，修改后替换原来的数组，通过这种防御性的方式，实现另类的线程安全

Vector 线程安全的 List 实现，在方法上加入 synchronized。现在一般不推荐使用了，可用 Collections.synchronizedList 来包装集合使用

与 Array 的区别及转换

数组和 List 类似，也是有序结构，如果我们使用数组，在添加和删除元素的时候，会非常不方便。例如，从一个已有的数组{‘A’, ‘B’, ‘C’, ‘D’, ‘E’}中删除索引为 2 的元素

这个“删除”操作实际上是把’C’后面的元素依次往前挪一个位置，而“添加”操作实际上是把指定位置以后的元素都依次向后挪一个位置，腾出来的位置给新加的元素。这两种操作，用数组实现非常麻烦

list 转 array

Integer[] array = list.toArray(Integer[]::new);

//Integer[] array = list.toArray(new Integer[list.size()]);

array 转 list

Integer[] array = { 1, 2, 3 };
List<Integer> list = List.of(array);

//java 11 之前的版本，可以使用 Arrays.asList(T...) 方法把数组转换成 List

要注意的是，返回的 List 不一定就是 ArrayList 或者 LinkedList，因为 List 只是一个接口，如果我们调用 List.of()，它返回的是一个只读 List。对只读 List 调用 add()、remove() 方法会抛出 UnsupportedOperationException

如果对 List 对象做了任何修改，又不想让原始数组被修改，那么就应该在另一个集合中创建一个副本。

Set

Set 用于存储不重复的元素集合,如果我们只需要存储不重复的 key，并不需要存储映射的 value，那么就可以使用 Set。Set 实际上相当于只存储 key、不存储 value 的 Map。我们经常用 Set 用于去除重复元素

Set 接口并不保证有序，而 SortedSet 接口则保证元素是有序的：

HashSet

HashSet 是无序的，因为它实现了 Set 接口，并没有实现 SortedSet 接口。HashSet 内部通过维护一个 HashMap 来实现读取插入等功能

TreeSet

TreeSet 是有序的，因为它实现了 SortedSet 接口。使用 TreeSet 和使用 TreeMap 的要求一样，添加的元素必须正确实现 Comparable 接口，如果没有实现 Comparable 接口，那么创建 TreeSet 时必须传入一个 Comparator 对象, 可按照条件进行排序

LinkedHashSet

LinkedHashSet 底层使用 LinkedHashMap 来保存所有元素，它继承与 HashSet，其所有的方法操作上又与 HashSet 相同, LinkedHashSet 中的元素顺序是可以保证的，也就是说遍历序和插入序是一致的

LinkedHashSet 输出顺序是确定的，就是插入时的顺序

CopyOnWriteArraySet

juc 中提供的在并发编程中读多写少的场景下的 set 实现，内部维护了一个 CopyOnWriteArrayList，CopyOnWriteArraySet 相对 CopyOnWriteArrayList 用来存储不重复的对象

ConcurrentSkipListSet

juc 中提供的在并发编程中线程安全的有序的集合，适用于高并发的场景。ConcurrentSkipListMap 其实是 TreeMap 的并发版本，但实现是不一样的：ConcurrentSkipListSet 是通过 ConcurrentSkipListMap 实现的，而 TreeSet 是通过 TreeMap 实现的

Set 最常见的用途是测试归属性，可以很轻松地询问某个对象是否在一个 Set 中。因此，查找通常是 Set 最重要的操作，因此通常会选择 HashSet 实现，该实现针对快速查找进行了优化。

Map

map 相关的介绍在 java 多线程 6-ConcurrentHashMap 有体现，另外再补充一个 EnumMap

EnumMap

如果作为 key 的对象是 enum 类型，可以使用 Java 集合库提供的一种 EnumMap，它在内部以一个非常紧凑的数组存储 value，并且根据 enum 类型的 key 直接定位到内部数组的索引，并不需要计算 hashCode()，既保证速度，也不浪费空间

Queue

Queue

它和 List 的区别在于，List 可以在任意位置添加和删除元素，而 Queue 只有：

功能	抛异常	返回值
增（把元素添加到队列末尾)	add(e)	offer(e)
删（从队列头部取出元素)	remove()	poll()
查（或者说瞧，看队列中还有没有元素)	element()	peek()

两组方法的区别：

1. 如果队列空了，那 remove() 会抛异常，而 poll() 返回 null；element() 会抛异常，而 peek() 返回 null;
2. 有些队列（如 BlockingQueue) 会有容量的限制，当达到了最大的容量且不会扩容时，使用 add(e) 就会抛异常；而 offer(e) 返回 false;

所以使用时尽量前后统一，即前面使用了 add(e) 后面就使用 remove()，前面使用了 offer(e) 后面就使用 poll();

PriorityQueue

优先队列,它的出队顺序与元素的优先级有关（如排队时 vip 的处理)

PriorityQueue 默认按元素比较的顺序排序（必须实现 Comparable 接口），也可以通过 Comparator 自定义排序算法（元素就不必实现 Comparable 接口）

BlockingQueue

并发编程中经常用到了阻塞队列，如线程池的任务队列 java 多线程 2-线程池 ，它是基于 ReentrantLock

阻塞队列 BlockingQueue 就是为线程之间共享数据而设计的

• 当队列中没有数据的情况下，消费者端的所有线程都会被自动阻塞（挂起），直到有数据放入队列
• 当队列中填满数据的情况下，生产者端的所有线程都会被自动阻塞（挂起），直到队列中有空的位置，线程被自动唤醒

这也是我们在多线程环境下，为什么需要 BlockingQueue 的原因。作为 BlockingQueue 的使用者，我们再也不需要关心什么时候需要阻塞线程，什么时候需要唤醒线程，因为这一切 BlockingQueue 都给你一手包办了

Deque

双端队列（允许两头都进，两头都出)，那自然是有针对 First 端的操作和对 Last 端的操作：

功能	抛异常	返回值
增（把元素添加到队列头部/末尾)	addFirst(e)/ addLast(e)	offerFirst(e)/ offerLast(e)
删（从队列头部/末尾取出元素)	removeFirst()/ removeLast()	pollFirst()/ pollLast()
查（或者说瞧，看队列中还有没有元素)	getFirst()/ getLast()	peekFirst()/ peekLast()

LinkedList 即是 List，又是 Queue，还是 Deque,但是，在使用的时候，如果我们把它当作 List，就获取 List 的引用，如果我们把它当作 Queue，就获取 Queue 的引用

• getFirst() 和 element() 是相同的，它们都返回列表的头部（第一个元素）而并不删除它，如果 List 为空，则抛出 NoSuchElementException 异常。 peek() 方法与这两个方法只是稍有差异，它在列表为空时返回 null 。
• removeFirst() 和 remove() 也是相同的，它们删除并返回列表的头部元素，并在列表为空时抛出 NoSuchElementException 异常。 poll() 稍有差异，它在列表为空时返回 null 。
• addFirst() 在列表的开头插入一个元素。
• offer() 与 add() 和 addLast() 相同。 它们都在列表的尾部（末尾）添加一个元素。
• removeLast() 删除并返回列表的最后一个元素。

使用时一样，尽量用同一组方法

// 这是一个 List:
List<String> list = new LinkedList<>();
// 这是一个 Queue:
Queue<String> queue = new LinkedList<>();

注意

由于 Java 的集合设计非常久远，中间经历过大规模改进，我们要注意到有一小部分集合类是遗留类，不应该继续使用：

• Hashtable：一种线程安全的 Map 实现；
• Vector：一种线程安全的 List 实现；
• Stack：基于 Vector 实现的 LIFO 的栈(Java 6 添加了 ArrayDeque ，其中包含直接实现堆栈功能的方法)

如使用 ArrayDeque 封装下：

public class Stack<T> {
  private Deque<T> storage = new ArrayDeque<>();
  public void push(T v) { storage.push(v); }
  public T peek() { return storage.peek(); }
  public T pop() { return storage.pop(); }
  public boolean isEmpty() { return storage.isEmpty(); }
  @Override
  public String toString() {
    return storage.toString();
  }
}

//或者直接 Deque<Integer> stack = new ArrayDeque<>();

还有一小部分接口是遗留接口，也不应该继续使用：Enumeration：已被 Iterator 取代。

线程安全集合

interface	non-thread-safe	thread-safe
List	ArrayList	CopyOnWriteArrayList
Map	HashMap	ConcurrentHashMap
Set	HashSet / TreeSet	CopyOnWriteArraySet
Queue	ArrayDeque / LinkedList	ArrayBlockingQueue / LinkedBlockingQueue
Deque	ArrayDeque / LinkedList	LinkedBlockingDeque

java.util.Collections 工具类还提供了一个旧的线程安全集合转换器，可以这么用:

Map unsafeMap = new HashMap();
Map threadSafeMap = Collections.synchronizedMap(unsafeMap);

但是它实际上是用一个包装类包装了非线程安全的 Map，然后对所有读写方法都用 synchronized 加锁，这样获得的线程安全集合的性能比 java.util.concurrent 集合要低很多，一般不推荐使用。

例如:

private static class SynchronizedMap<K,V>
    implements Map<K,V>, Serializable {
    private final Map<K,V> m;     // Backing Map
    final Object      mutex;        // Object on which to synchronize
    // …
    public int size() {
        synchronized (mutex) {return m.size();}
    }
 // … 
}

Collections

java 提供了 Collections 方便集合的操作

• 排序

List<Integer> list = Arrays.asList(2, 4, 9, 3, 1, 5, 8, 6);

//排序
Collections.sort(list);
System.out.println("list: " + list);

//倒序
Collections.reverse(list);
System.out.println("list: " + list);

reverse 的意思是反转，而不是降序。只是将 list 集合原来的顺序反转了一下，反转并不意味着降序了。所以要想实现降序，可以先对集合进行升序，然后再反转，这样就降序了

使用场景

• 如果要经常随机访问，推荐 ArrayList
• 如果经常从列表的任意位置插入或者删除元素，推荐 LinkedList
• 如果需模拟堆栈（后进先出)，推荐 LinkedList
• 使用 map 如果不要求顺序，推荐 HashMap
• 使用 map 如果需要根据自己需要进行排序，推荐 TreeMap
• 使用 map 如果需要按照插入的顺序进行访问，又想保持快速访问的能力，推荐 LinkedHashMap
• 想要列表中不存在重复元素，推荐 set, 由于 set 的很多实现类实际上是 map 实现类的特殊存在(value 为空对象的 map), 故使用哪个实现类同 map 一样

不要在新代码中使用遗留类 Vector ，Hashtable 和 Stack(替代为 ArrayDeque)

面试常见问题

Vector 和 ArrayList 的区别是什么？

1. 线程安全问题，Vector 在很多方法上都添加了 synchronized 以保障线程安全，但线程安全的成本就是效率会降低，在某些系统里很容易成为瓶颈；
2. 扩容时 ArrayList 的新容量是原容量的1.5倍，而 Vector 默认则为两倍；

ArrayDeque 和 LinkedList 的区别有哪些？

1. ArrayDeque 是一个可扩容的数组，LinkedList 是链表结构；
2. ArrayDeque 里不可以存 null 值，
3. 但是 LinkedList 可以；ArrayDeque 在操作头尾端的增删操作时更高效，但是 LinkedList 只有在当要移除中间某个元素且已经找到了这个元素后的移除才是 O(1) 的；
4. ArrayDeque 在内存使用方面更高效。

所以，如果要实现普通的队列只要不是必须要存 null 值，推荐 ArrayDeque。当然如果需要兼容 Java6 之前的版本就得用 LinkedList，因为 ArrayDeque 是 Java6 才引入的。