hashmap
Java
- 冲突链表：数组+链表
- java8：数组+链表+红黑树（链表元素大于8个时会转变为红黑树）
- 扩容：每次扩大一倍容量，一次性扩容
Go
- 冲突链表：数组+链表+溢出桶(也是链表，每个哈希桶只能装8个元素，超过8个就放到溢出桶中，每个溢出桶也是8个元素)
- 扩容：
- 翻倍扩容：装载因子超过6.5
- 等量扩容：溢出桶太多
- 增量扩容：每次对 hashmap 进行写操作会迁移一到两个哈希桶
线程安全的hashmap
Java
ConcurrentHashMap
- java5到java7：
- 采用分段锁的机制实现：segment（默认16个） + 哈希桶
- 扩容：segment不能扩容，只会对segment的哈希桶进行扩容，因为是对segment的哈希桶进行扩容，不会有并发问题（需要先获取到segment的锁）
- Java8：
- 数组+链表+红黑树，加锁通过 CAS 和 Syncchronized 实现
- 扩容：支持多线程同时进行扩容（每个线程负责不同的哈希桶）
Go
sync.Map
- read map + dirty map
- 读： 先读 read map, read map 读不到就加锁读 dirty map
- 增改：如果 read map 存在该key并且没有标记删除，直接更新（CAS）；否则加锁更新 dirty map
- 删：read map 标记删除；dirty map 直接删除
- 读写分离，适合读多写少的场景，不适合大量写的场景
互斥锁
Java
Synchronized
- java语言的关键字，由jvm实现的可重入、非公平、不可被中断的互斥锁
- 都是针对对象进行加锁：类锁对应的是类对象，可以修饰方法、代码块
- 实现原理：
- 通过 monitorenter 和 monitorexit 指令进行加锁和释放锁
- 通过 monitor 计数实现可重入
- 锁优化：
- 锁粗化：减少不必要的紧连在一起的unlock、lock操作，将多个连续的锁扩展成一个范围更大的锁
- 锁消除：通过运行时JIT编译器的逃逸分析来消除一些没有在当前同步块以外被其他线程共享的数据的锁保护
- 偏向锁：加解锁不使用CAS操作，针对只有一个线程访问同步块的场景
- 轻量级锁：如果有多个线程访问同步块，得不到锁的线程会自旋等待锁，针对同步块执行速度非常快的场景
- 重量级锁：如果有多个线程访问同步块，得不到锁的线程自旋一段时间仍然得不到锁，就会把锁升级为重量级锁，线程进入休眠，等待锁释放被唤醒
- 可以配合 object.wait 和 object.notify 使用
ReentrantLock
- JDK实现的可重入、公平、可被中断的互斥锁
- 实现原理：
- 继承 AQS 类，实现了获取和释放独占资源的方法
- 加锁：CAS 修改资源值，修改不成功把该线程添加到等待队列
- 释放锁：CAS 修改资源值，如果资源值变为0则唤醒等待队列的队头线程
- 可重入：通过 校验当前获取锁的线程 和 获取锁的计数实现
- 可中断、可超时、可阻塞 ：LockSupport 工具类提供的特性（AQS使用 LockSupport 来阻塞唤醒线程）
- 公平：获取锁时先检查等待队列是否为空
- 可以配合condition来使用
Go
Mutex
不可重入、公平的互斥锁
实现原理：
加锁：CAS 修改 state 的值，修改不成功（如果在正常模式下会自旋执行30次 PAUSE 指令等待锁释放），把协程放到等待队列，触发协程调度
释放锁：CAS 修改 state 的值，把等待队列的队头协程放到可运行队列
公平：
正常模式：锁的等待者按照先进先出的顺序获取锁
- 被唤醒的协程与新请求锁的协程竞争，被唤醒的协程大概率获取不到锁。被唤醒的协程没有获取到锁会加入到等待队列的前面。如果一个等待的协程超过1ms没有获取到锁，会把锁变为饥饿模式。
饥饿模式：锁的所有权将从unlock的协程交给等待队列的中的第一个
新请求的协程不会尝试去获取锁，即使锁看起来是unlock状态，也不会去尝试自旋，直接插入到等待队列的尾部。
如果一个等待的协程获取到锁，并且满足以下任一一个条件：1）它是等待队列中的最后一个；2）它等待的时间小于1ms。它会将锁变为正常模式
读写锁
Java
ReentrantReadWriteLock
- JDK实现的可重入、公平、可被中断的读写锁
- 实现原理：
- 继承 AQS 类，实现了 获取和释放独占、共享资源的方法，资源值高16位保存读锁计数，低16位保存写锁计数
- 加锁：
- 写锁：如果存在读锁，直接把该线程添加到等待队列；否则 CAS 修改资源值，修改不成功，把该线程添加到等待队列
- 读锁：如果存在写锁，并且持有写锁的线程不是自身，把线程添加到等待队列；否则 CAS 修改资源值，修改不成功，把该线程添加到等待队列
- 释放锁：
- 写锁：CAS 修改资源值，如果写锁计数变为0，则唤醒等待队列的队头线程
- 读锁：CAS 修改资源值，如果读锁计数变为0，则唤醒等待队列的队头线程
- 可重入：通过 校验当前获取锁的线程 和 获取锁的计数实现
- 可中断、可超时、可阻塞 ：LockSupport 工具类提供的特性（AQS使用 LockSupport 来阻塞唤醒线程）
- 公平：获取锁时先检查等待队列是否为空
- 锁降级：获取写锁 -> 获取读锁 -> 释放写锁
Go
RWMutex
- 不可重入、公平的读写锁
- 实现原理：
- 加锁
- 写锁：
- 通过 mutex 获取锁
- 获取到锁以后将 readerCount 设置为负数（减去rwmutexMaxReaders），这一步是为了防止防止读操作做准备
- 如果之前的 readerCount 不为0 （有其他协程持有读锁），把之前的 readerCount 加到 readerWait 中，把协程放到写锁等待队列中，触发调度
- 读锁：原子操作给readerCount加1，如果结果为负数（表明有协程持有或正在申请写锁），把协程放到读锁等待队列中，触发调度
- 释放锁
- 写锁：原子操作给 readerCount 加 rwmutexMaxReaders，把读锁队列中的所有协程放到可运行队列中
- 读锁：原子操作给 readerCount 减 1, 如果结果为负数（表明有协程正在申请写锁），原子操作给 readerWait 减1，如果readerWait变为0则把写锁等待队列的对头协程放到可运行队列中
- Mutex 保证同时只会有一个协程申请写锁
- 通过 readerCount 和 readerWait 实现了 读写互斥
- 写锁不会被饿死：有协程申请写锁后，后续申请读锁的协程会被阻塞，申请写锁前的读锁全部被释放后，会唤醒申请写锁的协程
阻塞队列 / channel
Java
阻塞队列
- 实现原理：
- 写入：
- 使用 ReentrantLock 进行加锁
- 检查队列是否已满，如果队列已满并需要阻塞，调用 notFull.await 阻塞线程等待唤醒
- 每次成功写入一个元素，调用 notEmpty.signal 唤醒阻塞的线程
- 读取：
- 使用 ReentrantLock 进行加锁
- 检查队列是否为空，如果队列为空并需要阻塞，调用 notEmpty.await 阻塞线程等待唤醒
- 每次成功取出一个元素，调用 notFull.signal 唤醒阻塞的线程
Go
Channel
- 实现原理：
- 发送：
- 加锁
- 如果 接收队列 不为空，直接把数据发送给 接收队列 队头的协程，并把该协程放到可运行队列等待调度执行
- 如果 缓冲区 有剩余空间，把发送数据放到缓冲区
- 如果 缓冲区 没有剩余空间，把当前协程放到 发送队列 中，调用 gopark 阻塞当前协程，执行调度循环执行下一个可运行的协程
- 接收：
- 加锁
- 如果 发送队列 不为空，表明缓冲区中有数据，把 缓冲区 的队头数据拷贝到接收变量，然后把 发送队列 队头协程的发送数据写到 缓冲区 中，并且把 队头协程放到可运行队列等待调度执行
- 如果 缓冲区 有数据，把 缓冲区 的队头数据拷贝到接收变量
- 如果 缓冲区 没有数据，把当前协程放到 发送队列 中，调用 gopark 阻塞当前协程，执行调度循环执行下一个可运行的协程
CountDownLatch / WaitGroup
Java
CountDownLatch
- 实现原理
- 继承 AQS 类，实现了获取和释放共享资源的方法
- countDown：CAS 修改资源值，如果资源值变为0，唤醒等待队列中的线程
- await：检查资源值是否为0，不为0的话，加入到等待队列中等待唤醒
Go
WaitGroup
- 实现原理：
- Add：原子操作给 counter 增加 / 减少 指定的值，当 counter 为 0 时，把等待队列中的协程放到可运行队列中等待调度执行
- Done：调用 Add 传递 负数参数 实现
- Wait：检查 counter 是否 0, 如果不为0， CAS 增加 waiter 的值，把当前协程加入到等待队列，调用 gopark 阻塞当前协程，执行调度循环执行下一个可运行的协程
Condition / Cond
Java
Condition
- 实现原理
- await：
- 释放锁
- 把 当前线程 放到 条件等待队列 中，然后调用 LockSupport.park 阻塞线程
- 被 signal 唤醒后，去阻塞地获取锁，获取到锁后返回
- signal：唤醒 条件等待队列 队头线程
Go
Cond
- 实现原理
- Wait：
- 原子操作给等待计数器加1 并 解锁
- 把 当前协程 加入到 等待队列 中，调用 gopark 阻塞当前协程，执行调度循环执行下一个可运行的协程
- 被 Signal 唤醒后，阻塞地获取锁
- Signal：
- 把 等待队列 队头协程放到可运行队列中等待调度执行
线程池 / 协程池
Java
ThreadPoolExecutor
- 关键参数：核心线程数、最大线程数、任务队列（阻塞队列）、空闲存活时间
- 线程数还没有达到核心线程数时：每添加一个任务，新建一个线程
- 线程数达到核心线程数，任务队列未满时：新建的任务添加到任务队列中
- 任务队列满了，线程数未达到最大线程数时：每添加一个任务，新建一个线程
- 多余的线程空闲时间超过空闲存活时间后，线程会被销毁（默认非核心线程空闲才会被销毁，可以设置核心线程空闲也进行销毁）
- 实现原理
- 添加任务：
- 线程数还没有达到核心线程数时：每添加一个任务，新建一个线程
- 线程数达到核心线程数，任务队列未满时：新建的任务添加到任务队列中
- 任务队列满了，线程数未达到最大线程数时：每添加一个任务，新建一个线程
- 执行任务：线程循环阻塞从任务队列中获取任务，获取到任务之后就执行任务
- 销毁空闲线程：设置了核心线程空闲销毁 或 线程数大于核心线程数时，线程把空闲存活时间作为超时时间从任务队列中阻塞的获取任务，超时没获取到任务，就会结束线程循环
Go
- 关键参数：协程池大小
- 实现原理：
- 添加任务：
- 获取空闲worker
- 空闲worker队列不为空，从空闲worker队列中获取返回
- 空闲worker队列为空时，如果正在运行的worker数量没有超过协程池大小，就新创建一个worker返回
- 等待worker队列不为空的信号
- 把任务通过worker的channel传给worker
- 执行任务：
- worker协程循环阻塞从task channel获取task
- 如果获取到的task为空，就结束协程
- 执行task
- 把自身放回到空闲worker队列
- 销毁空闲协程
- 有一个协程定时从空闲worker队列中获取空闲了指定时间的worker
- 给这些worker的task channel传nil的task，让worker结束协程