目前没时间排版，已排版内容可点击此链接：
https://blog.csdn.net/qq_36010886/article/details/126624180
Java集合概述
? ? ? ? Java 集合， 也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。
List, Set, Queue, Map 四者的区别？
List(对付顺序的好帮手): 存储的元素是有序的、可重复的。
Set(注重独一无二的性质): 存储的元素是无序的、不可重复的。
Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，"x" 代表 key，"y" 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。
List
ArrayList： Object[] 数组
Vector：Object[] 数组
LinkedList： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)
Set
HashSet(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素，底层实现上是对 HashMap进行了一个包装，也就是说HashSet里面有一个HashMap(适配器模式)。插入方式以元素+map形式? 故为有序。
LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。
TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)。支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)
Queue
PriorityQueue: Object[] 数组来实现二叉堆
ArrayQueue: Object[] 数组 + 双指针
Map
HashMap： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
Hashtable： 数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的
TreeMap： 红黑树（自平衡的排序二叉树）。继承自AbstractMap实现了NavigableMap接口和SortedMap 接口。有对集合内元素的搜索的能力和对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。
ArrayList 和 Vector 的区别
ArrayList 是 List 的主要实现类，底层使用 Object[ ]存储，适用于频繁的查找工作，线程不安全 ；
Vector 是 List 的古老实现类，底层使用Object[ ] 存储，线程安全的。
ArrayList 和 Vector 的区别
ArrayList 是 List 的主要实现类，底层使用 Object[ ]存储，适用于频繁的查找工作，线程不安全 ；
Vector 是 List 的古老实现类，底层使用Object[ ] 存储，线程安全的。
List特性
? 数组的扩容为1.5倍；数组的删除都是把要删除的元素后面的元素迁移，把最后一个元素置为null，然后重新创建一个新的数组，copy过去，copy的时候size-1。原来的数组失去引用，后续会被GC回收.
ArrayList
? ? ? ? ArrayList实现了List接口、RandomAccess 接口，可以插入空数据，也支持随机访问。ArrayList 相当于动态数据，其中最重要的两个属性分别是: elementData 数组，以及 size 大小。初始数组容量(capacity)默认为10，超过长度自动扩容，扩容为1.5倍。 ? ? 由于 ArrayList 是基于动态数组实现的，所以并不是所有的空间都被使用。因此使用了 transient 修饰，可以防止被自动序列化。因此 ArrayList 自定义了序列化与反序列化，ArrayList 只序列化了被使用的数据。 ? ? ArrayList删除方法有两个，按照索引删除和直接删除对象。底层实现都是把指定元素删除，后面的元素前移，然后把最后一个元素置为null，用于提醒gc可以回收。
Vector
? ? ? Vector? 也是实现于 List 接口，底层数据结构和 ArrayList 类似。无transient修饰。Vector的 add() 方法的时候使用 synchronized修饰，是线程安全的，但是开销较大。
LinkedList ?
? ? ? ? LinkedList 基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。LinkedList没有实现同步，可以先采用Collections.synchronizedList()方法对其进行包装。LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(Stack)? ? ? ? LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。当链表为空的时候first和last都指向null。linkedList删除都是移动指针。clear() 为了让GC更快可以回收放置的元素，需要将node之间的引用关系赋空。
Stack & Queue
? ? ? Java已不推荐使用Stack，而是推荐使用更高效的ArrayDeque；Queue只是一个接口，当需要使用队列时也就首选ArrayDeque了(次选是LinkedList)。Queue接口继承自Collection接口，Deque 继承自 Queue接口，由于Deque是双向的，所以可以对队列的头和尾都进行操作，它同时也支持两组格式，一组是抛出异常的实现；另外一组是返回值的实现。
? ? ? ? ArrayDeque和LinkedList是Deque的两个通用实现。ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组(circular array)，也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的(not thread-safe)，当多个线程同时使用的时候，需要手动同步；另外，该容器不允许放入null元素。
PriorityQueue
? ? ? ? PriorityQueue 优先队列。基于堆结构实现，可以用它来实现优先队列。 优先队列的作用是能保证每次取出的元素都是队列中权值最小的。(Java的优先队列每次取最小元素，C++的优先队列每次取最大元素)。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器。
? ? ? ? ? Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树(complete binary tree)实现的小顶堆，也就意味着可以通过数组来作为PriorityQueue的底层实现。
Map特性
? ? ? ? HashMap 基于哈希表实现。HashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素；除该类未实现同步。影响HashMap的性能: 初始数组容量16(inital capacity)和负载系数(load factor)0.75 ，超过容量*0.75 就会自动扩容，每次扩容是原来容量的2倍。容量是指存储的键值对的数量。
? ? ? ? HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。链表则是主要为了解决哈希冲突而存在的。
?? 扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。
?? 所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表/链表+红黑树 数组，数组中每一格就是一个（1.7链表、1.8链表+红黑树）。若遇到哈希冲突，则将冲突的值加到链表/链表+红黑树中即可。
? JDK1.7 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 HashMap 由数组+链表+红黑树。JDK1.8之后增加红黑树要求：1、链表长度大于阈值（默认为 8）；2、HashMap 数组长度超过 64。
Java7 是先扩容后插入新值的，Java8 先插值再扩容。
? Java7中Hashmap底层采用的是Entry对数组，1.8之后是Node对象。
? ? ? ? HashMap在多线程情况下会导致死循环，主要原因在于并发下调用 resize() 方法里的 rehash() 时，容易出现环形链表。这样当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标时就会出现死循环。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap
? ? ? ? HashTable 和 HashMap 类似，但它是线程安全的，内部的方法基本都经过synchronized 修饰。LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表/红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。。
ConcurrentHashMap 和 Hashtable 的区别
? ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
底层数据结构：
? JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，
? JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。
? Hashtable 底层数据结构采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
实现线程安全的方式（重要）：
① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一段数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
? JDK1.8 是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。
ConcurrentHashMap
? ? ? JDK1.7的 ConcurrentHashMap 是 Segment 数组 + HashEntry 数组 + 链表；JDK1.8是 Node 数组 + 链表 / 红黑树。不过Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。当冲突链表达到一定长度时，链表会转换成红黑树。
ConcurrentHashMap 线程安全的具体实现方式/底层具体实现
JDK1.7
?? 首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。
?? 一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。
JDK1.8
?? ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）
?? synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。
总结
?? Java7 中 ConcruuentHashMap 使用的分段锁，也就是每一个 Segment 上同时只有一个线程可以操作，每一个 Segment 都是一个类似 HashMap 数组的结构，它可以扩容，它的冲突会转化为链表。但是 Segment 的个数一但初始化就不能改变。
?? Java8 中的 ConcruuentHashMap 使用的 Synchronized 锁加 CAS 的机制。结构也由 Java7 中的 Segment 数组 + HashEntry 数组 + 链表 进化成了 Node 数组 + 链表 / 红黑树，Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树，在冲突小于一定数量时又退回链表。
工具
Comparator 定制排序
Collections 集合工具类
疑问
一、HashSet 如何检查重复？
HashSet的add()方法只是简单的调用了HashMap的put()方法，并且判断了一下返回值以确保是否有重复元素。在 JDK1.8 中，实际上无论HashSet中是否已经存在了某元素，HashSet都会直接插入，只是会在add()方法的返回值处告诉我们插入前是否存在相同元素。
二、HashMap 的长度为什么是 2 的幂次方
? ? ? ? 为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。HashMap的下标计算方法是“ (n - 1) & hash”。
常见用法
集合判空 isEmpty()
集合转Map Collectors.toMap(注意当 value 为 null 时会抛 NPE 异常)
? ? ? ? 内部调用了 Map 接口的 merge() 方法.
集合遍历
? ? ? ? 普通for循环、迭代器。注意：迭代器的增删不建议使用，容易出现fail-fast 机制。
集合去重
? ? ? ? 可以利用set集合特性去重或者list的contains
集合转数组
? ? ? ? list.toArray(new String[0]);
数组转集合
? ? ? ? Arrays.asList() 传递的数组必须是对象数组，而不是基本类型