Ada*_*ner 2 hashtable hashmap data-structures
链接列表需要O(n)进行搜索,而BST采用O(log n).那么为什么要使用链表来处理冲突呢？我能想到的唯一原因是因为插入链表是O(1),而插入BST是O(log n).
哈希表的理由是应该有很少的项目哈希到同一哈希槽。对于这些小数字，链表实际上应该比 BST（更好的常数因子）更快，并且在任何情况下都更简单、更可靠。BST 最坏的情况在任何情况下都与链表相同，除非您想真正超越顶部并使用平衡树。
如果散列函数是好的并且散列表加载因子不是太高那么在任何一个桶中都不应该有很多冲突.链表是一种非常简单的数据结构,足够好,碰撞次数少.速度快,占用空间小.请记住,大多数存储桶中都包含0或1个值.
此外,BST会强制要求物品可以订购.哈希表的一个不错的特性是键不需要具有可比性.