集合是数据结构的载体
Java集合类图，参考Java源码
红色：接口
蓝色：抽象类
绿色：并发包中的类
灰色：早期线程安全的类
数据结构与时间复杂度
数据结构：指逻辑意义上的 数据组织方式 及其 对应的处理方式
数据组织方式
线性结构、树结构、图结构、哈希结构
数据处理方式
增删改查：以某种特定的算法实现数据的增加、删除、查找、遍历
从最好的到最坏的时间复杂度如下
常数级O(1)，对数级O(logN)，线性级(N)，线性对数级O(NlogN)，平方级O(N^2)，指数级O(2N)， 阶乘级(N!)
HashMap的基本概念
哈希类集合的三个基本存储概念
| 名称 | 说明 |
|---|---|
| table | 存储所有节点数据的数组 |
| slot | 哈希槽。即table[i]这个位置 |
| bucket | 哈希桶。table[i]上的所有元素形成的表或树的集合 |
HashMap的主干是一个Entry数组
Entry是HashMap的基本组成单元，每一个Entry包含Node内部类
HashMap的哈希算法
如何为初始容量为13的HashMap分配存储空间？
应该分配16个空间（比13大的最小二的整数幂）
利用 -1(补码1111 1111 1111 1111 1111 1111 1111 1111)位移获取最接近13的1111...，进而获取二的整数幂 解决的问题： 左边的1应该往右边移动多少位？
- numberOfLeadingZeros就是计算移动多少位的方法
- 入参13-1=12，执行红色框代码 if(i >= 1 << 2){n -= 2; i >>>= 2;}
- (12 >= 4)为true，n = 29，i = 11(二进制)
- n - (i >>> 1) = 28
- -1 往右边移动28位，得到1111(15)
- 经由tableSizeFor()判断，返回 n + 1 = 16
- 分配的内存空间为16
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0)? 1 : (n > MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// 跟上面的一样
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
if(n < 0) {
return 1;
} else if(n > MAXIMUM_CAPACITY) {
return MAXIMUM_CAPACITY;
} else {
return n + 1;
}
}
public static int numberOfLeadingZeros(int i) {
if(i <= 0) {
return i == 0 ? 32 : 0;
}
int n = 31;
if(i >= 1 << 16){n -= 16; i >>>= 16;} // 65536
if(i >= 1 << 8){n -= 8; i >>>= 8;} // 256
if(i >= 1 << 4){n -= 4; i >>>= 4;} // 16
if(i >= 1 << 2){n -= 2; i >>>= 2;} // 4
return n - (i >>> 1);
}
>>>无符号右移
>>有符号右移
位移的好处就是快，不需要两个运算器，在晶体管内移动，无需加法器（会很慢）
写 1 << 2 而不是直接写 4 的原因，在计算机内还需要对4进行转换，不如直接位移
if(i >= 1 << 2){n -= 2; i >>>= 2;}的目的：得到挪动的位数
现在是用1101(13) 找 1111
具体做法就是用 -1 (1111 1111 1111 1111 1111 1111 1111 1111)来挪，看挪动的位数
(算法就是上面的算法，Java已经给好了)
最后找到1111后，经过判断后即可返回待分配的空间
并发处理
什么是并行与并发
并行是指同时处理多任务的能力
并发是指在某一时间段内，多任务交替处理的能力
同一CPU不同时刻交替执行不同的方法，是并发
不同CPU同一时刻执行不同的方法，是并行
延伸到计算机线程处理过程，各个线程轮流占用CPU的计算资源，可能会出现某个线程尚未执行完就不得不中断的情况，容易导致线程不安全
线程安全问题只在多线程环境下才出现，单线程串行执行不存在此问题
保证高并发场景下的线程安全，可以从以下四个维度考量
- 数据单线程内可见
- 只读对象
- 线程安全类
- 同步锁机制
Abstract 抽象：包含5个抽象方法，具体由子类实现
Queued 队列：利用队列来管理竞争共享资源的多线程
Synchronizer 同步器：是解决多线程同步问题的工具
AQS的使用场景1、线程同步类
2、线程池
3、线程安全Queue/List/Map
线程与线程池
线程池的作用
1、管理并复用线程、控制最大并发数等
2、增加对线程的管理，快速排查问题
3、实现任务线程队列缓存策略和拒绝机制
4、实现某些与时间相关的功能，如定时执行、周期执行等
5、隔离线程环境
线程池的用处
1、消息框架实现消费的线程管理
2、数据库实现SQL语句执行的线程管理
3、RPC框架内实现长链接的线程管理
