Java集合总结

集合概述

所有的集合类都位于 java.util 包下。Java 5 还在java.util.concurrent包下提供了一些多线程支持的集合类。

与数组对比： 数组元素既可以是基本类型的值，也可以是对象（实际上是对象的引用变量）；而集合里只能保存对象（对象的引用变量）。

Java集合类主要由两个接口派生而来： Collection 和 Map （它们是Java集合框架的根接口）

对于Set, Queue, List 集合，常用的实现类有以下几种：HashSet, TreeSet, ArrayList, ArrayDeque（实现了Deque接口，上面的图片没有列出来）, LinkedList等。

对于Map集合，常用的实现类有以下几种：HashMap, TreeMap等。

Set集合

Set（无序、不能重复）

• Set里存放的对象是无序，不能重复的，集合中的对象不按特定的方式排序，只是简单地把对象加入集合中。
• Set集合不允许包含相同的元素。如果试图将两个相同的元素加入到一个Set集合中，则添加操作会失败，add()方法返回false，其新元素也不会被加入。

HashSet类

HashSet按Hash算法来存储集合中的元素，因此具有很好的存取和查找性能。
特点：

• 不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也有可能发生变化
• HashSet不是同步的。如果多个线程同时访问同一个HashSet，假设有两个或两个以上的线程修改集合时，则必须通过代码来保证其同步。
• 集合元素值可能是null

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

LinkedHashSet类

它是HashSet的子类。也是根据元素的hashCode来决定元素的存储位置，但它同时使用链表维护元素的次序。这样使得元素看起来是以插入顺序保存的。

性能略低于HashSet。但在迭代访问Set里的全部元素时将有很好的性能，因为它以链表来维护内部顺序。

TreeSet类

是SortedSet接口的实现类。它可以确保集合元素处于排序状态。它比HashSet多了一些方法。具体可以查阅API文档。
TreeSet采用红黑树的数据结构来存储集合元素。

TreeSet支持两种排序方法：自然排序和定制排序

自然排序

TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素之间的大小关系，然后将元素按升序排序，这种方式就是 自然排序。

Java中提供了一个Comparable接口，该接口定义了一个compareTo(Object obj)方法，该方法返回了一个整数值，实现该接口的类，就必须实现该方法，实现了该方法的类就可以比较大小。
当一个对象调用该方法与另一个对象进行比较时，例如obj1.compare(obj2),如果方法返回0，则表明这两个对象相等；如果返回一个正整数，则表明obj1大于obj2；如果返回一个负整数，则表明obj1小于obj2；
Java中的一些常用类已经实现了Comparable接口，并提供了比较大小的标准。
例如：
BigDecimal
Character
Boolean
String
Date
Time

注意：

• 如果试图将一个对象添加到TreeSet中，则该对象必须实现了Comparable接口，否则程序将会抛出异常。
• 向TreeSet集合中添加的应该是同一种类型的对象，否则也会引发ClassCastException异常

当把一个对象加入到TreeSet集合中时，TreeSet调用该对象的compareTo(Object obj)方法与容器中的其他对象比较大小，然后根据红黑树的数据结构找到它的存储位置。
如果两个对象通过compareTo(Object obj)方法比较相等，新对象将无法添加到TreeSet集合中。

注意一个问题，但需要把一个对象放入TreeSet中，需要重写equals方法，规则如下：如果两个对象通过equals()方法比较返回true时，这两个对象通过compareTo(Object obj)方法应返回0。

对于TreeSet集合，判断两个对象是否相等的标准是：
两个对象通过CompareTo(Object obj)方法比较是否返回0，如果返回0，则认为他们相等。

定制排序

放入TreeSet集合的对象需要实现Comparator接口，由该Comparator对象负责集合元素的排序逻辑。
由于Comparator是一个函数式接口，因此可以使用Lambda表达式来代替Comparator对象。

EnumSet类

是一个专为枚举类设计的集合类。EnumSet中的所有元素都必须是指定枚举类型的枚举值，该枚举类型在创建EnumSet时显示或者隐式地指定。
EnumSet中的集合元素也是有序的。以枚举值在Enum类中定义的顺序来决定集合元素的顺序。

各Set实现类的性能分析

HashSet的性能总是比TreeSet好（特别是常用的添加、查找元素等操作），因为TreeSet需要额外的红黑树算法维护集合元素的顺序。当需要一个保持排序的Set时，才应该使用TreeSet，否则都应该使用HashSet。

LinkedHashSet，对于普通的插入、删除操作，LinkedHashSet比HashSet要略微慢一点，这是由维护链表所带来的额外开销造成的，但由于有了链表，遍历LinkedHashSet会更快。

EnumSet是所有Set实现类中性能最好的，但它只能保存同一个枚举类的枚举值作为集合元素。

另外，HashSet、TreeSet、EnumSet都是线程不安全的。

List集合

List集合代表一个元素有序、可重复的集合。
集合中每个元素都有其对应的顺序索引，索引从0开始。
List集合默认按元素添加顺序设置元素的索引。

List关注的是索引，拥有一系列和索引相关的方法，查询速度快。因为往list集合里插入或删除数据时，会伴随着后面数据的移动，所有插入删除数据速度慢。

