前言

这是对自己所学的集合框架的知识的整理和汇总，以及一些常见的面试题。

1.Java集合体系

java中的集合一共分为两个体系，一个以Collection接口往下延伸，一个以Map接口往下延伸，建议结合体系图理解：
知识整理：Java中的集合框架汇总及常见面试题

2.以Collection接口往下延伸的体系

以Collection往下延伸的体系有三个接口，分别是 List，Set 和 Queue，它们都继承了Collection中的所有方法。

2.1 List

实现了List接口的集合类有两个特点，分别是有序和可添加重复元素，List接口有三个典型的实现，分别是ArrayList ，Vector 和 LinkedList

2.1.1 ArrayList

ArrayList集合的底层数据结构是数组，查询快，增删慢;线程不安全，效率高。

2.1.2 Vector

Vector集合底层数据结构是数组，查询快，增删慢;线程安全，效率低，几乎已经被淘汰了。

2.1.3 LinkedList

LinkedList集合底层数据结构是链表，查询慢，增删快;线程不安全，效率高。

2.2 Set

实现了Set接口的集合类有两个特点，分别是无序和不可添加重复元素，Set接口有三个典型的实现，分别是HashSet ，TreeSet 和 LinkedHashSet

2.2.1 HashSet

HashSet集合底层采用哈希表算法，增删改查的速度都快，不能保证元素的顺序；不可重复；线程不安全；集合元素可以为 NULL，但由于不能重复，最多只可以有一个。

2.2.2 TreeSet

TreeSet集合底层采用了红黑树算法，不保证元素的添加顺序，但是会对集合中的元素进行排序；线程不安全。

2.2.3 LinkedHashSet

LinkedHashSet集合是HashSet 的子类，底层采用了哈希表算法以及链表算法，既保证了元素的添加顺序，也保证了查询效率。但是整体性能要低于HashSet，线程不安全。

2.3 Queue

Queue队列，特点是先进先出，跟我们生活中的排队有点相似。它是一个用来存放等待处理元素的集合。

3.以Map接口往下延伸的体系

以Map接口往下延伸的体系分为三大类，分别是HashMap ，LinkedHashMap 和 TreeMap。
实现了Map接口的集合类有三个特点，以键值对(key,value)的方式存储元素，键不可以重复，值可以重复，无序。

3.1 HashMap

HashMap集合底层采用了哈希表算法，Key不会保证添加的先后顺序且不允许重复，线程不安全，效率高。key判断重复的标注是：两个key的equals() 方法返回 true，两个key的 hashCode 值也应该相同。(与HashSet类似)

3.2 LinkedHashMap

LinkedHashMap集合采用链表和哈希表算法，Key会保证先后添加的顺序，线程安全，效率低。key重复判断标准和HashMap相同。(与LinkedHashSet)

3.3 TreeMap

TreeMap采用红黑树算法，key会按照自然顺序或者定制顺序进行排序，key当然也不允许重复，线程不安全，效率高。key重复判断标准是：compareTo()/compare()返回值是否为零。(与TreeSet类似)

集合框架的一些面试题

1.实现了List，Set和Map接口的集合类之间的区别

List和Set都实现了Collection接口，Collection接口的父接口是Iterator接口，实现Iterator接口的集合类都拥有增强for循环(foreach)的功能，所以List接口和Set接口下的集合类都可以用foreach遍历集合，而Map接口下的集合类不可以。

2.Collection接口的remove方法和Iterator接口的remove方法的区别

Collection接口继承自Iterator接口，Iterator接口中的remove()方法没有参数，Collection接口中的remove(Object o)方法有参数。
性能方面：Iterator接口的remove方法需要配合next()方法使用，它获取集合中由next()方法获取的下一项，然后删除元素，效率比Collection接口的remove方法高；Collection接口的remove方法需要先找到要删除的元素，由于找出该项是采用单链表结构查询集合，每删除一个元素就要重新查询一遍集合，效率很低。
容错方面：在使用iterator遍历时，调用Iterator中的remove方法不会报错，因为Iterator的内部对象的个数会与原来集合中的元素个数一致；在使用iterator遍历时，调用Collection中的remove方法有可能报错，因为原来的集合元素个数可能发生改变，而Iterator的内部对象的个数则不会，个数不一致会发生冲突，从而导致异常。

3.集合与数组的区别

集合的长度可变，而数组的长度不可变。

4.ArrayList与LinkedList的异同?

