代码拉取完成，页面将自动刷新
同步操作将从 帝八哥/JavaBooks 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
集合这一块，问就是并发问题，但前提先有总体了解。
面试官：谈谈集合吧
我：可以的，我们首先要介绍集合顶层接口Collection、Map，而List、Queue、Set实现了Collection接口，List又有ArrayList、LinkedList，Queue又有LinkedList、PriorityQueue，Set又有HashSet、TreeSet、LinkedHashSet等。Map又有HashMap，TreeMap，LinkedHashMap，当然HashTable是继承Dictionary接口，实现了Map。
此时就开始谈JUC下的集合，比如HashMap对应的ConcurrentHashMap，ConcurrentSkipListMap；比如ArrayList对应CopyOnWriteArrayList，Set对应的CopyOnWriteArraySet等。阻塞队列暂时先不谈哈。
其实就是size++ 这一步的问题。 越界就是两个线程临界值去扩容都满足，于是一个线程size++导致的，另外一个线程就溢出了，null就是element[size] = e,第一个线程还没来得及size++，第二个线程就在原先的索引上把值给覆盖了，并且在下一个索引为null。
越界
ArrayIndexOutOfBoundsException。null
element[0] = e上。因为获取 key 在数组中对应的下标是通过 key 的哈希值与数组长度 -1 进行与运算，如：tab[i = (n - 1) & hash]
n 为 2 的整数次幂，这样 n-1 后之前为 1 的位后面全是 1，这样就能保证 (n-1) & hash 后相应的位数既可能是 0 又可能是 1，这取决于 hash 的值，这样能保证散列的均匀，同时与运算效率高
如果 n 不是 2 的整数次幂，会造成更多的 hash 冲突
举个例子：如 16：10000, 16-1=15：1111, 1111 再与 hash 做 & 运算的时候，各个位置的取值取决于 hash，如果不是2的整数次幂，必然会有的0的位，这样再进行 & 操作的时候就为 0了，会造成哈希冲突。注意：HashMap的tableSizeFor方法做了处理，能保证n永远都是2次幂
负载因子过低，频繁扩容，扩容会重新哈希，性能下降;负载因子过高，容易浪费容量.（经验+概率）
在 hash 函数设计合理的情况下，发生 hash 碰撞 8 次的几率为百万分之 6，概率说话。(泊松分布)
6是因为如果 hash 碰撞次数在 8 附近徘徊，会一直发生链表和红黑树的转化，为了预防这种情况的发生。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash 函数是先拿到通过 key 的 hashcode，是 32 位的 int 值，然后让 hashcode 的高 16 位和低 16 位进行异或操作。这个也叫扰动函数，这么设计有二点原因：
先说1.7吧
for (HashMapEntry<K, V> e : table) {
// 如果这个数组位置上有元素且存在哈希冲突的链表结构则继续遍历链表
while (null != e) {
//取当前数组索引位上单向链表的下一个元素
HashMapEntry<K, V> next = e.next;
//重新依据hash值计算元素在扩容后数组中的索引位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; // 这一步和下一步就是头插法了，并且这两步出现线程不安全死循环问题
newTable[i] = e;
e = next; // 遍历链表
}
}
1.8 HashMap的扩容使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。也就是说省略了重新计算hash值的时间，而且新增的1位是0还是1机会是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。如果在新表的数组索引位置相同，则链表元素不会倒置。
ReentrantLock（可能还会扯AQS）。scanAndLockForPut() 自旋获取锁。
MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。总的来说：
在 JDK1.7 中，第一种方案他会使用不加锁的模式去尝试多次计算 ConcurrentHashMap 的 size，最多三次，比较前后两次计算的结果，结果一致就认为当前没有元素加入，计算的结果是准确的。 第二种方案是如果第一种方案不符合，他就会给每个 Segment 加上锁，然后计算 ConcurrentHashMap 的 size 返回
1.7 查询遍历链表效率太低（种种原因）。其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性（会扯1.6对synchronized的优化）
synchronized锁写入数据ConcurrentHashMap 提供了 baseCount、counterCells 两个辅助变量和一个 CounterCell 辅助内部类。sumCount() 就是迭代 counterCells 来统计 sum 的过程。 put 操作时，肯定会影响 size()，在 put() 方法最后会调用 addCount() 方法。
在addCount()方法中：
缓存系统中是以缓存行（cache line）为单位存储的。缓存行是2的整数幂个连续字节，一般为32-256个字节。最常见的缓存行大小是64个字节。当多线程修改互相独立的变量时，如果这些变量共享同一个缓存行，就会无意中影响彼此的性能，这就是伪共享。
实际上：
https://zhuanlan.zhihu.com/p/40627259
HashSet中不允许有重复元素，这是因为HashSet是基于HashMap实现的，HashSet中的元素都存放在HashMap的key上面，而value中的值都是统一的一个private static final Object PRESENT = new Object();。 HashSet跟HashMap一样，都是一个存放链表的数组。这样遇到重复元素就可以返回object了(意味着不是null)，如果value是null的话，发现重复，那么就返回上一个value值null，那么不符合源码：
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
System.out.println(map.put(1, o)); // null
System.out.println(map.put(1, o));// java.lang.Object@610455d6
// 所以重复就false
TreeSet底层则采用NavigableMap这个接口来保存TreeSet集合，而实际上NavigableMap只是一个接口，实际上TreeSet还是用TreeMap来保存set元素。
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
TreeMap采用一种被称为“红黑树”的排序二叉树来保存Map中的的每个Entry——每个Entry都被当做红黑树的一个节点来对待；TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
一般说完这个，可能让你手撸LRU，你可以撸个伪代码即可。
// 双向链表+HashMap，Java中的LinkedHashMap就实现了该算法。
// get
public int get(int key) {
if (map.containsKey(key)) {
Node n = map.get(key); // 获取内存中存在的值，比如A
remove(n); //使用链表的方法，移除该节点
setHead(n); //依然使用链表的方法，将该节点放入头部
return n.value;
}
return -1;
}
// put
public void set(int key, int value) {
if (map.containsKey(key)) {
Node old = map.get(key);
old.value = value;
remove(old); // 移除旧节点
setHead(old); // 放到队头
} else {
Node created = new Node(key, value);
if (map.size() >= capacity) {
map.remove(end.key); // clear该key
remove(end); //链表也是依次
setHead(created); // 将created放入队头
} else {
setHead(created); // 如果没满，直接放入队头
}
map.put(key,created);
}
}
//lc: 146. LRU缓存机制
class LRUCache {
private int cap;
private Map<Integer, Integer> map = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if (map.containsKey(key)) {
int value = map.get(key);
// 查一次，就将查到到仍在队尾
map.remove(key);
map.put(key,value);
return value;
}
return -1;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
map.remove(key);
} else if (map.size() == cap) {
// 满了
Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
iterator.next();
iterator.remove();
}
map.put(key, value);
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
