今天开始第二篇，集合的相关面试题。

java 集合都有哪些？

Collection 和 Collections 有什么区别？

• java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set。
• Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。

List、Set、Map 之间的区别是什么？

HashMap 和 Hashtable 有什么区别？

• 继承的类不同，HashMap继承AbstractMap类，Hashtable 继承Dictionary类。但两者都实现了Map接口。

public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable

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

• 性能不同。HashMap线程不安全，效率较高；Hashtable 线程安全，效率较低。
• 存储要求不同。HashMap允许null键和null值，键不能重复，值可以重复；Hashtable 不允许null键和null值，key 和 value都不能重复，否则会抛出空指针异常。初始化容量不同。HashMap底层数组初始化长度为16，Hashtable 底层数组初始化长度为11；扩容方式不同。HashMap扩容容量为old * 2 ;Hashtable 扩容容量为 old * 2 + 1。计算数组位置索引的方式不同。HashMap是将hash值和数组长度-1做 &运算；Hashtable 是取模运算。

HashMap和TreeMap的区别和使用？

• HashMap基于散列桶（数组和链表）实现；TreeMap基于红黑树实现。
• HashMap不支持排序；TreeMap默认是按照Key值升序排序的，可指定排序的比较器，主要用于存入元素时对元素进行自动排序。
• HashMap大多数情况下有更好的性能，尤其是读数据。在没有排序要求的情况下，使用HashMap。
• 都是非线程安全。

HashMap的底层原理是什么？线程安全么？

基本原理

HashMap底层是基于Hash原理，通过数组链表实现的。它的数据结构是整体是数组结构，每个元素是一个链表结构。
当元素插入的时候，首先通过Hash方法计算key的哈希值，然后通过（n-1）&hash 公式（n为数组长度,初始化数组默认长度为16），得到key在数组中存放的下标，如果该位置已经有了其他元素（存在hash冲突），则与原来的元素组成链表，如果该位置没有其他元素，则直接插入。在JDK1.8之后，如果该链表的长度超过8，并且数组长度大于64，则该链表转成红黑树。

HashMap内部使用数组存储数据，数组中的每个元素类型为Node<K,V>：

//Node包含了四个字段：hash、key、value、next，其中next表示链表的下一个节点。
static class Node<K,V> implements Map.Entry<K,V> { 
final int hash; 
final K key; 
V value;
Node<k,V> next; //链表的下一个节点
}
HashMap包含几个重要的变量：
// 数组默认的初始化长度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 数组最大容量，2的30次幂，即1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转换为红黑树的长度阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转换为链表的长度阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 链表转换为红黑树时，数组容量必须大于等于64
static final int MIN_TREEIFY_CAPACITY = 64;
// HashMap里键值对个数
transient int size;
// 扩容阈值，计算方法为 数组容量*加载因子
int threshold;

为什么要加入红黑树？

JDK1.8之前，HashMap底层实现用的是数组+链表。（JDK1.8以后用数组+链表+红黑树）。hashMap通过Hash方法计算key的哈希码，然后通过公式得到key在数组中存放的下标，当两个key的下标一致是，也就是存在hash碰撞，则数据以链表的形式存储，在链表中查找数据必须从第一个一层层往下找，直到找到为止，时间复杂度为O(N)，所以当链表长度越来越长，Hashmap的效率就会越来越低。
所以需要在当链表中的元素超过8个并且数组长度大于64时，会将链表转换为红黑树，转换后数据查询时间复杂度从O(N)变为O(logN)。

红黑树的节点使用TreeNode表示：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
TreeNode<K,V> parent; // red-black tree links 
TreeNode<K,V> left; 
TreeNode<K,V> right; 
TreeNode<K,V> prev; // needed to unlink next upon deletion 
boolean red; 
TreeNode(int hash, K key, V val, Node<K,V> next) { 
super(hash, key, val, next); 
} 
...
}

加载因子

从上面的常量中可以看到HashMap的加载因子是0.75。加载因子也叫扩容因子，用于决定HashMap数组何时进行扩容。比如数组容量为16，加载因子为0.75，那么扩容阈值为数组容量加载因子，16*0.75=12，即HashMap数据量大于等于12时，数组就会进行扩容。
我们都知道，数组容量的大小在创建的时候就确定了，所谓的扩容指的是重新创建一个指定容量的数组，然后将旧值复制到新的数组里。扩容这个过程非常耗时，会影响程序性能。

所以加载因子是基于容量和性能之间平衡的结果：
当加载因子过大时，扩容阈值也变大，也就是说扩容的门槛提高了，这样容量占用就会降低。但这时哈希碰撞的几率就会增加，效率下降；
当加载因子过小时，扩容阈值变小，扩容门槛降低，容量占用变大。这时候哈希碰撞的几率下降，效率提高。

可以看到容量占用和性能是此消彼长的关系，它们的平衡点由加载因子决定，0.75是一个即兼顾容量又兼顾性能的经验值。

