Java 集合类是一种特别有用的工具类，大致可分为Set、List、Queue、Map四种体系。

Set代表无序、不可重复的集合；
List代表有序、重复的集合；
Map代表具有映射关系的集合；
Queue代表队列集合。

一、集合概述

Java5在java.util.concurrent包下提供了一些多线程支持的集合类。

集合里只能保存对象。

Java的集合类主要由两个接口派生：Collection和Map。

Collection体系的继承树

上图中Deque还有一个实现类ArrayDeque，只是我没有找到合适的图。。

Map体系的继承树

最常用的集合类有：HashSet、TreeSet、ArrayDeque、ArrayList、LinkedList、HashMap、TreeMap

二、Collection和Iterator接口

Collection接口里面定义了如下操作集合元素的方法：

• boolean add(Object o)
• boolean addAll(Collection c)
• void clear()
• boolean contains(Object o)
• boolean isEmpty()
• Iterator iterator()
• boolean remove(Object o)
• boolean removeAll(Collection c)
• boolean retainAll(Collection c)
• int size()
• Object[] toArray()

使用lambda表达式遍历集合

Java8为Iterable接口新增了一个forEach(Consumer action)默认方法，该方法所需参数的类型是一个函数式接口，Iterable接口是Collection接口的父接口，Collection集合可以使用这个接口。

books.forEach(obj -> System.out.println(obj));

使用Java8增强的Iterator遍历集合元素

Iterator接口提供了4中方法：

• boolean hasNext()
• Object next()
• void remove()
• void forEachRemaining(Consumer action)

Iterator it = books.iterator();
while(it.hasNext){
    String book = (String)it.next();
}

Iterator必须依附于Collection对象。

使用Lambda表达式遍历Iterator

it.forEachRemaining(obj->System.out.println(obj));

使用foreach循环遍历集合元素

使用Java8新增的predicate操作集合

Java8为Collection集合新增了一个removeIf(Predicate filter)方法，批量删除符合filter的元素。

books.removeIf(obj->((String)obj).length()<10);

使用Java8新增的Stream操作集合

Java8新增了Stream，IntStream，LongStream，DoubleStream等流式API，这些API代表多个支持串行和并行聚集操作的元素。还有每个Stream提供了Builder，如Stream.Builder，IntStream.Builder，开发者可以通过这些Builder来创建对应的流。

独立使用Stream的步骤：

1. 使用Stream的builder类方法创建Builder
2. 重复调用Builder的add方法添加元素
3. 调用Builder的build方法获取对应的流
4. 调用Stream的聚集操作

Stream提供了大量的方法，有"中间方法"(生成另外一个流)和"末端方法"(对流的最终操作)。

常用的中间方法：

1. filter(Pridicate predicate)
2. mapToXxx(ToXxxFunction Mapper)
3. peek(Consumer action)
4. distict()
5. sorted()
6. limit(long maxSize)

常用的末端方法：

1. forEache(Consumer action)
2. toArray()
3. reduce()
4. min()
5. max()
6. count()
7. anyMatch(Predicate predicate)
8. allMatch(Predicate predicate)
9. noneMatch(Predicate predicate)
10. findFirst()
11. findAny()

Java8为Collection提供了一个stream默认方法。

三、Set集合

HashSet类

特点：

• 不能保证顺序
• 不能保证同步(多线程)
• 集合元素值可以是null

当向HashSet集合添加一个元素时，HashSet会调用该对象的hashCode()方法得到对象的hashCode值，然后根据该hashCode值决定该对象在HashSet中的存储位置。

HashSet集合判断两个元素相等的标准是两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法返回值也想等。

重写hashCode()方法的基本原则：

• 同一个对象多次调用应该返回相等的值
• 当两个对象通过equals()方法比较返回true时，他们的hashCode()值应该相等
• 对象中用于equals()比较的实例变量都应该用于计算hashCode

重写hashCode()的一般步骤：

1. 把对象内每个有意义的实例变量计算出一个int类型的hashCode值。
2. 用第一步计算的多个hashCode值组合计算出一个hashCode值返回

hashCode值的计算方式：

