集合框架复习大纲

List：

1.可以允许重复的对象。

　　2.可以插入多个null元素。

3.是一个有序容器，保持了每个元素的插入顺序，输出的顺序就是插入的顺序。

4.常用的实现类有 ArrayList、LinkedList 和 Vector。ArrayList 最为流行，它提供了使用索引的随意访问，而 LinkedList 则对于经常需要从 List 中添加或删除元素的场合更为合适。

Set：

1.不允许重复对象

　　2.无序容器，你无法保证每个元素的存储顺序，TreeSet通过 Comparator 或者 Comparable 维护了一个排序顺序。

3.只允许一个 null 元素

4.Set接口最流行的几个实现类是 HashSet、LinkedHashSet 以及 TreeSet。最流行的是基于 HashMap 实现的 HashSet；TreeSet 还实现了 SortedSet 接口，因此 TreeSet 是一个根据其 compare() 和 compareTo() 的定义进行排序的有序容器。

Map:

1.Map不是collection的子接口或者实现类。Map是一个接口。

2.Map的每个 Entry 都持有两个对象，也就是一个键一个值，Map 可能会持有相同的值对象但键对象必须是唯一的。

3. TreeMap也通过 Comparator 或者 Comparable 维护了一个排序顺序。

4. Map里你可以拥有随意个 null 值但最多只能有一个 null 键。

5.Map接口最流行的几个实现类是 HashMap、LinkedHashMap、Hashtable 和 TreeMap。（HashMap、TreeMap最常用）

2.面试题：什么场景下使用list，set，map呢？

（或者会问为什么这里要用list、或者set、map，这里回答它们的优缺点就可以了）

答：

1.如果你经常会使用索引来对容器中的元素进行访问，那么List 是你的正确的选择。如果你已经知道索引了的话，那么 List 的实现类比如 ArrayList 可以提供更快速的访问,如果经常添加删除元素的，那么肯定要选择LinkedList。

如果你想容器中的元素能够按照它们插入的次序进行有序存储，那么还是List，因为 List 是一个有序容器，它按照插入顺序进行存储。

2. 如果你想保证插入元素的唯一性，也就是你不想有重复值的出现，那么可以选择一个Set 的实现类，比如 HashSet、LinkedHashSet 或者 TreeSet。所有 Set 的实现类都遵循了统一约束比如唯一性，而且还提供了额外的特性比如 TreeSet 还是一个 SortedSet，所有存储于 TreeSet 中的元素可以使用 Java 里的 Comparator 或者 Comparable 进行排序。LinkedHashSet 也按照元素的插入顺序对它们进行存储。

[if !supportLists]3. [endif]如果你以键和值的形式进行数据存储那么Map 是你正确的选择。你可以根据你的后续需要从 Hashtable、HashMap、TreeMap 中进行选择。

二．掌握ArrayList,LinkedList及Vector间的区别。掌握ArrayList接LinkedList的底层实现及各自优缺点。

①ArrayList：

1. 内部采用数组存储元素，支持高效随机访问，

2. 支持动态调整大小；

3. 更适合遍历查询，增删改的效率相对低；

4.不同步所以不安全

②LinkedList：

1. 内部采用双向链表来存储元素，

2. 支持快速插入/删除元素，但不支持高效地随机访问；

3. 更适合增删改，遍历效率相对低[无同步]；

4. 不同步所以不安全

③Vector：

1.采用数组存储元素，

2.使用了synchronized方法，是一个线程安全的容器，

3. 所以性能上比ArrayList差[同步]；

三．掌握迭代器使用，掌握list set 及Map的遍历方式。

遍历List方法一：普通for循环

