java 集合详细介绍

集合框架介绍

Java集合工具包位于Java.util包下，包含了很多常用的数据结构，如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分：List列表、Set集合、Map映射、迭代器（Iterator、Enumeration）、工具类（Arrays、Collections）。

Java集合类的整体框架如下：

Collection是List、Set等集合高度抽象出来的接口，它包含了这些集合的基本操作，它主要又分为两大部分：List和Set。

List 类：

​ List接口通常表示一个列表（数组、队列、链表、栈等），其中的元素可以重复，常用实现类为ArrayList和LinkedList，另外还有不常用的Vector。另外，LinkedList还是实现了Queue接口，因此也可以作为队列使用。

Set接口

​ Set接口通常表示一个集合，其中的元素不允许重复（通过hashcode和equals函数保证），常用实现类有HashSet和TreeSet，HashSet是通过Map中的HashMap实现的，而TreeSet是通过Map中的TreeMap实现的。另外，TreeSet还实现了SortedSet接口，因此是有序的集合（集合中的元素要实现Comparable接口，并覆写Compartor函数才行）。 我们看到，抽象类AbstractCollection、AbstractList和AbstractSet分别实现了Collection、List和Set接口，这就是在Java集合框架中用的很多的适配器设计模式，用这些抽象类去实现接口，在抽象类中实现接口中的若干或全部方法，这样下面的一些类只需直接继承该抽象类，并实现自己需要的方法即可，而不用实现接口中的全部抽象方法。

Map接口

Map是一个映射接口，其中的每个元素都是一个key-value键值对，同样抽象类AbstractMap通过适配器模式实现了Map接口中的大部分函数，TreeMap、HashMap、WeakHashMap等实现类都通过继承AbstractMap来实现，另外，不常用的HashTable直接实现了Map接口，它和Vector都是JDK1.0就引入的集合类。

Iterator迭代器

Iterator是遍历集合的迭代器（不能遍历Map，只用来遍历Collection），Collection的实现类都实现了iterator()函数，它返回一个Iterator对象，用来遍历集合，ListIterator则专门用来遍历List。而Enumeration则是JDK1.0时引入的，作用与Iterator相同，但它的功能比Iterator要少，它只能再Hashtable、Vector和Stack中使用。

工具类

Arrays和Collections是用来操作数组、集合的两个工具类，例如在ArrayList和Vector中大量调用了Arrays.Copyof()方法，而Collections中有很多静态方法可以返回各集合类的synchronized版本，即线程安全的版本，当然了，如果要用线程安全的结合类，首选Concurrent并发包下的对应的集合类。

集合和数组的区别

• 数组长度固定并且无法保存映射关系的数据。集合类可以用来保存数量不确定并且具有映射关系的数据。
• 数组可以保存基本类型的数据，也可以是引用类型的数据；而集合只能保存对象。

List集合

• List集合是一组有序可重复集合，元素都有索引，按照添加顺序排列，可以通过索引（LinkedList使用链表）快速查找，其中包含了三个常用的类，分别是ArrayList，Vector，LinkedList。下面我们逐一分析。

ArrayList：

• 底层使用的是数组；
• 根据数组索引查找元素，所以查询快；增删因为要移动元素位置，所以增删慢；
• 元素按照插入的顺序排列，元素可以重复；
• 非线程安全

注意点：如果我们在使用ArrayList的时候，提前知道会放入多少长度元素的时候，可以提前指定集合的容量，这样就会减少添加数据的时候扩容的次数，提高性能（当然数据量大时候效果更好）。

Vector：

• 底层使用的是数组；
• 根据数组索引查找元素，所以查询快；增删因为要移动元素位置，所以增删慢；
• 元素按照插入的顺序排列，元素可以重复；
• 线程安全（对方法整体使用synchronized关键字加锁，效率不高）

LinkedList：

• 底层使用的双向链表；
• 使用链表查找元素，所以查询慢，增删只需要替换掉指针的指向即可，所以增删快；
• 元素按照插入的顺序排列，元素可以重复；

Set集合

• Set集合是一组无序不可重复集合（LinkedHashSet元素有序），其中包含了三个常用的类，分别是HashSet，TreeSet，LinkedHashSet。下面我们逐一分析。

HashSet：

• 底层是用HashMap数据结构，以存入的元素为Key，因为不关心value，所以value为同一个object，Key元素可以为null。
• 因为HashMap的Key不可重复，而我们只关心Key，所以HashSet元素不可重复，元素无序。
• 因为内部使用的是HashMap，并没有自身的数据结构，感兴趣可以查看HashMap数据结构

TreeSet:

• 底层采用树结构来进行存储，内部使用的是TreeMap。
• 元素按照字符串顺序存储，元素不允许为null。

LinkedHashSet:

• 继承HashSet，内部采用的是LinkedHashMap数据结构。
• 和HashSet一样，内部存储元素不可重复。
• 和HashSet唯一不同的地方是元素有序。
• 因为内部使用的是LinkedHashMap，它内部的存储元素是LinkedHashMapEntry

Queue集合

队列是数据结构中比较重要的一种类型，它支持 FIFO，尾部添加、头部删除（先进队列的元素先出队列），跟我们生活中的排队类似。

PriorityQueue

PriorityQueue保存队列 元素的顺序并不是按照加入的顺序，而是按照队列元素的大小进行排序的。
PriorityQueue不允许插入null元素。

Deque

Deque接口是Queue接口的子接口，它代表一个双端队列,当程序中需要使用“栈”这种数据结构时，推荐使用ArrayDeque。

Map集合

• Map集合中存储的是具有<Key,Value>映射关系的元素，它在工作中是使用最多的数据结构之一。它有几个常用的实现类，HashMap，LinkedHashMap，Hashtable，TreeMap，其实前面讲解Set的时候已经提到了，下面我们再逐个分析一下：

HashMap: HashSet中使用的这个数据结构

• 它通过Key的hashCode()做相关的位运算得到数组中的位置索引，如果hash散列算法以及数组长度合适的话，效率很高。
• 它可以存入键为null的键值对，JDK1.7是将其存在数组的第一个索引位置。
• 因为它不是线程安全的，并且在高并发的情况下HashMap容易出现死循环，所以多线程环境下可以使用Collections.synchronizedMap()或者HashTable，它们两个是线程安全的，但是因为HashTable是对方法整体加锁，而Collections.synchronizedMap()是对代码块加锁，所以效率不够高。
• 在高并发的环境下可以使用ConcurrentHashMap，它采用的是分段加锁机制（1.8中引入了二叉树）

LinkedHashMap:

• 它是HashMap的子类，它和HashMap的区别是在HashMap的基础上，增加了一个双向链表来记录存储数据的先后顺序，能够保证遍历数据的时候，首先得到的是先插入的数据。

HashTable:

• 它不允许存入键值对为null（Key和Value都不能为null,否则会报NullPointerException）。
• 它是线程安全的，但是因为是对方法整体加锁，所以并发性不太好。一般不使用这个类，在不要求线程安全的时候可以使用HashMap, 对线程安全有要求的时候可以使用ConcurrentHashMap。
• 数据结构图和HashMap一致。

TreeMap：

• 它实现了SortedMap接口，查看put源码可以看到，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
• 它能够把保存的记录根据键排序，默认是按键值的升序排序，可以在构造方法中指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。