为了避免直接相加的偶然相等，可以通过为各实例变量的hashCode值乘以任意一个质数后再相加。

LinkedHashSet

也是根据hashCode插入元素，但是要维护元素的插入顺序，性能略低于HashSet。

TreeSet

TreeSet是SortedSet的实现类。有几个额外方法：

• Comparator comparator()
• Object first()
• Object last()
• Object lower(Object e)
• Object hight(Object e)
• SortedSet subSet(Object fromElement, Object toELement)
• SortedSet headSet(Object toElement)
• SortedSet tailSet(Object toElement)

TreeSet使用红黑树的数据结构来存储集合元素。支持自然排序和定制排序。

自然排序

调用集合的compareTo(Object obj)方法比较元素之间的大小关系，然后按升序排序。

Comparable接口里定义了一个compareTo(Object obj)方法。

如果试图把一个对象添加到TreSet，则该对象的类必须实现Comparable接口。

向TreeSet中插入元素时，第一个元素不会调用compareTo()方法

定制排序

创建TreeSet时传递给它一个Comparator对象即可，该接口是函数式接口，可以使用lambda表达式创建对象。

四、List集合

代表一个元素有序、可重复的集合，集合中每个元素都有其对应的顺序索引。

java8改进的List接口和ListIterator接口

List接口的方法：

• void add(int index, Object element)
• boolean addAll(int index, Collection c)
• Object get(int index)
• int indexOf(Object o)
• int lastIndexOf(Object o)
• Object remove(int index)
• Object set(int index, Object element)
• List subList(int fromIndex, int toIndex)
• void replaceAll(UnaryOperator operator)
• void sort(Comparator c)

List判断两个对象相等只要通过equals方法返回true即可。

List除了有Set的iterator()方法之外，还有listIterator()方法，该方法返回一个ListIterator对象，ListIterator接口继承于Iterator接口。ListIterator相较于Iterator多了如下方法：

• boolean hasPrevious()
• Object previous()
• void add(Object o)

ArrayList和Vector实现类

使用initialCapacity参数设置该数组的长度。如果需要向集合中添加大量元素，可使用ensureCapacity(int minCapacity)方法一次性地增加容量，可以减少重分配的次数，提高性能。

可以在创建的时候指定initialCapacity，还可以通过一下两个方式重新分配Object[]数组，不指定的话默认长度为10：

• void ensureCapacity(int minCapacity)
• void trimToSize()

ArrayList和Vector用法几乎完全相同，Vector是一个古老的集合，里面有重复的方法。

通常尽量少用Vector。

Vector是线程安全的，但效率低，ArrayList不是线程安全的，java.util.Collections类可以将ArrayList变成线程安全的。推荐使用ArrayList。

Stack是Vector的子类。有以下方法：

• Object peek()
• Object pop()
• void push(Object item)

Stack继承于Vector，古老的类，线程安全，但是效率低，不建议使用。可以使用后来的ArrayDeque类代替。

固定长度的List

Arrays类提供了asList(Object... a)方法，可以把一个数组或指定个数的对象转换成List集合。这个List集合既不是ArrayList实现类的实例，也不是Vector实现类的实例，而是Arrays的内部类ArrayList的实例。

Arrays.ArrayList是一个固定长度的List集合，只能遍历，不可增加修改。

五、Queue集合

Queue接口中定义的方法：

• void add(Object e)
• Object element():获取队列头元素，但不删除
• boolean offer(Object e):加入元素，比add()好
• Object peek():获取头元素，如果为空，返回null
• Object poll():获取头元素，并删除，如果为空，返回null
• Object remove():获取头元素，并删除

Deque是Queue的子接口，代表双端队列。有ArrayDeque和LinkedList两个实现类。

PriorityQueue实现类

内部排序。

Deque接口和ArrayDeque实现类

Deque接口方法：

• void addFirst(Object e)
• void addLast(Object e)
• Iterator descendingIterator()
• Object getFirst()
• Object getLast()
• boolean offerFirst(Object e)
• boolean offerLast(Object e)
• Object peekFirst()
• Object peekLast()
• Object pollFirst()
• Object pollLast()
• Object pop()
• void push()
• Object removeFirst()
• Object removeFirstOccurrence(Object o)
• Object removeLast()
• Object removeLastOccurrence(Object o)

