集合

用提问题的方式回顾一些知识点

java.util包的层次结构：https://docs.oracle.com/javase/8/docs/api/java/util/package-tree.html

• 集合类特点是什么？

1. 只能存储引用数据类型
2. 可以自动地调整自己的大小

• 数组和集合类都是容器，它们有何不同？

1. 数组可以存储基本数据类型的数据，集合不可以。
2. 数组的长度是固定的，集合可以自动调整自己的大小。
3. 数组的效率高，相对来说集合效率比较低。
4. 数组没有API，集合有丰富的API。

• 一般讨论集合类无非是讨论？

1. 底层数据结构
2. 增删改查方式
3. 初始容量，扩容方式，扩容时机
4. 线程安全与否
5. 是否允许空，是否允许重复，是否有序

List

① ArrayList、LinkedList、Vector的实现和区别？

1. ArrayList 底层是数组 增删慢查找快 线程不安全 效率高 可存储null

2. Vector 底层是数组 增删慢查找快 线程安全 效率低 可存储null JDK1.0就已经有了

3. LinkedList 底层是链表 增删快查找慢 线程不安全 效率高 可存储null 实现了Deque 接口 可以用来当作栈、队列、双端队列

② ArrayList#removeAll方法优化

参考自：https://juejin.cn/post/6932039907669966855

ArrayList#removeAll(Collection c) 实际调用了 ArrayList#batchRemove(Collection c, false)。
该方法使用时间复杂度为O(n*m)的算法，在原始数组上进行一趟遍历，并调用参数中的collection的contains方法来判断当前元素是否在参数中。
如何优化：将collection转化为Set，contains方法时间复杂度将从O(m)降至O(1)。

import cn.hutool.core.date.DateUtil;
import cn.hutool.core.date.TimeInterval;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ArrayListTest {
    public static void main(String[] args) {
        //1000W数据中过滤掉100个
        ArrayList<Integer> ids1 = new ArrayList<>();
        ArrayList<Integer> ids2 = new ArrayList<>();
        for (int i = 0; i < 10_000_000; i++) {
            ids1.add(i);
            ids1.add(i);
        }

        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < 100; i++) {
            list.add(i);
            set.add(i);
        }

        TimeInterval timer = DateUtil.timer();
        ids1.removeAll(list);

        System.out.println("耗时：" + timer.intervalRestart());

        ids2.removeAll(set);
        System.out.println("耗时：" + timer.intervalRestart());
    }
}
//输出结果
//耗时：1573
//耗时：2

Map

• HashMap

① 数据结构
底层数据结构是哈希表，不保证迭代顺序，特别是不保证该顺序恒久不变；允许null键和null值
JDK 1.7 HashMap 采用数组 + 链表实现。
JDK 1.8 HashMap 采用数组 + 链表 + 红黑树实现。（当链表长度超过阈值 “8” 时，将链表转换为红黑树）

② hash冲突如何解决（使用链表和红黑树）
如果多个hashCode()的值落到同一个桶内的时候，这些值是存储到一个链表中的；最坏的情况下所有的key都映射到同一个桶中，这样HashMap就退化成了一个链表——查找时间从O(1)到O(n)。当某个桶中的记录过大的话（TREEIFY_THRESHOLD = 8），HashMap会动态的使用一个专门的treemap实现来替换掉它。

③ 扩容时机
扩容会触发resize方法，有3种扩容时机：
1、第一次添加元素时，即当hashMap的数组为null或者数组的长度为0时的初始化；
2、触发链表转红黑树、且数组容量小于64时（优先扩容而不是树化）；
3、数组元素个数size的大小超过扩容阈值时（0.75比例）；
https://blog.csdn.net/wandou9527/article/details/105953010/

④ 数组长度为什么要保证是2的幂？
扩容时避免rehash的优化：扩容时每个entry不需要再计算一次hash，新的位置要么在原位置，要么在原长度+原位置的位置
计算模的时候方便：可以直接通过位运算(capacity-1) | hash来计算出模

⑤ Hashtable 和 HashMap 区别

1、HashMap是继承自AbstractMap类，而HashTable是继承自Dictionary类。
不过它们都实现了同时实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口。

2、Hashtable比HashMap多提供了elments() 和contains() 两个方法。

