哈希表-使用二进制搜索树实现

从破解编码面试,第71页:

或者,我们可以使用BST实现哈希表.然后我们可以保证O(log n)查找时间,因为我们可以保持树平衡.另外,我们可以使用更少的空间,因为不需要在一开始就分配大型阵列.

我知道链表,哈希表和BST的基础知识,但我无法理解这些行.它究竟意味着什么？这个最终的数据结构会是Trie吗？

该全是部分国家的文字,随着最后一段是你问了一句:

哈希表是一种数据结构,它将键映射到值以进行高效查找.在散列表的非常简单的实现中,散列表具有底层数组和散列函数.如果要插入对象及其键,哈希函数会将键映射到整数,该整数表示数组中的索引.然后将该对象存储在该索引处.

但通常情况下,这不太适用.在上面的实现中,所有可能键的哈希值必须是唯一的,否则我们可能会意外地覆盖数据.数组必须非常大 - 所有可能键的大小 - 以防止这种"冲突".

我们不是制作一个非常大的数组并将对象存储在索引散列(键)中,而是可以使数组更小,并将对象存储在索引散列(键)%array_length的链表中.为了获得具有特定键的对象,我们必须在链表中搜索此密钥.

或者,我们可以使用二叉搜索树实现哈希表.然后我们可以保证0(log n)查找时间,因为我们可以保持树平衡.另外,我们可以使用更少的空间,因为不需要在一开始就分配大型阵列.

所以他们谈论使用BST(二叉搜索树)来处理冲突.使用BST作为唯一的数据结构实际上没有意义,因为正确调整的散列的整个点是查找的顺序O(1),比BST的要好得多O(log n).最重要的是,使用BST 完全实现哈希表意味着它实际上不是哈希表:-)

但是,请注意,当您在哈希表中发生冲突时,处理它们的常用方法是让每个存储桶包含其项目的链接列表.在简并的情况下(所有项目都散列到同一个桶),你最终只得到一个链表并且O(1)转入O(n).

因此,您有一个BST,而不是每个桶的链表.然后O(n),在单个存储桶具有多个项目(前面提到的冲突)的情况下,您不再具有搜索复杂性.

您可以使用哈希函数查找存储桶,O(1)然后在O(log n)存在冲突的情况下搜索BST .在最好的情况下(每桶一个项目),它仍然是O(1).最坏的情况然后变得O(log n)而不是O(n).

我最初关心这个理论的唯一问题是,他们还讨论了不再需要大量分配的事实.如果它是共享散列/ BST组合,您仍然需要分配整个散列表,以使其看起来不协调.

但是,从上下文("......因为不再需要分配大型数组......")看来,它们意味着它们可以使哈希表成为双数据结构的一部分,因为冲突更有效处理.换句话说,如果使用BST,则可以使用100个元素的哈希表,而不是具有链接列表的1000个元素哈希表,因为冲突不会对搜索时间造成太大损害.