LinkedList实现类

LinkedList即可以当成双端队列，也可以当成栈使用，也可以当成队列使用。

ArrayList和ArrayDeque内部使用数组实现，而LinkedList内部使用链表实现。

各种线性表的性能分析

整体来说ArrayList比LinkedList性能好。

1. 如果需要遍历List，对于ArrayList、Vector集合，应该使用随机访问方法（get()）遍历；对于LinkedList则应该采用Iterator遍历。
2. 经常插入删除，考虑使用LinkedList
3. 多个线程，可以使用Collections将集合包装成线程安全的集合。

六、Java8增强的Map集合

从Java源码看，Java先实现了Map，然后通过包装一个所有value都为null的Map就实现了Set集合。

Map的实现子类和子接口中key集的存储形式和对应Set集合中元素的存储形式完全相同。

方法：

• void clear()
• boolean containsKey(Object key)
• boolean containsValue(Object value)
• Set entrySet()

返回Map中包含的key-value对所组成的Set集合，每个集合元素都是Map.Entry对象

• Object get(Object key)
• boolean isEmpty()
• Set keySet()
• Object put(Object key, Object value)
• void putAll(Map m)
• Object remove(Object key, Object value)
• int size()
• Collection values()

Map接口中有一个内部类Entry，该类封装了key-value键值对。Entry包含如下三个方法：

• Object getKey()
• Object getValue()
• Object setValue(V value)

java8新增的方法

• Object compute(Object key, BiFunction remappingFunction)
• Object computeIfAbsent(Object key, Function mappingFunction)
• Object computeIfPresent(Object key, BiFunction remappingFunction)
• void forEach(BiConsumer action)
• Object getOrDefault(Object key, V default Value)
• Object merge(Object key, Object value, BiFunction remappingFunction)
• Object putIfAbsent(Object key, Object value)
• Object replace(Object key, Object value)
• boolean replace(K key, V oldValue, V newValue)
• replaceA(BiFunction Function)

java8改进的Hash Map和Hashtable实现类

hashtable和vector同一时期出现。

区别：

1. Hashtable是线程安全的
2. Hashtable不允许null作为key和value

用作key的对象必须实现hashcode()和equals()方法

与HashSet类似，尽量不要使用可变对象作为HashMap、Hashtable的key。

LinkedHashMap

使用双向链表维护key-value对的次序。

使用Properties读写属性文件

Properties是Hashtable的子类。

• String getProperty(String key)
• String getProperty(String key, String defaultValue)
• String setProperty(String key, String value)
• void load(InputStream inStream)
• void store(OutputStream out, String comments)

SortedMap接口和TreeMap实现类

Map性能分析

HashMap和Hashtable实现机制相同，但由于Hashtable是一个古老的、线程安全的集合，HashMap通常比Hashtable快。

TreeMap更慢，但是其key-value是有序状态，无需专门的排序操作。可以调用keySet()，再用toArray()方法，再用Arrays的binarySearch()方法快速查找对象。

七、操作集合的工具类Collections

排序

• void reverse(List list)
• void shuffle(List list)
• void sort(List list)
• void sort(List list, Comparator c)
• void swap(List list, int i, int j)
• void rotate(List list, int distance)

查找、替换操作

• int binarySearch(List list, Object key)
• Object Max(Collection coll)
• Object Max(Collection coll, Comparator c)
• Object Min(Collection coll)
• Object Min(Collection coll, Comparator c)
• void fill(List list, Object obj)
• int frequency(Collection c, Object o)
• int indexOfSubList(List source, List target)
• int lastIndexOfSubList(List source, List target)
• boolean replaceAll(List list, Object oldVal, Object newVal)

同步控制

synchronizaedXxx()方法。

设置不可变集合

• emptyXxx()
• singletonXxx()
• unmodifiableXxx()

九、繁琐的接口Enumeration

该接口是Iterator接口的古老版本。

不要使用，使用Iterator代替