千万级插槽快速判断是否有值的数据结构
哪些公司问过
答案要点
- 编号连续时用位图,每个插槽1 bit
- 一千万bit约1.25MB,查询和修改都是O(1)
- 通过下标除8定位字节、模8定位位,用位运算读写
- key不连续或很大时可用布隆过滤器,存在误判且不支持删除
- 并发修改需原子操作或加锁
易错点
- 把一千万bit算成125MB,单位换算错误
- 用哈希集合存海量整数,内存浪费
- 以为布隆过滤器判断存在就一定存在
面试官常见追问
- 如果还要快速找到第一个空插槽呢?
- Redis里怎么实现?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。