如何实现线程安全的开链哈希表
哪些公司问过
答案要点
- 结构是桶数组,每个桶用链表存放冲突元素
- 分段锁:按桶号映射到一组锁之一,不同段可并行
- 读多写少时用读写锁提升查找并发
- 扩容需按固定顺序获取全部锁,或采用新旧表并存的渐进式迁移
- 可参考 ConcurrentHashMap:空桶 CAS、非空桶锁链表头
易错点
- 只给插入加锁,查找不加锁却又立即释放删除的节点
- 扩容时只锁部分段,导致迁移过程中数据丢失
- 多把锁加锁顺序不一致,扩容时出现死锁
面试官常见追问
- 锁的数量怎么选?
- 查找时可以不加锁吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 线程同步与互斥的实现方式218 场
- 线程安全的保障方法121 场
- 自旋锁与互斥锁的区别和使用场景94 场
- 无锁队列的实现与 CAS64 场
- 生产者-消费者模型47 场
- 信号量的作用与它和锁的区别45 场
- 阻塞队列与有锁队列的实现22 场
- 多线程为什么需要加锁13 场
- mutex、lock_guard 与 unique_lock 的区别11 场
- 两个线程交替打印奇偶数10 场