Java集合

Java 集合概览

Java 集合， 也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。

如何选用集合

主要根据集合的特点来选用，比如我们需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。

当我们只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。

List, Set, Queue, Map 四者的区别

• List(对付顺序的好帮手): 内部存储一系列可重复的对象，是一个有序集合，对象按插入顺序排列
• Set(注重独一无二的性质): 内部存储一系列不可重复的对象，且是一个无序集合，对象排列顺序不一
• Queue(实现排队功能的叫号机): 是一个队列容器，其特性与List相同，但只能从队头和队尾操作元素
• Map(用 key 来搜索的专家): 存储<key,value>键值对，查找元素时通过key查找value

List

List接口直接继承Collection接口，是可以存储重复元素的集合，并且元素按照插入顺序有序排列，且可以通过索引访问指定位置的元素

Vector

Object[] 数组

由于每个操作都被synchronized关键字修饰，性能低下被淘汰

线程安全情况下，使用ArrayList集合

并发环境下，使用CopyOnWriteArrayList

Stack

Stack继承Vector，是一种后入先出的容器，性能原因淘汰

取而代之的是Deque接口，其实现有ArrayDeque，该数据结构更加完善、可靠性更好，依靠队列也可以实现LIFO的栈操作，所以优先选择ArrayDeque实现栈

Arraylist

Object[] 数组

1. 具备随机访问特点，访问元素的效率较高，ArrayList在频繁插入、删除集合元素的场景下效率较低
2. 底层使用数组作为存储结构，具备查找快、增删慢的特点
3. 线程不安全
4. 首次扩容后的长度为10，调用add()时需要计算容器的最小容量．如果elementData为空数组，会将最小容量设为10，之后会将数组长度完成首次扩容到10
5. 集合从第二次扩容开始，数组长度将扩容为原来的1.5倍，即：newLength = oldLength * 1.5

LinkedList

双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)

1. LinkedList底层没有扩容机制，使用双向链表存储元素，所以插入和删除元素效率较高，适用于频繁操作元素的场景
2. LinkedList不具备随机访问的特点，查找某个元素只能从head或tail指针一个一个比较，所以查找中间的元素时效率很低
3. LinkedList查找某个下标index的元素时做了优化，若index > (size / 2)，则从head往后查找，否则从tail开始往前查找
4. 实现Deque接口，使得LinkedList可以用做双端队列

Set

Set接口继承了Collection接口，是一个不包括重复元素的集合

HashSet

无序，唯一，基于 HashMap 实现的，底层采用 HashMap 来保存元素

1. 底层由数组+链表+红黑树组成
2. 由于采用HashMap实现，而HashMap本身线程不安全，在HashSet中没有添加额外的同步策略，所以HashSet也线程不安全
3. 存入HashSet的对象状态最好不要发生变化，因为有可能改变状态后，在集合内部出现两个元素o1.equals(o2),破快equals()的语义

LinkedHashSet

• LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样，不过还是有一点点区别的

1. 继承自HashSet，LinkedHashSet调用父类构造方法初始化map时是LinkedHashMap而不是HashMap
2. 由于LinkedHashMap不是线程安全的，且在LinkedHashSet中没有添加额外的同步策略，所以LinkedHashSet也不是线程安全的

TreeSet

TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)

1. TreeSet的所有操作都会转换为对TreeMap的操作，TreeMap采用红黑树实现，任意操作的平均时间复杂度为0(logN)
2. TreeSet是一个线程不安全的集合
3. TreeSet常应用于对不重复的元素定制排序

Queue

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

Queue 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

Deque 接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈

ArrayDeque

Object[] 数组 + 双指针，最小容量是8(JDK 1.8)，在JDK 11默认容量已经是16了

LinkedList采用链表实现双端队列,ArrayDeque使用数组实现双端队列

ArrayDeque作为栈时比Stack性能好，作为队列时比LinkedList性能好

PriorityQueue

Object[] 数组来实现二叉堆

1. PriorityQueue是基于优先级堆实现的优先级队列，而堆是用数组维护的
2. PriorityQueue适用于元素按优先级处理的业务场景

Map

Map接口是有<key,value>组成的集合，由key映射到唯一的value，所以Map不能包含重复的key，每个键至多映射一个值

HashMap

JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间

1. 它是集合中最常用的Map集合类型，底层由数组+链表+红黑树组成
2. HashMap不是线程安全的
3. 插入元素时，通过计算元素的哈希值，通过哈希映射函数转换为数组下标；查找元素时，同样通过哈希映射函数得到数组下标定位元素的位置

LinkedHashMap

LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

1. 它底层维护了一条双向链表，因为继承了HashMap，所以它也不是线程安全的
2. LinkedHashMap可实现LRU缓存淘汰策略，其原理是通过设置accessOrder为true并重写removeEldestEntry方法定义淘汰元素时需满足的条件

TreeMap

红黑树（自平衡的排序二叉树）

1. 它底层是由红黑树这种数据结构实现的，所以操作的时间复杂度恒为0(logN)
2. TreeMap可以对key进行自然排序或自定义排序，自定义排序时需要传入Comparator，而自然排序要求key实现Comparable接口
3. TreeMap不是线程安全的

WeakHashMap

WeakHashMap日常开发中比较少见，它是基于普通的Map实现的，而里面Entry中的键在每一次的垃圾回收都会被清除掉，所以非常适用于短暂访问、仅访问一次的元素缓存在WeakHashMap中，并尽早的把它回收掉

1. 它的键是一种弱键，放入WeakHashMap时，随时会被回收掉，所以不能确保某次访问元素一定存在
2. 它依赖普通的Map进行实现，是一个非线程安全的集合
3. WeakHashMap通常作为缓存使用，适合存储那些只需访问一次、或只需保存短暂时间的键值对

HashTable

数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的

HashTable是一个线程安全的Map，它所有方法都被加上了synchronized关键字，性能在并发环境下非常差，因此被淘汰

1. HashTable底层采用数组+链表存储键值对
2. HashTable默认长度为11，负载因子为0.75F，每次扩容为原来数组长度的2倍
3. HashTable所有的操作都是线程安全的

ArrayDeque 与 LinkedList 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

• ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
• ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
• ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
• ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

HashMap 的底层实现

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

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

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。

我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。

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

主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

HashMap 和 Hashtable 的区别

1. 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
2. 效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；
3. 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
4. 初始容量大小和每次扩充容量大小的不同 ： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。
5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

HashMap 和 HashSet 区别

如果你看过 HashSet 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

HashMap 和 TreeMap 区别

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

• 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
• 实现线程安全的方式（重要）： ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。