List判断两个对象相等的标准是：
List判断两个对象相等只要通过equals()方法比较返回true即可。

ArrayList和Vector实现类

ArrayList和Vector都是基于数组实现的类，它们封装了一个动态的、允许再分配的Object[]数组。
ArrayList和Vector对象使用initialCapacity参数来设置该数组的长度，当向集合中添加元素的个数超出该数组的长度，它们的initialCapacity会自动增加。
如果创建空的ArrayList和Vector集合时，不指定initialCapacity参数，则Object数组的默认长度是10。

如果向ArrayList和Vector集合中添加大量元素时，可使用ensureCapacity(int minCapacity)方法一次性地增加initialCapacity，可以减少分配的次数，从而提高性能。

ArrayList和Vector的区别：
Vector 是从JDK 1.0 出现的，线程安全。（不推荐使用它）
ArrayList是从JDK 1.2 出现的，线程不安全。

LinkedList类

它也是List接口的实现类。可以根据索引来随机访问集合中的元素。
它还实现了Deque接口，可以被当成双端队列来使用，因此既可以被当成栈来使用，也可以被当成队列使用。

例子如下：

public static void main(String[] args) {
		LinkedList books = new LinkedList();
		// 将字符串元素加入队列的尾巴
		books.offer("book 1");
		// 将字符串元素加入栈的顶部
		books.push("book 2");
		// 将字符串元素加入队列的顶部（相当于栈的顶部）
		books.offerFirst("book 3");
		// 以List的方式遍历集合
		for (int i = 0; i < books.size(); i++) {
			System.out.println(books.get(i));
		}
		// 访问并不删除栈顶的元素
		System.out.println(books.peekFirst());
		// 访问并不删除队列的最后一个元素
		System.out.println(books.peekLast());
		// 将栈顶的元素弹出
		System.out.println(books.pop());
		// 输出可以看到，第一个元素被删除
		System.out.println(books);
		// 访问并删除队列的最后一个元素
		System.out.println(books.pollLast());
		// 输出可以看到，最后一个元素被删除
		System.out.println(books);
	}

输出结果：

book 3
book 2
book 1
book 3
book 1
book 3
[book 2, book 1]
book 1
[book 2]

性能分析

由于数组是以一块连续的内存区来保存所有的元素，所以数组在随机访问时性能最好。所有的内部是以数组作为底层实现的集合在随机访问时性能都比较好。
所有的内部是以链表作为底层实现的集合在执行插入、删除操作时有较好的性能。

总体而言，ArrayList的性能比LinkedList的性能要好，因此大部分时候考虑使用ArrayList。

使用List集合时的建议：

• 如果需要遍历List集合元素，对于ArrayList、Vector集合，应该使用随机访问方式（get）来遍历集合，这样性能更好；对于LinkedList集合，则应该采用迭代器（Iterator）来遍历集合。
• 如果需要经常执行插入、删除操作来改变包含大量数据的List集合的大小，可以考虑使用LinkedList集合。使用ArrayList和Vector集合可能需要经常重新分配内部数组的大小，效果可能较差。
• 如果有多个线程需要同时访问List集合中的元素，可考虑使用Collections将集合包装成线程安全的集合。

Map集合

Map（键值对、键唯一、值不唯一）
Map集合中存储的是键值对，键不能重复，值可以重复。根据键得到值，对map集合遍历时先得到键的set集合，对set集合进行遍历，得到相应的值。

Map用于保存具有映射关系的数据。
key和value都可以是任何引用类型的数据。
Map的key不允许重复，即同一个Map对象的任何两个key通过equals方法比较总是返回false。

Java 8中又为Map添加了很多方法。
HashMap和Hashtable都是Map接口的典型实现类，

Hashtable和HashMap判断两个value相等的标准：
只要两个对象通过equals()方法比较返回true即可。

Properties类是Hashtable类的子类。

Hashtable

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

• 在java.util 包下，从JDK1.0 就开始出现。
• 是一个线程安全的Map实现。
• 底层数组+链表 实现
• Hashtable 中不允许使用 null 作为 key和value。如果试图把null值放入，会引发NullPointerException异常。
• 初始size为 11，扩容：newsize = oldSize*2 + 1

HashMap

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

• 在java.util 包下，从JDK1.2 开始出现。
• 是一个线程不安全的Map实现。
• 底层数组+链表 实现
• HashMap中允许使用 null 作为 key和value。（由于HashMap里的key不能重复，所以HashMap中最多只有一组key-value对的 key为null，可以多个value为null的元素）
• 初始size为 16，扩容：newsize = oldSize*2，size一定为2的n次幂

ConcurrentHashMap

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable

• 在java.util.concurrent 包下，从JDK 1.5 开始出现
• 线程安全
• 底层采用 分段的数组+链表实现
• ConcurrentHashMap 中不允许使用 null 作为 key和value。如果试图把null值放入，会引发NullPointerException异常。
• 它是Hashtable的替代，比Hashtable的扩展性更好
• 初始size为16

说明：

jdk1.7
ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。
不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。