3、HashMap的key-value支持key-value，null-null，key-null，null-value四种。
而Hashtable只支持key-value一种（即key和value都不为null这种形式）。
既然HashMap支持带有null的形式，那么在HashMap中不能由get()方法来判断HashMap中是否存在某个键，而应该用containsKey()方法来判断，因为使用get的时候，当返回null时，你无法判断到底是不存在这个key，还是这个key就是null，还是key存在但value是null。

4、线程安全性不同
HashMap的方法都没有使用synchronized关键字修饰，都是非线程安全的，而Hashtable的方法几乎都是被synchronized关键字修饰的。但是，当我们需要HashMap是线程安全的时，怎么办呢？我们可以通过Collections.synchronizedMap(hashMap)来进行处理，亦或者我们使用线程安全的ConcurrentHashMap。ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。

5、初始容量大小和每次扩充容量大小的不同
Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。

6、计算hash值的方法不同
为了得到元素的位置，首先需要根据元素的 KEY 计算出一个hash值，然后再用这个hash值来计算得到最终的位置

• LinkedHashMap

① 基本原理

底层数据结构是哈希表和双向链表，用这个链表来记录节点的先后顺序；允许null键和null值

② 哪两种有序

LinkedHashMap的有序性分成两种，一种是元素插入的顺序，另一种是元素访问的顺序(调用get方法)，即将最新操作的数据放在内部链表的尾部，可以用来做LRU算法。

成员变量中accessOrder属性的作用：
如果accessOrder为false，则可以按插入元素的顺序遍历元素；
如果accessOrder为true，则可以按访问元素的顺序遍历元素。

③ 如何用它实现LRU

LRU（Least Recently Used）：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

import java.util.LinkedHashMap;
import java.util.Map;

class LRU<K, V> extends LinkedHashMap<K, V> {
    // 缓存容量
    private final int capacity;

    public LRU(int capacity, float loadFactor) {
        super(capacity, loadFactor, true);
        this.capacity = capacity;
    }

    /**
     * 在每次插入新元素后LinkedHashMap会自动询问removeEldestEntry()是否要删除最老的元素，返回true最老的那个元素就会被删除
     * 重写LinkedHashMap的removeEldestEntry方法，当元素数量大于缓存（capacity）容量时删除旧元素
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > this.capacity;
    }
    public static void main(String[] args) {
        Map<String, String> map = new LRU(8, 0.75f);

        for (int i = 1; i <= 10; i++) {
            map.put(i + "", i + "");
        }

        map.forEach((k, v) -> {
            System.out.print(k + ":" + v + "  ");
        });

        System.out.println(map.get("8"));

        map.forEach((k, v) -> {
            System.out.print(k + ":" + v + "  ");
        });
    }
}
//输出结果
//3:3  4:4  5:5  6:6  7:7  8:8  9:9  10:10  8
//3:3  4:4  5:5  6:6  7:7  9:9  10:10  8:8

• TreeMap

① 数据结构

底层数据结构是红黑树；不允许null键
如果创建对象时，没有传入比较器，按照元素的自然顺序排序（key需实现Comparable接口的compareTo方法）
如果创建对象时，传入了compactor比较器，按照compactor的compare(o1, o2)进行排序

② key对象为什么必须要实现Compare接口

为了实现元素的自动排序

③ 如何用它实现一致性哈希

一致性哈希算法（consistent hashing）：对于分布式存储，不同机器上存储不同对象的数据，我们使用哈希函数建立从数据到服务器之间的映射关系。

原理：
https://www.jianshu.com/p/51acb4cbc68f
https://zhuanlan.zhihu.com/p/129049724
https://www.cnblogs.com/fanguangdexiaoyuer/p/6549306.html

目的：一般的哈希函数，在节点数量动态变化的情况下会造成大量的数据迁移，导致网络通信压力的剧增，严重情况还可能导致数据库宕机。
【hash算法的单调性Monotonicity】

实现方式：一致性哈希算法将key哈希到一个具有2^32 次方个桶的空间中，即0~(2^32)-1的数字空间中。

仍存在问题：当集群中的节点数量较少时，可能会出现节点在哈希空间中分布不平衡的问题。
【hash算法的平衡性Balance】

解决方法：虚拟节点。

TreeMap实现一致性hash算法的实现：
java.util.TreeMap.tailMap()方法通过红黑树查找比fromKey大的值时间复杂度为O(logN)，模拟hash环

④ 红黑树

https://www.cnblogs.com/LiaHon/p/11203229.html

• Hashtable

① 数据结构
底层数据结构是哈希表，不保证迭代顺序，特别是不保证该顺序恒久不变；不允许null键和null值