1 for(int i=0;i<list.size();i++){//list为集合的对象名2 String temp = (String)list.get(i);3 System.out.println(temp);4 }

遍历List方法二：增强for循环(使用泛型!)

1 for (String temp : list) {2 System.out.println(temp);3 }

遍历List方法三：使用Iterator迭代器(1)

1 for(Iterator iter= list.iterator();iter.hasNext();){2 String temp = (String)iter.next();3 System.out.println(temp);4 }

遍历List方法四：使用Iterator迭代器(2)

1 Iterator iter =list.iterator();2 while(iter.hasNext()){3 Object obj = iter.next();4 iter.remove();//如果要遍历时，删除集合中的元素，建议使用这种方式！5 System.out.println(obj);6 }

遍历Set方法一：增强for循环

1 for(String temp:set){2 System.out.println(temp);3 }

遍历Set方法二：使用Iterator迭代器

1 for(Iterator iter = set.iterator();iter.hasNext();){2 String temp = (String)iter.next();3 System.out.println(temp);4 }

遍历Map方法一：根据key获取value

1 Map<Integer, Man> maps = new HashMap<Integer, Man>();2 Set<Integer> keySet = maps.keySet();3 for(Integer id : keySet){4 System.out.println(maps.get(id).name);5 }

遍历Map方法二：使用entrySet

1 Set<Entry<Integer, Man>> ss = maps.entrySet();2 for (Iterator iterator = ss.iterator(); iterator.hasNext();) {3 Entry e = (Entry) iterator.next(); 4 System.out.println(e.getKey()+"--"+e.getValue());

四．掌握HashMap及HashTable间的区别与联系

1）Hashtable是线程安全，而HashMap则非线程安全

2）HashMap可使用null作为key，Hashtable不允许null作为key

[if !supportLists]3）[endif]HashMap是对Map接口的实现，Hashtable对Map接口的实现和对Dictionary抽象类的继承

4）HashMap的初始容量是16，Hashtable初始容量是11，两者的填充因子默认都是0.75

5）HashMap与Hashtable计算hash的是方法不同

Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模

HashMap计算hash对key的hashcode进行了二次hash，以获得更好的散列值，然后对table数组长度取摸

6）HashMap和Hashtable的底层实现都是数组+链表结构实现

五．掌握HashMap的底层实现，理解一个K-V键值对的存取过程，掌握HashMap JDK1.8新特性。

1.JDK1.7

HashMap是Java中大家最常用的一个map实现类，其为键值对也就是key-value的形式。他的数据结构则是采用的位桶和链表相结合的形式完成了，即拉链法。

默认的加载因子是0.75，如果不扩容，链表就会越来越长，查找起来因为要逐一equals进行比对，所以会慢很多。当然现在因为又采用了红黑树，相对来说比jdk1.7要好一些。扩容之后，会将原本的链表数组中的每个链表分为奇偶两个，分别挂在新链表的数组下的对应的散列位置。减少查找时间，提高效率。

2.1 jdk1.8的最大区别就在于底层的红黑树策略。

相对于JDK1.7，HashMap处理hash冲突时，会首先存放在链表中去，但是一旦链表中的数据较多(即>8个)之后，就会转用红黑树来进行存储，优化存储速度。O(lgn)。如果是链表。一定是O(n)

[if !supportLists]六．[endif]理解TreeSet的原理与使用。

1、TreeSet()是使用二叉树的原理对新add()的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。

2、Integer和String对象都可以进行默认的TreeSet排序，而自定义类的对象是不可以的，自己定义的类必须实现Comparable接口，并且覆写相应的compareTo()函数，才可以正常使用。

3、在覆写compare()函数时，要返回相应的值才能使TreeSet按照一定的规则来排序（升序，this.对象 < 指定对象的条件下返回-1）

（降序，this.对象 < 指定对象的条件下返回-1）升序是：比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正

七．理解ConcurrentHashMap使用及实现原理。

Java7

在Java7中，ConcurrentHashMap维持了16个segment（继承自ReentrantLock），每个segment存放一个HashMap，各segment之间可以并行。

所以segment的hash散列会关系到并行效率，对key取hash后，利用hash的高位来计算属于哪个segment。

获取size时，为了提高效率，会先不锁表，先对segment的值求和，连续三次，如果值不变就认为没有冲突，如果值变化了，再去锁表。

Java8

Java8的ConcurrentHashMap和Java8里的HashMap都使用红黑树（如果链表长度超过8，就使用红黑树管理）。

在Java8中，ConcurrentHashMap做了进一步优化，不再划分segment，而是直接针对数组挂的每条链表都可以并行，同时，为了保持可见性，数组、Node的value，和Node的next都是volatile变量。

在获取size时，不再做运算，而是在平时，put和remove时，维护map的size。

八．了解CopyOnWriteArrayList，CopyOnWriteArraySet，ArrayBlockingQueue，LinkedBlockingQueue，了解其各自特点及使用场景。

2. CopyOnWriteArraySet类

特点：

它最适合于set大小通常保持很小、只读操作远多于可变操作以及需要在遍历期间防止线程间冲突的应用程序。

它是线程安全的。

因为通常需要复制整个基础数组，所以可变操作（添加、设置、移除，等等）的开销巨大。

迭代器不支持可变移除操作。

使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。

3. CopyOnWriteArrayList类

CopyOnWriteArrayList是concurrent包中提供的一个非阻塞型的，线程安全的List实现。其中所有可变操作（添加、设置，等等）都是通过对基础数组进行一次新的复制来实现的。

CopyOnWriteArrayList在进行数据修改时，都不会对数据进行锁定，每次修改时，先拷贝整个数组，然后修改其中的一些元素，完成上述操作后，替换整个数组的指针。

对CopyOnWriteArrayList进行读取时，也不进行数据锁定，直接返回需要查询的数据，如果需要返回整个数组，那么会将整个数组拷贝一份，再返回，保证内部array在任何情况下都是只读的。

CopyOnWriteArrayLIst在少量修改，频繁读取的场景下，有很好的并发性能。

4. ConcurrentLinkedQueue类

一个基于链接节点的、无界的、线程安全的队列。此队列按照FIFO（先进先出）原则对元素进行排序。队列的头部是队列中时间最长的元素。队列的尾部是队列中时间最短的元素。新的元素插入到队列的尾部，队列检索操作从队列头部获得元素。当许多线程共享访问一个公共collection 时，ConcurrentLinkedQueue 是一个恰当的选择。此队列不允许 null 元素。

此实现采用了有效的“无等待(wait-free)”算法。与大多数 collection 不同，size 方法不是一个固定时间的操作。由于这些队列的异步特性，确定当前元素的数量需要遍历这些元素。

5. BlockingQueue接口

BlockingQueue很好的解决了多线程中，如何高效安全“传输”数据的问题。通过这些高效并且线程安全的队列类，为我们快速搭建高质量的多线程程序带来极大的便利。

BlockingQueue不光实现了一个完整队列所具有的基本功能，同时在多线程环境下，他还自动管理了多线间的自动等待于唤醒功能，从而使得程序员可以忽略这些细节，关注更高级的功能。

BlockingQueue特点：

如果BlockQueue是空的，从BlockingQueue取东西的操作将会被阻断进入等待状态，直到BlockingQueue进了东西才会被唤醒。同样，如果BlockingQueue是满的，任何试图往里存东西的操作也会被阻断进入等待状态，直到BlockingQueue里有空间才会被唤醒继续操作。

BlockingQueue不接受 null 元素。

BlockingQueue可以是限定容量的。

BlockingQueue实现主要用于生产者-使用者队列。

BlockingQueue实现是线程安全的。

BlockingQueue常用方法：

boolean add(E o):将指定的元素添加到此队列中（如果立即可行），在成功时返回 true，其他情况则抛出 IllegalStateException。

boolean offer(E o):如果可能的话，将指定元素插入此队列中。成功返回true，否则返回false。

void put(E o):将指定元素添加到此队列中，如果没有可用空间，将一直等待（如果有必要）。

E poll(long timeout, TimeUnit unit):检索并移除此队列的头部，如果此队列中没有任何元素，则等待指定等待的时间（如果有必要）。

E take():检索并移除此队列的头部，如果此队列不存在任何元素，则一直等待。

5.1 ArrayBlockingQueue类

一个由数组支持的有界阻塞队列。此队列按FIFO（先进先出）原则对元素进行排序。队列的头部是在队列中存在时间最长的元素。队列的尾部是在队列中存在时间最短的元素。新元素插入到队列的尾部，队列检索操作则是从队列头部开始获得元素。

这是一个典型的“有界缓存区”，固定大小的数组在其中保持生产者插入的元素和使用者提取的元素。一旦创建了这样的缓存区，就不能再增加其容量。试图向已满队列中放入元素会导致放入操作受阻塞；试图从空队列中检索元素将导致类似阻塞。

此类支持对等待的生产者线程和使用者线程进行排序的可选公平策略。默认情况下，不保证是这种排序。然而，通过将公平性(fairness)设置为 true 而构造的队列允许按照 FIFO 顺序访问线程。公平性通常会降低吞吐量，但也减少了可变性和避免了“不平衡性”。

5.2 LinkedBlockingQueue类

一个基于已链接节点的、范围任意的blocking queue。此队列按 FIFO（先进先出）排序元素。队列的头部是在队列中时间最长的元素。队列的尾部是在队列中时间最短的元素。新元素插入到队列的尾部，并且队列检索操作会获得位于队列头部的元素。链接队列的吞吐量通常要高于基于数组的队列，但是在大多数并发应用程序中，其可预知的性能要低。

可选的容量范围构造方法参数作为防止队列过度扩展的一种方法。如果未指定容量，则它等于Integer.MAX_VALUE。除非插入节点会使队列超出容量，否则每次插入后会动态地创建链接节点。

九：hashset与hashmap的区别

[if !supportLists]1. [endif]Hashset不是key value的存储

[if !supportLists]2. [endif]仅仅存储不重复的元素

3.是简化版的hashmap

[if !supportLists]九．[endif]Treeset 和treemap如何比较元素

TreeSet：

要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。

TreeMap：

要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。

[if !supportLists]十．[endif]Conllections工具类中的sort()怎么比较元素

第一种：

该方法中的泛型都是Comparable接口的子类，即只有是Comparable接口子类类型的数据，才能进行比较排序。如果其他类型的数据要进行比较排序，必须继承Comparable接口并覆写equals()和compareTo()方法。其中如String类、Integer类都是Comparable接口子类，可以进行排序，而基本类型不能进行sort排序。比较项目在类内指定

第二种：

说明：该方法中指定比较方式Comparator c，即c必须实现Comparator接口，覆写compareTo()方法指定比较项目。比较项目在类外指定，比较灵活

[if !supportLists]十一．[endif]HsahMap中的为什么hash的长度为2的幂而&位必须为奇数

[if !supportLists]十二．[endif]为什么重写了eqauls还必须重写hashcod

equals返回true，且hashcode值相同时才是同一对象

即：

(1)当obj1.equals(obj2)为true时，obj1.hashCode() == obj2.hashCode()必须为true

(2)当obj1.hashCode() == obj2.hashCode()为false时，obj1.equals(obj2)必须为false

[if !supportLists]十三．[endif]Fail-fst 与fail-safe之间的区别

Fail-safe:

采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先copy原有集合内容,在拷贝的集合上进行遍历.

原理:

由于迭代时是对原集合的拷贝的值进行遍历,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会ConcurrentModificationException

缺点:

基于拷贝内容的优点是避免了ConcurrentModificationException,但同样地, 迭代器并不能访问到修改后的内容 (简单来说就是, 迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的)

Fail-fast:

在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个modCount变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

十四．Comparable与Comparator的不同之处

1.Comparable & Comparator都是用来实现集合中元素的比较、排序的，只是 Comparable 是在集合内部定义的方法实现的排序，Comparator 是在集合外部实现的排序，所以，如想实现排序，就需要在集合外定义 Comparator 接口的方法或在集合内实现 Comparable 接口的方法

2.Comparator位于包Java.util下，而Comparable位于包 java.lang下

3.Comparable是一个对象本身就已经支持自比较所需要实现的接口（如 String、Integer 自己就可以完成比较大小操作，已经实现了Comparable接口）

十五．描述ConcurrentHashmap的数据存储结构，为什么提高效率

ConcurrentHashMap是线程安全并且高效的HashMap。Hashtable效率低下的原因是所有访问HashTable的线程必须竞争同一把锁。加入容器里有多把锁，每一把锁用于锁容器中的一部分数据，那么当多线程访问容器里不同数据段的数据时，线程之间就不会存在锁竞争，从而可以有效的提高并发效率，这就是ConcurrentHashMap的锁分段技术。首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个数据段时，其他段的数据也能被其他线程访问。

十六．Hashmap的实现原理

HashMap是基于拉链法实现的一个散列表，内部由数组和链表实现。

1.数组的初始容量为16，而容量是以2的次方扩充的，一是为了提高性能使用足够大的数组，二是为了能使用位运算代替取模预算。

2.数组是否需要扩充是通过负载因子判断的，如果当前元素个数为数组容量的0.75时，就会扩充数组。这个0.75就是默认的负载因子，可由构造传入。我们也可以设置大于1的负载因子，这样数组就不会扩充，牺牲性能，节省内存。

3.为了解决碰撞，数组中的元素是单向链表类型。当链表长度到达一个阈值时（7或8），会将链表转换成红黑树提高性能。而当链表长度缩小到另一个阈值时（6），又会将红黑树转换回单向链表提高性能，这里是一个平衡点。

十七．Hashset的实现原理

对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet 的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成，

十八．如何决定使用hashmap 还是TreeMap

1.TreeMap的Key值是要求实现java.lang.Comparable，所以迭代的时候TreeMap默认是按照Key值升序排序的；TreeMap的实现也是基于红黑树结构。

2.而HashMap<K,V>的Key值实现散列hashCode(),分布是散列的均匀的，不支持排序；数据结构主要是桶(数组),链表或红黑树。

3.大多情况下HashMap有更好的性能，所以大多不需要排序的时候我们会使用HashMap.

十九．数组与list之间的转化

数组->list:

第一种方法:Arrays.asList(arrays)

注:此种方法生成的List不可进行add和remove操作，因为它是一个定长的List，跟数组长度一致

第二种方法: Collections.addAll(list, arrays);

List->数组：

第一种：调用ArrayList的toArray方法。