jdk1.8
其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。

LinkedHashMap实现类

它是HashMap的子类。
使用双向链表来维护key-value对的次序。该链表负责维护Map的迭代顺序，迭代顺序与key-value对的插入顺序保持一致。

SortedMap接口和TreeMap实现类

Map接口派生出了一个SortedMap子接口，TreeMap是SortedMap的实现类。

TreeMap是一个红黑树结构，每个key-value对作为红黑树的一个节点。
TreeMap存储key-value对（节点）时，需要根据key对节点进行排序。
TreeMap可以保证所有的key-value对处于有序状态。

TreeMap也有两种排序方式：

• 自然排序： TreeMap的所有key必须实现Comparable接口，而且所有key应该是同一个类的对象，否则将会抛出ClassCaseException异常
• 定制排序： 创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中的所有key进行排序。注意，采用定制排序时，不要求Map的key实现Comparable接口。

TreeMap中判断两个key相等的标准是：
两个key通过compareTo()方法返回0，TreeMap则认为这两个key是相等的。

如果使用自定义类作为TreeMap的key，且想让TreeMap良好工作，则应该重写该类的equals()方法和compareTo()方法时应保持一致的返回结果：两个key通过equals()方法比较返回true时，它们通过compareTo()方法时应该返回0。如果equals()方法和compareTo()方法的返回结果不一致，则与Map接口的规则冲突。

工具类 Collections

Java 提供了一个操作Set、List、Map等集合的工具类：Collections。
该工具类提供了大量方法对集合元素进行排序、查询和修改等操作，还提供了将集合对象设置为不可变、对集合对象实现同步控制等方法。

排序

可查找API文档

查找、替换

可查找API文档

同步控制

Collections类中提供了多个synchronizedXxx()方法：该方法可以指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合的线程安全问题。

public static void main(String[] args) {
		// 下面程序创建了4个线程安全的集合类
		Collection c = Collections.synchronizedCollection(new ArrayList());

		List list = Collections.synchronizedList(new ArrayList());

		Set set = Collections.synchronizedSet(new HashSet());

		Map map = Collections.synchronizedMap(new HashMap());
	}

设置不可变集合

Collections通过如下三个方法来返回一个不可变类：

• emptyXxx()方法： 返回一个空的、不可变的集合对象
• singletonXxx()方法：返回一个只包含指定对象的（只有一个元素）、不可变的集合对象
• unmodifiableXxx()方法：返回指定集合对象的不可变视图

public static void main(String[] args) {
		// 创建一个空的，不可改变的List对象
		List unmodifiableList = Collections.emptyList();
		// 创建只有一个元素，且不可改变的Set对象
		Set unmodifiableSet = Collections.singleton("Test");

		Map students = new HashMap();
		students.put("1", "Tom");
		students.put("2", "Jerry");
		// 返回普通Map对象的不可改版本
		Map unmodifiableMap = Collections.unmodifiableMap(students);

		// 造成：java.lang.UnsupportedOperationException异常
		unmodifiableMap.put("3", "Bob");

	}

线程安全的集合类

• Vector：就比ArrayList多了个同步化机制（线程安全）

• Hashtable：就比HashMap多了个线程安全

• ConcurrentHashMap：是一种高效但是线程安全的集合。

• CopyOnWriteArrayList和CopyOnWriteArraySet：它们是加了写锁的ArrayList和ArraySet，锁住的是整个对象，但读操作可以并发执行。

其他常见操作

创建线程安全的List

1、Vector
这个是最常听到的线程安全的List实现，但是已经不常用了。
内部实现直接使用synchronized 关键字对 一些操作的方法加锁。性能很慢。
2、SynchronizedList
使用Collections.synchronizedList(list); 将list包装成SynchronizedList
需要注意的是SynchronizedList的add等操作加了锁，但是iterator()方法没有加锁，如果使用迭代器遍历的时候需要在外面手动加锁。
适用场景：当不需要使用iterator()并且对性能要求不高的场景。

SynchronizedList 和 Vector区别
1> SynchronizedList 有较好的扩展性，可以将ArrayList ，LinkedList等都改成同步的，而Vector底层只有数组的结构。
2> SynchronizedList 并没有对Iterator方法进行加锁，遍历时需要手动同步处理，Vector加锁了。
3> SynchronizedList 可以指定锁定的对象。
4> 扩容机制不一样SynchronizedList 1.5倍 ，Vector 2倍。
5、SynchronizedList使用同步代码块，锁的范围更小。Vector锁的方法。

3、CopyOnWriteArrayList
在写的时候加锁（ReentrantLock锁），读的时候不加锁，大大提升了读的速度。
添加元素的时候，先加锁，再复制替换操作，再释放锁。
适用场景：适用于读多写少的场景。

CopyOnWriteArraySet 这个集合也是在add时加锁，不过在增加元素前会先判断元素是否存在，不存在才会调add方法

集合转为数组

调用Collection的toArray()方法

数组转为List

可以借助 Arrays工具类。

String[] array = {"a", "b", "c"};
List<String> list = Arrays.asList(array);

String str = Arrays.toString(list.toArray());   
//[a, b, c]