集合
用提问题的方式回顾一些知识点
java.util包的层次结构：https://docs.oracle.com/javase/8/docs/api/java/util/package-tree.html
- 集合类特点是什么？
- 只能存储引用数据类型
- 可以自动地调整自己的大小
- 数组和集合类都是容器，它们有何不同？
- 数组可以存储基本数据类型的数据，集合不可以。
- 数组的长度是固定的，集合可以自动调整自己的大小。
- 数组的效率高，相对来说集合效率比较低。
- 数组没有API，集合有丰富的API。
- 一般讨论集合类无非是讨论？
- 底层数据结构
- 增删改查方式
- 初始容量，扩容方式，扩容时机
- 线程安全与否
- 是否允许空，是否允许重复，是否有序
List
① ArrayList、LinkedList、Vector的实现和区别？
-
ArrayList 底层是数组 增删慢查找快 线程不安全 效率高 可存储null
-
Vector 底层是数组 增删慢查找快 线程安全 效率低 可存储null JDK1.0就已经有了
-
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值
网友评论