Java 集合

集合提供了一个对象来在内部容纳若干其他的 Java 对象，并提供相应的访问接口。Java 的java.util 包主要提供了一下三种不同类型的集合：

List 有序列表的集合，可按插入顺序访问。，
Set 确保不可以插入重复元素的集合。
Map 通过 key-value 快速查找元素的集合。

Java的集合设计有两个特点：一是支持泛型，可以限制插入到集合中元素的数据类型；二是实现了接口与类的分离，以上三种均为接口而非具体的实现类。并且可以通过统一的迭代器方式进行访问。

我们尽量以接口而非具体的实现类来访问元素。

重要以下遗留类不应该被继续使用：

Hashtable, Vector, Stack, Enumeration<E>.

List

需要实现equals 方法。

ArrayList基于动态数组实现，支持随机访问。LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插⼊和删除元素。

List<Integer> array = new ArrayList<Integer>();
List<Integer> array2 = new LinkedList<Integer>();
List<Integer> array = List.of(1,2,3);
array.add(1);
array.add(1, 2); //(index, elem)
array.remove(1);//(elem)
int elem = array.get(1)//(index)
int n = array.size();

Map

HashMap 的 key必须实现equals() 和 hashCode() 方法。
有序 map 必须实现Comparable 接口；或者在声明时传入一个Comparator 接口，里面声明compare 函数
无序的 HashMap基于哈希表实现，有序的 TreeMap底层基于红⿊树实现。

//无序map
Map<String, Integer> mapper = new HashMap<>();
mapper.put(')', '(');
mapper.containsKey(ch);
mapper.get(key);
//遍历
for (String key : mapper.keySet());
for (Map.Entry<String, Integer> entry : mapper.entrySet());
for(String value: mapper.valueSet());
//有序map
Map<String, Integer> order_map = new TreeMap<>();

//基础的使用map计数出现次数
Map<Integer, Integer> mapper1 = new HashMap<Integer, Integer>();
        for(int num: arr){
            mapper1.put(num, occur.getOrDefault(num, 0) + 1);
        }

Set

只会存储 key 的值。
需要正确实现equals()和hashCode()方法。
有序的Set还要实现Comparable 接口；或者在声明时传入一个Comparator 接口，里面声明compare 函数
HashSet基于哈希表实现， TreeSet底层基于红黑树实现。

//无序Set
Set<String> set = new HashSet<>();
set.add("123");
set.contains("123");
set.remove("123");
int n = set.size();
//有序

Set<String> set = new TreeSet<>();

Queue

实现类为 LinkedList

Queue<int> que = new LinkedList<int>();
int n = que.size();
//throw exception
que.add();
que.remove();
que.element();

//return false or null
que.offer();
que.poll();
que.peel();

注意有两套方法，对应不同的情况。

PriorityQueue

放入的元素需要实现Comparable，或者提供一个Comparator对象来判断两个元素的顺序。
PriorityQueue：基于堆结构实现

// 实现类与接口分离
Queue<Integer> que = new PriorityQueue<Integer>();

//throw exception
que.add();
que.remove();
que.element();

//return false or null
que.offer();
que.poll();
que.peek();

Deque

deque 是用 LinkedList实现的接口，赋予了不同的功能。

Deque<Integer> que = new LinkedList<Integer>();

//throw exception
que.addLast(); //addFirst
que.removeLast(); //removeFirst
que.getLast(); // getFirst

//return false or null
que.offerLast(); //offerFirst
que.pollLast(); //pollLast
que.peekLast(); //peekLast

Stack

stack 是用Deque接口来模拟的，原来的stack被不推荐使用。

Deque<Character> stack = new LinkedList<>();
stack.isEmpty();
stack.pop();
stack.push(ch);
stack.peek()

并发容器

ConcurrentHashMap

ConcurrentHashMap 是线程安全的 Map。

ConcurrentHashMap采⽤锁分段技术，将整个 Hash数组分成几个小的 segment，在每个 segment分别上锁。在插⼊元素的时候就需要先找到应该插⼊到哪⼀个⽚segment，然后对该 segment上锁并操作。这样做明显减小了锁的粒度。

HashTable 同样是线程安全的，然而其使用了synchronized 关键字对 get 和put 等操作进行加锁，也就是每一次操作都会锁住整个 Hash表，每个线程独占哈希表，效率低下。

CopyOnWriteArrayList

线程安全的 List。所有可变操作（add，set等等）都是通过创建底层数组的新副本来实现的。当需要修改的时并不直接修改原有内容，⽽是对原有数据进⾏⼀次复制，将修改的内容写⼊副本。写完之后，再将修改完的副本替换原来的数据，这样就可以保证写操作不会影响读操作了。读取操作没有任何同步控制和锁操作，因此可以保证数据安全。

此外，写⼊操作在添加集合的时候加了锁，保证了同步，避免了多线程写的时候会复制出多个副本。