Put的整个操作过程

1. 判断HashMap数组是否为空，是的话初始化数组（由此可见，在创建HashMap对象的时候并不会直接初始化数组）；
2. 通过 (n-1) & hash 计算key在数组中的存放索引；
3. 目标索引位置为空的话，直接创建Node存储；
4. 目标索引位置不为空的话，分下面三种情况：

• key相同，覆盖旧值；
• 该节点类型是红黑树的话，执行红黑树插入操作；
• 该节点类型是链表的话，遍历到最后一个元素尾插入，如果期间有遇到key相同的，则直接覆盖。如果链表长度大于等于8，并且数组容量大于等于64，则将链表转换为红黑树结构；

5. 判断HashMap元素个数是否大于等于扩容阀值（ 0.75*数组初始化长度16），是的话，进行扩容操作（扩容为原来的两倍）。

set有哪些实现类？

HashSet

HashSet是set接口的实现类，set下面最主要的实现类就是HashSet（也就是用的最多的），此外还有LinkedHashSet和TreeSet。
HashSet是无序的、不可重复的。通过对象的hashCode和equals方法保证对象的唯一性。
HashSet内部的存储结构是哈希表，是线程不安全的。

TreeSet

TreeSet对元素进行排序的方式：

• 元素自身具备比较功能，需要实现Comparable接口，并覆盖compareTo方法。
• 元素自身不具备比较功能，需要实现Comparator接口，并覆盖compare方法。

LinkedHashSet

LinkedHashSet是一种有序的Set集合，即其元素的存入和输出的顺序是相同的。

说一下 HashSet 的实现原理？

• HashSet实际上是一个HashMap实例，数据存储结构都是数组+链表。
• HashSet是基于HashMap实现的，HashSet中的元素都存放在HashMap的key上面，而value都是一个统一的对象PRESENT。
• private static final Object PRESENT = new Object();
• HashSet中add方法调用的是底层HashMap中的put方法，put方法要判断插入值是否存在，而HashSet的add方法，首先判断元素是否存在，如果存在则插入，如果不存在则不插入，这样就保证了HashSet中不存在重复值。
• 通过对象的hashCode和equals方法保证对象的唯一性。

ArrayList 和 LinkedList 的区别是什么？

最明显的区别是 ArrrayList底层的数据结构是数组，支持随机访问，而 LinkedList 的底层数据结构是双向循环链表，不支持随机访问。使用下标访问一个元素，ArrayList 的时间复杂度是 O(1)，而 LinkedList 是 O(n)。

如何实现数组和 List 之间的转换？

• List转换成为数组：调用ArrayList的toArray方法。
• 数组转换成为List：调用Arrays的asList方法。

ArrayList 和 Vector 的区别是什么？

• 同步性
  Vector是线程安全的，也就是说是它的方法之间是线程同步的，而ArrayList是线程序不安全的，它的方法之间是线程不同步的。如果只有一个线程会访问到集合，那最好是使用ArrayList，因为它不考虑线程安全，效率会高些；如果有多个线程会访问到集合，那最好是使用Vector。
  - 数据增长
  ArrayList与Vector都有一个初始的容量大小，当存储进它们里面的元素的个数超过了容量时，就需要增加ArrayList与Vector的存储空间，Vector增长率为目前长度的100%，而Arraylist增长率为目前长度的50%。

Array 和 ArrayList 有何区别？

• Array可以容纳基本类型和对象，而ArrayList只能容纳对象。
• Array是指定大小的，而ArrayList大小是固定的。
• Array没有提供ArrayList那么多功能，比如addAll、removeAll和iterator等。

ArrayList 和 LinkedList 的区别是什么？

ArrayList底层是数组结构，支持随机访问。
LinkList底层是双向循环列表，不支持随机访问。

在 Queue 中 poll()和 remove()有什么区别？

poll() 和 remove() 都是从队列中取出一个元素，但是 poll() 在获取元素失败的时候会返回空，但是 remove() 失败的时候会抛出异常。

哪些集合类是线程安全的？

• Vector：就比Arraylist多了个同步化机制（线程安全）。
• Hashtable：就比Hashmap多了个线程安全。
• ConcurrentHashMap:是一种高效但是线程安全的集合。
• Stack：栈，也是线程安全的，继承于Vector。

迭代器 Iterator 是什么？

迭代器是一种设计模式，它是一个对象，它可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，因为创建它的代价小。

Iterator 怎么使用？有什么特点？

Java中的Iterator功能比较简单，并且只能单向移动：
(1) 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时，它返回序列的第一个元素。注意：iterator()方法是java.lang.Iterable接口,被Collection继承。
(2) 使用next()获得序列中的下一个元素。
(3) 使用hasNext()检查序列中是否还有元素。
(4) 使用remove()将迭代器新返回的元素删除。

Iterator 和 ListIterator 有什么区别？

• Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。 Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。 ListIterator实现了Iterator接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引等等。

简单说下同步容器和并发容器的区别？

• 同步容器
  指的是通过synchronized实现线程同步的集合容器，比如Hashtable，这样虽然实现了线程同步，但是降低了效率。
• 并发容器
  指的是指的是通过锁分段技术，拷贝复制技术或者其他算法实现对写操作的元素进行加锁，而不会影响到其他的元素的读操作。

常见的并发容器有哪些？

1. ConcurrentHashMap

对应的非并发容器：HashMap
目标：代替Hashtable、synchronizedMap，支持复合操作
原理：JDK6中采用一种更加细粒度的加锁机制（分段锁），JDK8中使用的是synchronized+CAS。原因如下：

• 加入多个分段锁浪费内存空间
• 生产环境中， map 在放入时竞争同一个锁的概率非常小，分段锁反而会造成更新等操作的长时间等待。
• 为了提高 GC 的效率。

2. CopyOnWriteArrayList

对应的非并发容器：ArrayList
目标：代替Vector、synchronizedList
原理：利用高并发往往是读多写少的特性，对写操作加锁，读操作不加锁，对写操作，先复制一份新的集合，在新的集合上面修改，然后将新集合赋值给旧的引用，并通过volatile 保证其可见性。

3. CopyOnWriteArraySet

对应的非并发容器：HashSet
目标：代替synchronizedSet
原理：基于CopyOnWriteArrayList实现，其唯一的不同是在add时调用的是CopyOnWriteArrayList的addIfAbsent方法，其遍历当前Object数组，如Object数组中已有了当前元素，则直接返回，如果没有则放入Object数组的尾部，并返回。

4. ConcurrentSkipListMap

对应的非并发容器：TreeMap
目标：代替synchronizedSortedMap(TreeMap)
原理：Skip list（跳表）是一种可以代替平衡树的数据结构，默认是按照Key值升序的。

5. ConcurrentSkipListSet

对应的非并发容器：TreeSet
目标：代替synchronizedSortedSet
原理：内部基于ConcurrentSkipListMap实现

6. ConcurrentLinkedQueue

不会阻塞的队列
对应的非并发容器：Queue
原理：基于链表实现的FIFO队列（LinkedList的并发版本）

7. LinkedBlockingQueue、ArrayBlockingQueue、PriorityBlockingQueue

对应的非并发容器：BlockingQueue
特点：拓展了Queue，增加了可阻塞的插入和获取等操作
原理：通过ReentrantLock实现线程安全，通过Condition实现阻塞和唤醒
实现类：
LinkedBlockingQueue：基于链表实现的可阻塞的FIFO队列。
ArrayBlockingQueue：基于数组实现的可阻塞的FIFO队列。
PriorityBlockingQueue：按优先级排序的队列。

动态数组和静态数组的区别？

静态数组在内存中位于栈区，是在定义时就已经在栈上分配了固定大小，在运行时这个大小不能改变。在函数执行完以后，系统自动销毁。
动态数组是指其长度在运行期确定，也就是长度可变，存储在堆空间。

Collection和Collections的区别

• Collection:是集合类的顶层接口，里面包含了一些集合的基本操作。Collection接口是Set接口和List接口的父接口。
• Collections:是一个包装类(工具类)，它包含了对集合操作的各种静态多态方法，如：对集合的排序，删除和序列化。该类不能被实例化。

怎么确保一个集合不能被修改？

我们很容易想到final，final关键字可以修饰类，方法，成员变量，final修饰的类不能被继承，final修饰的方法不能被重写，final修饰的成员变量必须初始化值，如果这个成员变量是基本数据类型，表示这个变量的值是不可改变的，如果说这个成员变量是引用类型，则表示这个引用的地址值是不能改变的，但是这个引用所指向的对象里面的内容还是可以改变的。
所以我们可以采用Collections包下的unmodifiableMap方法，通过这个方法返回的map,是不可以修改的。他会报 java.lang.UnsupportedOperationException错。Collections包也提供了对list和set集合的方法。

Collections.unmodifiableList(List)
Collections.unmodifiableSet(Set)

队列和栈是什么？有什么区别？

• 队列先进先出，栈先进后出。
• 遍历数据速度不同。
  栈只能从头部取数据 也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性；
  队列则不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多。

ConcurrentHashMap（JDK1.8）为什么要使用synchronized而不是如ReentranLock这样的可重入锁？

我们知道，ConcurrentHashMap是一个 在juc包下的 map， 线程安全。 在jdk.1.8 之前采用数组+ 链表的结构 并且采用分段锁机制来保证线程安全，而jdk1.8 改成了 数组+ 链表+ 红黑树，线程安全方面也改成了 cas+ synchronized 来保证线程安全。

• 减少内存开销
  假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承AQS来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。
• 获得JVM的支持
  可重入锁毕竟是API这个级别的，后续的性能优化空间很小。
  synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。这就使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升。