容器

List、Set、Map之间的区别

比较	List	Set	Map
继承接口	Collection	Collection
常见实现类	AbstractList(其常用子类有ArrayList、LinkedList、Vector)	AbstractSet(其常用子类有HashSet、LinkedHashSet、TreeSet)	HashMap、HashTable、TreeMap
常见方法	add()、remove()、clear()、get()、contains()、size()	add()、remove()、clear()、contains()、size()	put()、get()、remove()、clear()、containsKey()、containsValue()、keySet()、values()、size()
元素是否可重复	可重复	不可重复(用equals判断)	不可重复
是否有序	有序	无序(实际上由HashCode决定)
线程是否安全	Vector线程安全		HashTable线程安全

List: List 接口储存一组不唯一 (可以有多个元素引用引用相同的对象)，有序的对象，可插入多条null元素；
Set: 不允许重复的集合，不允许有多个元素引用相同的对象，只允许有一个null元素；
Map: 使用键值对存储，Map会维护与Key有关联的值，两个Key可以引用相同的对象，但Key不能重复；

Array和ArrayList有什么区别？

Array可以包含基本类型和对象类型；ArrayList只能包含对象类型
Array大小是固定的；ArrayList大小是动态变化的
ArrayList提供了诸如addAll()、removeAll()、iterator()方法等
对于基本数据类型，集合使用自动装箱来减少代码量；但当处理固定大小的基本类型数据时，这种方式相对较慢。

数组与List之间的转换

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

ArrayList和LinkedList的区别

是否保证线程安全： ArrayList和LinkedList都是不同步的，也就是不保证线程安全；
底层数据结构： ArrayList底层使用的是Object 数组；LinkedList底层使用的是 双向循环链表 结构；
插入和删除是否受元素位置影响？ ArrayList采用数组储存，所以插入和删除元素都受元素位置的影响；LinkedList 采用链表储存，所以插入、删除元素都不受元素位置影响。
是否支持快速随机访问？ LinkedList因为使用链表储存，无法通过元素索引快速访问；而ArrayList因为底层采用Object数组储存，可以通过索引快速随机访问。使用下标访问一个元素，ArrayList 的时间复杂度是 O(1)，而 LinkedList 是 O(n)。
内存空间占用： ArrayList的空间浪费主要体现在在List列表的结尾都会预留一定的空间容量，而LinkedList的空间花费体现在他的每一个元素都需要消耗比ArrayList更多的空间（因为要储存直接后继和直接前驱以及数据）。

ArrayList 和 Vector 的区别是什么？

Vector是同步的，而ArrayList不是。然而，如果你寻求在迭代的时候对列表进行改变，你应该使用CopyOnWriteArrayList。
ArrayList比Vector快，它因为有同步，不会过载。
ArrayList更加通用，因为我们可以使用Collections工具类轻易地获取同步列表和只读列表。

ArrayList和Vector和LinkedList的区别？

ArrayList: 底层数据结构是数组，查询快，增删慢。线程不安全，效率高
Vector: 底层数据结构是数组，查询快，增删慢。线程安全，效率低
LinkedList: 底层数据结构是链表，查询慢，增删快。线程不安全，效率高

谈谈 ArrayList 的扩容机制

Java中基本数组都是定长的，一旦被实例化后就不能改变其长度，意味着创建数组时必须确定数组的容量大小。而很多情况下，数组的长度不是确定的，需要动态增减，ArrayList的出现就解决了这一问题。

ArrayList的扩容机制表现在add()方法上，先看add()方法的源码：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//获取最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

当向ArrayList对象中添加新元素时，首先会调用ensureCapacityInternal(size)方法，size为最小扩容量；ensureCapacityInternal()方法会首先调用calculateCapacity来确定需要的最小容量；最后调用ensureExplicitCapacity()方法判断是否需要扩容。最后判断所需最小容量如果大于当前数组的空间大小，则需要扩容，调用grow()方法扩容：

private void grow(int minCapacity) {
    // 获取ArrayList中elementDaata数组的长度
    int oldCapacity = elementData.length;
    // 扩容至原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 判断新的数组容量够不够
    // 够了就直接使用这个长度创建新数组
    if (newCapacity - minCapacity < 0)
        // 不够就将数组的长度设置为需要的长度
        newCapacity = minCapacity;
    // 检查此时的最大值是否溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 调用Arrays.copyOf()将elementData数组数据拷贝到新数组
    // 并将elementData指向新数组newCapacity的内存地址
    elementData = Arrays.copyOf(elementData, newCapacity);
}

总结： ArrayList 扩容的本质就是计算所需扩容size得到新的数组，将原数组中的数据复制到新数组中，最后将原数组指向新数组在堆内存的引用地址即可。

HashMap 和 Hashtable 有什么区别？

hashMap去掉了HashTable的contains方法，但是加上了containsValue（）和containsKey（）方法；
HashMap和HashTable都实现了Map接口，主要区别在线程安全性、同步、速度；
线程是否安全： HashMap非同步线程不安全，HashTable同步线程安全。HashTable内部的方法都经过synchronized修饰；
效率: HashMap线程不安全，效率高；HashTable线程安全，效率低；
对null key和null value的支持： HashMap中，null可以作为key，这样的key只有一个，但可以有多个key对应的值为null；在HashTable中的key不能为null；
底层数据结构： JDK1.8后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阀值时（默认是8），将链表转换为红黑树，以减少搜索时间。HashTable没有这样的机制；