线程安全:ArrayList和LinkedList都是线程不同步的，也就是线程不安全;
底层数据结构:ArrayList底层使用的是Object数组;LinkedList底层使用的是双向链表数据结构(JDK1.6之前为循环链表)
插入和删除是否受元素位置影响:ArrayList采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。LinkedList采用链表结构存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似O(1) 而数组近似O(n)。
是否支持快速随机访问:LinkedList不支持高效的随机元素访问，而ArrayList支持。(快速随机访问就是通过元素的序号快速获取元素对象，对应于get(Index)方法)
内存空间占用: ArrayList的空间浪费主要体现在list列表的结尾会预留一定的容量空间;LinkedList的空间话费则体现在它每一个元素都要消耗比ArrayList更多的空间。
*RandomAccess表示一个标识，标识实现的类具有随机访问功能。
*ArrayList实现了RandomAccess接口，而LinkedList没有实现。ArrayList底层是数组，而LinkedList底层是链表，数组天然支持随机访问，时间复杂度为O(1)，链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为O(n)，所以不支持快速随机访问。
-----实现了RandomAccess接口的数组，优先选择普通for循环，其次foreach。
-----未实现RandomAccess接口的数组，优先选择iterator遍历(foreach遍历底层也是通过iterator实现的)，大size的数据。千万不要使用普通for循环。

ArrayList与Vector的区别?
Vector类的所有方法都是同步的。可以由两个线程安全的访问一个Vector对象，但是一个线程访问Vector的话代码要在同步操作上话费大量的时间。(线程安全)
ArrayList是不同步的，所以在不需要保证线程安全时建议使用ArrayList。(线程不安全)

5.HashMap的底层实现

Jdk1.8之前
Jdk1.8之前HashMap底层是数组和链表结合在一起使用，也就是链表散列。HashMap通过key的hashCode经过扰动函数处理过后得到hash值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法换句话说使用扰动函数之后可以减少碰撞。
*所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
Jdk1.8之后
相比于之前的版本， JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

6.HashMap和HashTable的区别?

线程安全:HashMap是非线程安全的，HashTable是线程安全的(HashTable内部的方法基本都经过synchronized的修饰);
效率:因为线程安全问题，HashMap比HashTable效率更高一点(HashTable基本已经被淘汰，不要在代码中使用它)。
对Null key和Null value的支持:HashMap中，null可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为null。在HashTable中put进的键值只要有一个null，直接抛出空指针异常。
初始容量大小和每次扩充容量的大小不同:

创建时如果不指定容量初始值，HashTable默认的初始大小为11，之后每次补充，容量变为原来的2n+1;HashMap默认的初始化大小为16，之后每次扩充，容量变为原来的2倍。
创建时如果给定了容量初始值，HashTable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。
底层数据结构:jdk1.8以后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

7.HashMap的长度为什么是2的幂次方?

Hash 值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash ”。（n代表数组长度）。这也就解释了 HashMap 的长度为什么是2的幂次方。

8.HashMap多线程操作导致死循环问题

在多线程下，进行put操作会导致HashMap死循环，原因在于HashMap的扩容resize()方法。(jdk1.8已经解决了死循环的问题)

9.HashSet和HashMap的区别?

HashSet底层就是基于HashMap实现的。

HashMap	HashSet
实现了Map接口	实现Set接口
存储键值对	仅存储对象
调用put()向map中添加元素	调用add()方法向Set中添加元素
HashMap使用键(Key)计算HashCode	HashSet使用成员对象来计算还是从的值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false
HashMap相对于HashSet较快，因为它是使用唯一的键获取对象	ashSet比较HashMap来说比较慢

10.ConcurrentHashMap和HashTable的区别?

ConcurrentHashMap和HashTable的区别主要体现在实现线程安全的方式上不同。
底层数据结构:jdk1.7的ConcurrentHashMap底层采用分段的数组+链表实现，jdk1.8采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树;HashTable和jdk1.8之前的HashMap的底层数据结构类似都是采用数组+链表的形式，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的;
实现线程安全的方式(重要):
1. 在jdk1.7的时候，ConcurrentHashMap(分段锁)对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据。到了jdk1.8的时候已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发可控制使用synchronized和CAS来操作。
2. HashTable(同一把锁):使用synchronized来保证线程安全，效率非常低下。

11.集合框架底层数据结构总结

Collection

List
ArrayList: Object数组
Vector: Object数组
LinkedList: 双向链表
Set
HashSet(无序，唯一):基于HashMap实现的，底层采用HashMap来保存元素
LinkedHashSet:LinkedHashSet继承与HashSet，并且其内部是通过LinkedHashMap来实现的。有点类似于LinkedHashMap其内部是基于HashMap实现一样，不过还是有一点点区别。
TreeSet(有序，唯一):红黑树(自平衡的排序二叉树)

Map

HashMap:jdk1.8之前HashMap由数组+链表组成的
LinkedHashMap:LinkedHashMap继承自HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。
HashTable:数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
TreeMap:红黑树(自平衡的二叉树)

知识整理：Java中的集合框架汇总及常见面试题