面试系列之-JAVA集合梳理（JAVA基础）

集合体系

collection集合说明 所有集合类都位于java.util包下，Java的集合类主要由两个接口派生而出：Collection和Map，Collection和Map是Java集合框架的根接口，这两个接口又包含了一些子接口或实现类； Set接口继承Collection，集合元素不重复；List接口继承Collection，允许重复，维护元素插入顺序；Map接口是键－值对象，与Collection接口没有什么关系； ●List集合是有序集合，集合中的元素可以重复，访问集合中的元素可以根据元素的索引来访问； ●Set集合是无序集合，集合中的元素不可以重复，访问集合中的元素只能根据元素本身来访问（也是集合里元素不允许重复的原因）； ●

Map集合中保存Key-value对形式的元素，访问时只能根据每项元素的key来访问其value；

已实现的子类

List是一个有序的队列，每一个元素都有它的索引，第一个元素的索引值是0，List的实现类有LinkedList, ArrayList, Vector, Stack；

ArrayList ArrayList是一个动态数组，也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

LinkedList LinkedList是一个双向链表，所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。与ArrayList一样，LinkedList也是非同步的。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：List list = Collections.synchronizedList(new LinkedList(...));

Vector 与ArrayList相似，但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样；

Stack Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈；

CopyOnWriteArrayList CopyOnWriteArrayList是线程安全的List，内部使用数组存储数据，集合中多线程并行操作一般存在4种情况：读读、读写、写写、写读，这个只有在写写操作过程中会导致其他线程阻塞，其他3种情况均不会阻塞，所以读取的效率非常高； 当这个List需要修改时，并不修改原有内容（这对于保证当前在读线程的数据一致性非常重要），而是在原有存放数据的数组上产生一个副本，在副本上修改数据，修改完毕之后，用副本替换原来的数组，这样也保证了写操作不会影响读； Set是一个不允许有重复元素的集合，Set的实现类有HastSet和TreeSet，HashSet依赖于HashMap，它实际上是通过HashMap实现的；TreeSet依赖于TreeMap，它实际上是通过TreeMap实现的；

HashSet HashSet 是一个没有重复元素的集合。它是由HashMap实现的，不保证元素的顺序(这里所说的没有顺序是指：元素插入的顺序与输出的顺序不一致)，而且HashSet允许使用null元素。HashSet是非同步的，如果多个线程同时访问一个哈希set，而其中至少一个线程修改了该set，那么它必须保持外部同步。HashSet按Hash算法来存储集合的元素，因此具有很好的存取和查找性能。 HashSet的实现方式大致如下，通过一个HashMap存储元素，元素是存放在HashMap的Key中，而Value统一使用一个Object对象； HashSet使用和理解中容易出现的误区: ●HashSet中存放null值，HashSet中是允许存入null值的，但是在HashSet中仅仅能够存入一个null值； ●HashSet中存储元素的位置是固定的。HashSet中存储的元素的是无序的，这个没什么好说的，但是由于HashSet底层是基于Hash算法实现的，使用了hashcode，所以HashSet中相应的元素的位置是固定的；

LinkedHashSet LinkedHashSet继承自HashSet，其底层是基于LinkedHashMap来实现的，有序，非同步。LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素；

TreeSet TreeSet是一个有序集合，其底层是基于TreeMap实现的，非线程安全。TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。当我们构造TreeSet时，若使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数； TreeSet集合不是通过hashcode和equals函数来比较元素的，它是通过compare或者comparaeTo函数来判断元素是否相等，compare函数通过判断两个对象的id，相同的id判断为重复元素，不会被加入到集合中。

ConcurrentSkipListSet 有序的Set，内部基于ConcurrentSkipListMap实现的，放入的元素会进行排序，排序算法支持2种方式来指定： 1通过构造方法传入一个Comparator 2放入的元素实现Comparable接口 特性：迭代结果和存入顺序不一致；放入的元素会排序；元素不重复；元素不能为空；线程安全的；无界的；

CopyOnWriteArraySet 内部使用CopyOnWriteArrayList实现的，将所有的操作都会转发给CopyOnWriteArrayList。特性： 迭代结果和存入顺序不一致；元素不重复；元素可以为空；线程安全的；读读、读写、写读 不会阻塞；写写会阻塞；无界的； Iterator是获取集合中元素的过程，实际上帮助获取集合中的元素。 迭代器代替了Java Collections Framework中的Enumeration，迭代器与枚举有两点不同： ●迭代器允许调用方利用定义良好的语义在迭代期间从迭代器所指向的集合移除元素； ●方法名称得到了改进； Iterator仅有一个子接口ListIterator，是列表迭代器，允许程序员按任一方向遍历列表、迭代期间修改列表，并获得迭代器在列表中的当前位置。ListIterator 没有当前元素；它的光标位置 始终位于调用 previous()所返回的元素和调用next()所返回的元素之间。在长度为n的列表中，有n+1个有效的索引值，从0到n（包含）；

