散列查找与二叉查找树查找的区别
哪些公司问过
答案要点
- 散列平均O(1),冲突严重时会退化;BST平均O(log n),不平衡时最坏O(n)
- BST有序,支持范围查询、前驱后继和有序遍历;散列只适合等值查找
- 散列需要哈希函数、冲突处理和负载因子控制;BST只需key可比较
- 实践中用平衡树保证最坏O(log n),纯等值查找场景优先选哈希表
易错点
- 说哈希表查找“永远O(1)”,忽略冲突和rehash
- 把普通BST的O(log n)当成最坏复杂度
- 忽略有序性差异,在范围查询场景仍选哈希表
面试官常见追问
- 哈希冲突有哪些解决方法?
- 为什么数据库索引多用B+树而不是哈希?
- 哈希表的最坏情况会被攻击利用吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。