在处理哈希冲突时,为什么要在BST上使用链表？

链接列表需要O(n)进行搜索,而BST采用O(log n).那么为什么要使用链表来处理冲突呢？我能想到的唯一原因是因为插入链表是O(1),而插入BST是O(log n).

如果散列函数是好的并且散列表加载因子不是太高那么在任何一个桶中都不应该有很多冲突.链表是一种非常简单的数据结构,足够好,碰撞次数少.速度快,占用空间小.请记住,大多数存储桶中都包含0或1个值.

此外,BST会强制要求物品可以订购.哈希表的一个不错的特性是键不需要具有可比性.