手写系列-并发集合

基础数据结构的编写，红黑树、B+树。对比二叉树、B树的区别。

手写HashMap

HashMap根据存入的键值对中的key计算对应的index，也就是它在数组中的存储位置。当发生哈希冲突时，即不同的key计算出了相同的index，HashMap就会在对应位置生成链表。当链表的长度超过8时，链表就会转化为红黑树。

手写链表

单向链表Node数据结构

add节点的操作流程

手写红黑树

https://blog.csdn.net/monk0271_chen/article/details/122144752

场景一：计数法限流。

static class TreeNode {

int val;

? ? TreeNodeleft;

? ? TreeNoderight;

? ? TreeNode(){}

TreeNode(int val){this.val = val;}

TreeNode(int val, TreeNode left, TreeNode right){

this.val = val;

? ? ? ? this.left = left;

? ? ? ? this.right = right;

? ? }

}

ConcurrentHashMap应用

场景一：计数法限流。

使用线程池和countdownlatch模拟高并发场景。

一段有并发问题的代码

上述increase方法有线程不安全的风险，原因在于map.get操作和map.put操作是组合操作，没有保证原子性。

模拟场景：线程A初始化线程后，map当中的值是url,1L; 线程B和线程C同时抵达现场，同时拿到oldValue=1L ; 同时调用了put（url, 1L+1L）方法。调用后结果为2L。

解决方案：

1 通过加同步锁解决。在crease方法上增加synchronized锁；或者Hashmap+writereadlock解决。

2 通过concurrenthashmap.replace方法也就是CAS操作来解决这个问题。

2. concurrenthashmap的computeIfAbsent方法有性能问题，原因是哪怕是key存在的情况下，computeIfAbsent也会去进入到synchronized代码中。

异常：

运行时异常：也就是runtimeException。包括indexoutofbox exception; nullpointer exception; ArrayStoreException; ArithmeticException;? classcastexception;?

检查异常：

IOException; ClassNotFoundException; Nosuchfield Exception; interrupted exception;?