集合
集合大家庭：
四种集合的概述：
List
特点：有序、可重复
-
ArrayList：Object[]数组 -
LinkedList： 双向链表(JDK 1.6 之前为循环链表，JDK 1.7 取消了循环)，一般不用哈哈分析：以上两种，均为不同步，即不保证线程安全。二者的插入和删除元素复杂度是否受元素位置影响 以及 是否支持快速随机访问 体现了数组和链表的区别。内存占用体现在，
ArrayList的预留空间，LinkedList每个元素占用空间更大补充：
RandomAccess接口，什么都没定义，为了标识实现这个接口的类具有随机访问功能。ArrayList实现了这个接口，LinkedList没实现。例如：在binarySearch（)方法中，它要判断传入的 list 是否RandomAccess的实例，如果是，调用indexedBinarySearch()方法，如果不是，那么调用iteratorBinarySearch()方法 -
Vector：Object[]数组，Java的Stack类继承于此古老实现类，是线程安全的
Set
特点：无序、不可重复，都不能保证线程安全
-
HashSet(无序，唯一): 基于HashMap实现的，底层采用HashMap哈希表来保存元素，不保证插入和取出顺序。 -
LinkedHashSet:LinkedHashSet是HashSet的子类，并且其内部是通过LinkedHashMap来实现的。底层是链表和哈希表。元素的插入和取出顺序满足 FIFO。有点类似于我们之前说的LinkedHashMap其内部是基于HashMap实现一样，不过还是有一点点区别的 -
TreeSet(有序，唯一): 利用红黑树(自平衡的排序二叉树)，可以自定义排序规则注意：
- 无序性不等于随机性 ，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。
- 不可重复性是指添加的元素按照
equals()判断时 ，返回 false，需要同时重写equals()方法和hashCode()方法，参考Java基础的15.3。
Queue
https://blog.csdn.net/qq_27184497/article/details/116093422
特点：有序、可重复、先后顺序
只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则
拓展了接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。
Queue 接口 |
抛出异常 | 返回特殊值 |
|---|---|---|
| 插入队尾 | add(E e) | offer(E e) |
| 删除队首 | remove() | poll() |
| 查询队首元素 | element() | peek() |
PriorityQueue:Object[]数组来实现二叉堆，优先队列ArrayQueue:Object[]数组 + 双指针
Map
特点：键值对
HashMap： JDK 1.8 之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK 1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间LinkedHashMap：LinkedHashMap继承自HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。Hashtable： 数组+链表组成的，数组是Hashtable的主体，链表则是主要为了解决哈希冲突而存在的TreeMap： 红黑树（自平衡的排序二叉树
ArrayList扩容 与 Copy 机制
扩容机制：
-
以无参构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组添加第一个元素时，数组扩容为10；
-
每次触发扩容，容量都会变成原来的 1.5 倍左右；
int newCapacity = oldCapacity + (oldCapacity >> 1) // 右移效率高 -
addAll()方法总是选择扩容一次后的容量与旧容量加上添加的元素个数的容量中取一个最大值作为新的容量，比如：当前ArrayList中有10个元素，而addAll()方法需要添加6个元素，当ArrayList触发扩容后的新容量应该为15，而旧容量加上需要添加的元素容量为16，从中取一个较大值为16，所以新容量应该为16。 -
如果预知了要添加大量的元素，可以提前设置容量。
list.ensureCapacity(int num);
Copy机制：
-
System.arraycopy()方法（本地方法）源码：
/** * 复制数组 * @param src 源数组 * @param srcPos 源数组中的起始位置 * @param dest 目标数组 * @param destPos 目标数组中的起始位置 * @param length 要复制的数组元素的数量 */ public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);使用场景：
list.add(int index, E element)public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! //arraycopy()方法实现数组自己复制自己 //elementData:源数组;index:源数组中的起始位置;elementData：目标数组；index + 1：目标数组中的起始位置； size - index：要复制的数组元素的数量； System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }eg：正常应该先扩容的，这里简化了。
// TODO Auto-generated method stub int[] a = new int[10]; a[0] = 0;a[1] = 1;a[2] = 2;a[3] = 3; // a = [0 1 2 3 0 0 0 0 0 0]; System.arraycopy(a, 2, a, 3, 8); a[2]=99; // a = [0 1 99 2 3 0 0 0 0 0]; -
Arrays.copyOf()方法（非本地方法）里面也调用了
System.arraycopy()方法，主要用于给数组扩容。int[] a = new int[3]; a[0] = 0;a[1] = 1;a[2] = 2; int[] b = Arrays.copyOf(a, 10); System.out.println("b.length"+b.length);// 输出10
ArrayDeque 与 LinkedList 都实现了Deque接口，都具有队列功能，有何区别？
ArrayDeque是基于可变长的数组和双指针来实现，而LinkedList则通过链表来实现。ArrayDeque不支持存储NULL数据，但LinkedList支持。ArrayDeque是在 JDK 1.6 才被引入的，而LinkedList早在 JDK 1.2 时就已经存在。ArrayDeque插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然LinkedList不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。ArrayDeque实现队列更好，此外还可以用来实现栈
优先队列PriorityQueue
出队顺序是与优先级相关的，即优先级高的先出队列。一般手撕算法使用
- 利用二叉堆的数据结构实现，底层使用变长数组 存储数据；
- 实现了在O(log n)时间复杂度内插入元素 和 删除堆顶元素；
- 非线程安全的，不支持
NULL； - 只能存放实现
comparable接口的对象； - 默认是小顶堆，可以接收一个
Comparator作为构造函数，自定义排序。
Comparable 和 Comparator的区别
简单区分：Comparable是在类中重写使用，Comparator在集合中实现。
-
Comparable接口，包含compareTo(Object obj)方法用来排序，一般想对对象排序的话，类需要实现Comparable接口，并通过重写方法实现自定义比较规则。像Integer类等都已经实现了Comparable接口，所以不需要另外实现了// person对象没有实现Comparable接口，所以必须实现，这样才不会出错，才可以使treemap中的数据按顺序排列 // 前面一个例子的String类已经默认实现了Comparable接口，详细可以查看String类的API文档，另外其他 // 像Integer类等都已经实现了Comparable接口，所以不需要另外实现了 public class Person implements Comparable<Person> { private String name; private int age; // 省略构造器、get、set方法 /** * T重写compareTo方法实现按年龄来排序 */ @Override public int compareTo(Person o) { if (this.age > o.getAge()) { return 1; } if (this.age < o.getAge()) { return -1; } return 0; } }// 测试 public static void main(String[] args) { // TreeMap会对键值排序 TreeMap<Person, String> pdata = new TreeMap<Person, String>(); pdata.put(new Person("张三", 30), "zhangsan"); pdata.put(new Person("李四", 20), "lisi"); pdata.put(new Person("王五", 10), "wangwu"); pdata.put(new Person("小红", 5), "xiaohong"); // 得到key的值的同时得到key所对应的值 Set<Person> keys = pdata.keySet(); for (Person key : keys) { System.out.println(key.getAge() + "-" + key.getName()); } }
输出：5-小红
10-王五
20-李四
30-张三
-
Comparator接口，包含方法compare(Object obj1, Object obj2)一般用于Collections.sort()两参数的第二个参数，来自定义排序。ArrayList<Integer> arrayList = new ArrayList<Integer>(); // add元素之后假设 arrayList = [-1, 3, 3, -5, 7, 4, -9, -7] Collections.reverse(arrayList); // 翻转后：arrayList = [-7, -9, 4, 7, -5, 3, 3, -1] Collections.sort(arrayList); // 自然排序（升序）：arrayList = [-9, -7, -5, -1, 3, 3, 4, 7] Collections.sort(arrayList, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); // return o2 - o1; 也行 } }); // 定制排序（降序）：arrayList = [7, 4, 3, 3, -1, -5, -7, -9] // 上面是匿名内部类的方式，其实还可以用lambda表达式简化上述 Collections.sort(arrayList, (o1, o2) -> o2.compareTo(o1));
TreeMap 与 HashMap 的区别
-
都继承于
AbstractMap； -
TreeMap还实现了NavigableMap接口和SortedMap接口，使他实现了对集合内元素的快速搜索能力 和 根据键排序的能力； -
上面的
Person中Comparable接口的实现，也可以在TreeMap初始化时传入自定义排序方法TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> { int num = person2.getAge() - person1.getAge(); return Integer.compare(num, 0); }); // 这时候优先选择集合中实现的比较方式，得到于4.1相反的输出，即30、20、10、5
HashSet如何检查重复？
基本上用的都是HashMap的东西，简单调用一下map的put并返回值。源码：
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
HashMap的底层实现？
- hash值的获取，通过key的
hashcode进行扰动函数之后得到的值作为hash值，然后通过(n-1)&hash判断存放的位置，n为数组的长度；防止实现的较差的hashCode()，以减少碰撞。 - JDK 1.8之前是数组和链表；
- JDK 1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间；（源码）
- 不是线程安全的，并发情况下同时put可能导致元素丢失等情况，多并发情况下使用
ConcurrentHashMap
- 不是线程安全的，并发情况下同时put可能导致元素丢失等情况，多并发情况下使用
- JDK 1.8把插入元素的方式，从头插改为了尾插，目的是防止并发情况下出现死循环的情况。
为什么HashMap长度设为 2 的幂次方？
hash判断位置的时候，一般采用取余操作；
而取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；），也就是只有长度为 2 的幂次方的时候，才能使用 与运算& 取余操作，进而使得每一个槽都能被放入，可以减少哈希冲突，均匀分布元素 。
并且 采用二进制位操作 &，相对于 % 能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方
HashMap数组扩容的时候resize()函数采取二倍扩容，也是出于 与运算 简化rehash的目的
HashMap的扩容机制
几个参数：
- size： map的键值对数
- capacity：容量，默认为16；
- loadFactor：加载因子 取值范围0-1，默认值为 0.75。太大导致哈希冲突大，查找效率低；太小导致数组利用率低；
- threshold = capacity * loadFactor：阈值，size >= threshold 时，考虑把Node数组扩增；
put图示：
注：链表长度大于 8 ，但是数组长度不大于 64 的时候。只对数组进行扩容，不转红黑树。
resize方法进行扩容，会伴随重新一次hash分配，重新遍历hash表中所有的元素，非常耗时的，因此应该尽量避免resize
resize方法有一个阈值，如果超过了阈值就不再二倍扩容，摆了，碰撞就完事了。
HashMap的七种遍历方式？
遍历方式代码，迭代器使用？
public static void main(String[] args) {
// 创建并赋值 HashMap
Map<Integer, String> map = new HashMap();
map.put(1, "AAA");
map.put(2, "BBB");
map.put(3, "CCC DDD");
map.put(4, "EEE FFF");
map.put(5, "RRR");
// 1、迭代器 EntrySet
Iterator<Map.Entry<Integer, String>> Entryiterator = map.entrySet().iterator();
while (Entryiterator.hasNext()) {
Map.Entry<Integer, String> entry = Entryiterator.next();
System.out.println(entry.getKey() + ": " + entry.getValue());
}
System.out.println("-----------");
// 2、迭代器 KeySet
Iterator<Integer> keyIterator = map.keySet().iterator();
while (keyIterator.hasNext()) {
Integer key = keyIterator.next();
System.out.println(key + ": " +map.get(key));
}
System.out.println("-----------");
// 3、ForEach EntrySet
for (Map.Entry<Integer, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
System.out.println("-----------");
// 4、ForEach KeySet
for (Integer key : map.keySet()) {
System.out.println(key + ": " + map.get(key));
}
System.out.println("-----------");
// 5、Lambda
map.forEach((key, value) -> {
System.out.println(key + ": " + value);
});
System.out.println("-----------");
// 6、Stream API 单线程
map.entrySet().stream().forEach((entry) -> {
System.out.println(entry.getKey() + ": " + entry.getValue());
});
System.out.println("-----------");
// 7、Stream API 多线程 ， 大概率会乱序遍历
map.entrySet().parallelStream().forEach((entry) -> {
System.out.println(entry.getKey() + ": " + entry.getValue());
});
}
性能总结：
entrySet性能比keySet高出一倍之多，最好用entrySet；因为keySet遍历一遍数组之后，还有再去查询map.getKey()。- 迭代器和
forEach，最终的字节码是一样的，因此性能相同；
安全性总结：
-
不能在遍历中使用集合
map.remove()来删除数据，这是非安全的操作方式；产生fail-fast机制，报错 -
但可以使用迭代器的
iterator.remove()的方法来删除数据，这是安全的删除集合的方式；举例// Leetcode 102，二叉树层序遍历，可以使用迭代器安全删除集合元素 public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root == null) { return res; } List<TreeNode> cur = new ArrayList<>(); cur.add(root); List<TreeNode> next = new ArrayList<>(); while(cur.size()!=0) { // 记录下一层的所有节点 List<Integer> list = new ArrayList<>(); // 获取迭代器 Iterator<TreeNode> itr = cur.iterator(); // hasNext迭代 while(itr.hasNext()) { // 获取元素 TreeNode node = itr.next(); list.add(node.val); if(node.left!=null) { next.add(node.left); } if(node.right!=null) { next.add(node.right); } // 迭代器安全删除 itr.remove(); } res.add(list); List<TreeNode> tmp = next; next = cur; cur = tmp; } return res; } -
同样的我们也可以使用 Lambda 中的
removeIf来提前删除数据；或者是使用 Stream 中的filter过滤掉要删除的数据进行循环，这样都是安全的，当然我们也可以在for循环前删除数据再遍历也是线程安全的； -
总结的话，最好使用迭代器（Iterator）来遍历 entrySet 的方式，安全又高效！
ConcurrentHashMap相关
HashMap是线程不安全的，当多个线程同时put数据时，如果哈希冲突，可能造成数据错误。
HashTable是线程安全的，使用 synchronized 修饰方法保证同步，但是效率非常低下，同时只有一个线程可以访问同步方法。一般不用
为了保证并发情况的安全，HashTable 和 ConcurrentHashMap均不允许key和value为null。
key、value都不能为null原因是二义性问题，get方法返回null，不知道是key不存在还是key对应的值为null。HashMap可以使用containsKey解决，但是并发下不保证get和containsKey之间没有别的线程干扰。
底层数据结构
-
JDK 1.7 采用分段（Segment）数组 + HashEntry数组 + 链表，每一把锁只锁容器一部分数据，多线程可以访问容器不同段的内存，提高并发访问率；
-
JDK 1.8 摈弃了Segment ，采用 Node 数组 + 链表/红黑树，并发控制采用
synchronized和 CAS 来操作，看起来像是优化过且线程安全的HashMap。冲突大的时候链表转为红黑树、冲突小的时候又会退回链表。其中Node用于链表的情况、红黑树的情况要用 TreeNode。
具体实现
-
JDK 1.7 采用了继承了
ReentrantLock的 Segment 锁，一个ConcurrentHashMap包含一个Segment 数组，并且个数一旦初始化就不能改变，因此支持的并发数有限，例如Segment 数组默认大小为 16 ，即默认最多支持16个线程并发。初始化逻辑：
- 必要参数校验。
- 校验并发级别
concurrencyLevel大小，如果大于最大值，重置为最大值65536。无参构造默认值是 16. - 寻找并发级别
concurrencyLevel之上最近的 2 的幂次方值，作为初始化容量大小，默认是 16。 - 记录
segmentShift偏移量，这个值为【容量 = 2 的N次方】中的 N，在后面 Put 时计算位置时会用到。默认是 32 - sshift = 28. - 记录
segmentMask，默认是 ssize - 1 = 16 -1 = 15. - 初始化
segments[0]，默认大小为 2，负载因子 0.75，扩容阀值是 2*0.75=1.5，插入第二个值时才会进行扩容。
-
JDK 1.8 锁粒度更细了，通过优化了的
synchronized锁 和 CAS，只锁定当前链表 或者 红黑二叉树的首节点，这样只要不发生hash冲突，就不会产生并发冲突，效率大幅度提升。最大并发度 为 Node数组的大小。- 初始化：是通过自旋和 CAS 操作完成的。里面需要注意的是变量
sizeCtl，它的值决定着当前的初始化状态。- -1 说明正在初始化
- -N 说明有N-1个线程正在进行扩容
- 表示 table 初始化大小，如果 table 没有初始化
- 表示 table 容量，如果 table 已经初始化
- put实现：
- 根据 key 计算出 hashcode 。
- 判断是否需要进行初始化。
- 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
- 如果当前位置的
hashcode == MOVED == -1,则需要进行扩容。 - 如果都不满足，则利用 synchronized 锁写入数据。
- 如果数量大于
TREEIFY_THRESHOLD则要执行树化方法，在treeifyBin中会首先判断当前数组长度≥64时才会将链表转换为红黑树
- 初始化：是通过自旋和 CAS 操作完成的。里面需要注意的是变量
集合使用的一些注意事项：
-
判断集合内部元素是否为空，使用
isEmpty()方法，而非size() == 0；原因：
isEmpty()可读性好，时间复杂度低（对于concurrent包下的集合） -
在使用
java.util.stream.Collectors类的toMap()方法转为Map集合时，一定要注意当 value 为 null 时会抛 NPE 异常。class Person { private String name; private String phoneNumber; // getters and setters } List<Person> bookList = new ArrayList<>(); bookList.add(new Person("jack","18163138123")); bookList.add(new Person("martin",null)); // 空指针异常 bookList.stream().collect(Collectors.toMap(Person::getName, Person::getPhoneNumber));toMap()调用了Map的merge()，而会调用Objects.requireNonNull()方法判断value是否为 null。 -
不要在
foreach循环里进行元素的remove/add操作。remove 元素请使用Iterator方式，如果并发操作，需要对Iterator对象加锁。或者使用
fail-safe的集合类，java.util包下的全是fail-safe，而java.util.concurrent包下面的所有的类都是fail-safe的。 -
利用 Set 进行集合去重，比 List 更加高效；
-
集合转数组：使用集合转数组的方法，必须使用集合的
toArray(T[] array)，传入的是类型完全一致、长度为 0 的空数组。例如下面的例子，
new String[0]参数起到模板的作用String [] s= new String[]{ "dog", "lazy", "a", "over", "jumps", "fox", "brown", "quick", "A" }; // 转为list List<String> list = Arrays.asList(s); // 反转 Collections.reverse(list); //没有指定类型的话会报错 s=list.toArray(new String[0]); -
使用工具类
Arrays.asList()把数组转换成集合时，不能使用其修改集合相关的方法， 它的add/remove/clear方法会抛出UnsupportedOperationException异常总结
Arrays.asList()注意事项：-
Arrays.asList()是泛型方法，传递的数组必须是对象数组，而不是基本类型。否则list就会只传入一个数组的地址值，eg：
int[] myArray = {1, 2, 3}; List myList = Arrays.asList(myArray); System.out.println(myList.size());//1 System.out.println(myList.get(0));//数组地址值 System.out.println(myList.get(1));//报错：ArrayIndexOutOfBoundsException int[] array = (int[]) myList.get(0); System.out.println(array[0]);//1使用包装类，
Integer[] myArray = {1, 2, 3};解决。 -
使用集合的修改方法:
add()、remove()、clear()会抛出异常：UnsupportedOperationException原因在于
Arrays.asList()返回的不是java.util.ArrayList，而是java.util.Arrays的一个内部类，这个内部类没有实现上述方法。List myList = Arrays.asList(1, 2, 3); System.out.println(myList.getClass());//class java.util.Arrays$ArrayList
如何正确实现数组转ArrayList ？
-
手动实现工具类；
-
最简便的方法：
List list = new ArrayList<>(Arrays.asList("a", "b", "c")); -
Java 8 提供了Stream方法 （ 推荐 ）
Integer [] myArray = { 1, 2, 3 }; List myList = Arrays.stream(myArray).collect(Collectors.toList()); //基本类型也可以实现转换（依赖boxed的装箱操作） int [] myArray2 = { 1, 2, 3 }; List myList = Arrays.stream(myArray2).boxed().collect(Collectors.toList()); -
Guava（谷歌的java库）
// 不可变集合 List<String> il = ImmutableList.of("string", "elements"); // from varargs List<String> il = ImmutableList.copyOf(aStringArray); // from array // 可变集合 List<String> l1 = Lists.newArrayList(anotherListOrCollection); // from collection List<String> l2 = Lists.newArrayList(aStringArray); // from array List<String> l3 = Lists.newArrayList("or", "string", "elements"); // from varargs -
使用Apache Commons Collections
List<String> list = new ArrayList<String>(); CollectionUtils.addAll(list, str); -
使用java 9 的
List.of()Integer[] array = {1, 2, 3}; List<Integer> list = List.of(array);
-