008. J.U.C 之并发容器类 Map

1. JDK 源码学习方法

1. 演绎推导法

• 示例：因果推理。
• 因为 JAVA 中只提供了 BIO 和 NIO 两种方式，所以一切框架中，涉及到网络处理的，都可以用这两个知识点去探究原理。

2. 归纳总结法

• 示例：可能正确的猜想。
• 线上 10 台服务器，有 3 台总是每天自动会重启，收集相关信息后，发现是运维在修改监控系统配置的时候，漏掉了提高这 3 台机器的重启阀值。

3. 类比法

• 集群概念就好像是马在拉车，一匹马拉不动的时候，就使用多匹马去拉。
• 分布式的概念，就像是理发的过程中，洗头发和剪头发是不同的人负责的。

2. 推理 HashMap 的实现

1. 涉及内容

1. 数据要存储
   • 涉及到数据结构：数组、链表、栈、树、队列。
2. 数组的插入和查找
   • 顺序查找：插入时按先后顺序插入，查找时轮询扫描进行对比。
   • 二分查找：插入时进行排序；查找时将 n 个元素分成大致相等的两部分，减少复杂度。
   • 分块查找：分块查找是二分查找和顺序查找的一种改进。
   • 哈希表：对元素的关键信息进行 hash 计算，求出下标后直接插入或查找。常用的实现是除留余数法。
3. 哈希冲突，数组位置已存在值。
   • hash(key2)=hash(key1)。链地址法；ReHash1(key2) 再次计算 hash；
4. 合理控制数组和链表的长度。
   • 动态扩容 resize()。

2. HashMap(JDK1.7)

3. HashMap(JDK1.8)

• JDK1.8 后，HashMap 中链表中元素超过一个数量后，转变为红黑树结构。

3. ConcurrentHashMap

1. JDK1.7

2. JDK1.8

4. ConcurrentSkipListMap

4. List

1. CopyOnWriteArrayList 优缺点

• CopyOnWriteArrayList 容器即写时复制的容器。
• 优点：
  • 和 ArrayList 比较，优点是并发安全，
• 缺点：
  • 多了内存占用：写数据是 copy 一份完整的数据，单独进行操作。占用双份内存。
  • 数据一致性：数据写完之后，其他线程不一定马上能读取到最新内容。

2. CopyOnWriteArrayList 原理分析

5. Set

6. Queue

1. Queue API

• Queue - 队列数据结构的实现。分为阻塞队列和非阻塞队列。下列蓝色区块，为阻塞队列特有方法。

2. 常用队列

• ArrayBlockingQueue
• LinkedBlockingQueue
• ConcurrentLinkedQueue (并发行更好，cas 机制)
• SynchronousQueue
• PriorityBlockingQueue

3. SynchronousQueue(同步队列)

4. PriorityBlockingQueue(优先级队列)