HashMap和HashSet区别?

HashSet底层采用HashMap实现

HashMap	HashSet
实现了Map接口	实现了Set接口
储存键值堆	仅储存对象
调用`put()` 向Map中添加元素	调用`add()` 向Set中添加元素
`HashMap` 使用`Key` 计算`HashCode`	`HashSet` 使用成员对象来计算`hashCode` 值，对于两个对象来说，`hashCode` 可能相同，所以用`equals` 判断对象的相等性

HashSet如何检查重复？

在前面讲hashCode和equals时就提到了，HashSet集合同样适用。向HashSet中存入一个元素，HashSet首先会根据对象的hashCode值判断当期集合中此hashCode对应的位置有没有值，如果没有就直接添加，如果有就再调用equals方法比较两个对象是否相同，相同就不再储存（保证了Set集合不重复的特性），否则就散列到其他位置储存。

如何决定使用 HashMap 还是 TreeMap？

对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大小，也许向HashMap中添加元素会更快，将Map换为TreeMap进行有序key的遍历。

说一下 HashMap 的实现原理？

<=JDK1.7: Table数组 + Entry链表
>=JDK1.8: Table数组 + Entry链表/红黑树

HashMap概述：HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap的数据结构：在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

当我们往Hashmap中put元素时,首先根据key的hashcode重新计算hash值,根据hash值得到这个元素在数组中的位置(下标)，如果该数组在该位置上已经存放了其他元素，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放入链尾；如果数组中该位置没有元素，就直接将该元素放到数组的该位置上。

需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn)

说一下 HashSet 的实现原理？

HashSet底层由HashMap实现
HashSet的值存放于HashMap的key上
HashMap的value统一为PRESENT

Collection 和 Collections 有什么区别？

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

Comparable和Comparator的区别？

Comparable接口来自java.lang包，提供compareTo(Object obj) 方法排序
Comparator接口来自java.util包，提供compare(Object obj1, Object obj2)方法排序

当需要对一个集合采用一种方式排序，使用Comparable接口；如果需要对一个集合采用两种排序方式就使用Comparator接口。

ConcurrentHashMap

分段锁技术：https://blog.csdn.net/qq_42451835/article/details/104266687
JavaGuide：ConcurrentHashMap
读操作为什么不用加锁：https://blog.csdn.net/ahilll/article/details/82659798

ConcurrentHashMap实现线程安全的方式

JDK 1.7 及以前：ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

一个 Segment 数组包含多个 HashEntry。

JDK1.8 的实现降低锁的粒度，JDK1.7 版本锁的粒度是基于 Segment 的，包含多个 HashEntry，而 JDK1.8 锁的粒度就是 HashEntry（首节点）
ConcurrentHashMap的读操作要加锁吗？
不需要，使用了 volatile 关键字修饰了 Node 中的 val 和 next 保证了可见性。
ConcurrentHashMap的迭代器是强一致性的迭代器还是弱一致性的迭代器
弱一致性，主要是为了提升效率，是一致性与效率之间的一种权衡。要成为强一致性，就得到处使用锁，甚至是全局锁，这就与 Hashtable 和同步的 HashMap 一样了。
迭代器
什么是迭代器？

Iterator接口中提供了很多对集合元素迭代的方法。每个集合中都有可以返回迭代器对象的方法iterator()。迭代器在迭代的过程中可以删除底层集合的元素。

Iterator和ListIterator的区别？

Iterator可以用来遍历Set和List集合，但是ListIterator只能遍历List
Iterator对集合只能向前遍历（next()）；而ListIterator可以向前遍历（next()），也可以向后遍历（previous()）
ListIterator实现了Iterator接口

Java集合框架总结

Collection

List

ArrayList: Object数组，线程不安全，查询快，增删慢，效率高
Vector: Object数组，线程安全，查询快，增删慢，效率低
LinkedList: 双向链表，线程不安全，查询慢，增删快，效率高

Set
HashSet: 无序、唯一，基于HashMap实现，底层采用HashMap存储元素
LinkedHashSet: LinkedHashSet继承自HashSet，并且其内部通过LinkedHashMap实现
TreeSet: 有序、唯一，红黑树

Map
HashMap: JDK1.8之前HashMap由数组和链表组成，数组是HashMap的主体，链表是为了解决Hash冲突问题。JDK1.8之后当Table中Node数量大于8时，就将链表转换为红黑树，以减少搜索时间提高效率。
LinkedHashMap: LinkedHashMap继承自HashMap，所有他的底层仍然由数组和链表/红黑树实现。另外，LinkedHashMap在上面的结构基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。
HashTable: 数组+链表组成。数组时HashTable的主体，链表是为了解决Hash冲突问题
TreeMap: 红黑树

本面试文档部分来自：https://www.zhihu.com/question/27858692/answer/787505434

【技巧】Java技术手册

Java 容器

容器