集合框架之外的Map接口 Map将键映射到值的对象，一个映射不能包含重复的键；每个键最多只能映射一个值；Map接口是Dictionary（字典）抽象类的替代品； Map接口提供三种collection视图，允许以键集、值集合或键-值映射关系集的形式查看某个映射的内容。映射的顺序 定义为迭代器在映射的collection视图中返回其元素的顺序。某些映射实现可明确保证其顺序，如 TreeMap类；某些映射实现则不保证顺序，如HashMap类；

已实现的子类 HashMap：基于哈希表的Map接口的实现，此实现提供所有可选的映射操作，并允许使用null值和null键。（除了不同步和允许使用null之外，HashMap类与Hashtable大致相同）此类不保证映射的顺序，特别是它不保证该顺序恒久不变； TreeMap：它实现SortedMap接口的基于红黑树的实现。此类保证了映射按照升序顺序排列关键字，根据使用的构造方法不同，可能会按照键的类的自然顺序 进行排序（参见Comparable），或者按照创建时所提供的比较器进行排序； Hashtable：此类实现一个哈希表，该哈希表将键映射到相应的值，任何非null对象都可以用作键或值； LinkedHashMap：LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序； ConcurrentHashMap：功能和HashMap基本一致，内部使用红黑树实现的。特性：迭代结果和存入顺序不一致；key和value都不能为空；线程安全的；

ConcurrentSkipListMap 内部使用跳表实现的，放入的元素会进行排序，排序算法支持2种方式来指定： 1通过构造方法传入一个Comparator； 2放入的元素实现Comparable接口； 上面2种方式必选一个，如果2种都有，走规则1。特性：迭代结果和存入顺序不一致；放入的元素会排序；key和value都不能为空；线程安全的

Collection和Collections区别 ●java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set； ●java.util.Collections 是一个包装类（工具类/帮助类）。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，用于对集合中元素进行排序、搜索以及线程安全等各种操作，服务于Java的Collection框架；

Queue队列

ConcurrentLinkedQueue 高效并发队列，内部使用链表实现的；特性：线程安全的；迭代结果和存入顺序一致；元素可以重复；元素不能为空；线程安全的；无界队列；

快速失败和安全失败

快速失败fast-fail eg：在使用迭代器对集合对象进行遍历的时候，如果 A 线程正在对集合进行遍历，此时 B 线程对集合进行修改（增加、删除、修改），或者 A 线程在遍历过程中对集合进行修改，都会导致 A 线程抛出 ConcurrentModificationException 异常； 在使用迭代器遍历集合对象时，如果在遍历的过程中对集合中的元素进行了修改就会抛出ConcurrentModificationException异常； 集合中有一个modCount变量，在我们对集合进行修改(增加、删除、修改)操作的时候就会改变这个变量的值，当我们使用迭代器进行集合遍历时，我们在获得迭代器对象的就会对得带器内部的expectedModCount进行初始化，初始值就是我们modCount。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历；

安全失败safe-fail 采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历； 由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，故不会抛 ConcurrentModificationException 异常，程序正常执行；

快速失败和安全失败是对迭代器而言的，并发环境下建议使用 java.util.concurrent 包下的容器类，除非没有修改操作；

线程安全集合

1以Concurrent开头的集合类，可以支持多个线程并发写入访问，写入操作都是线程安全的，读取操作不必锁定，采用更复杂的算法保证永不会锁住整个集合，因此在并发写入时有较好的性能； 2以CopyOnWrite开头的集合类，采用复制底层数组的方式来实现写操作，读时无须加锁，对复制的新数组进行写操作，所以线程安全，频繁的复制数组，性能比较差，但读操作因为没有加锁和阻塞就很快、很安全； 3使用 Collections 装饰的线程安全集合 ○Collections.synchronizedCollection ○Collections.synchronizedList ○Collections.synchronizedMap ○Collections.synchronizedSet ○Collections.synchronizedNavigableMap ○Collections.synchronizedNavigableSet ○Collections.synchronizedSortedMap ○Collections.synchronizedSortedSet 4Blocking 大部分实现基于锁，并提供用来阻塞的方法；