哈希 table - 用二叉搜索树实现
Hash table - implementing with Binary Search Tree
来自 破解编码面试，第 71 页：
Alternatively, we can implement hash table with a BST. We can then
guarantee an O(log n) lookup time, since we can keep the tree
balanced. Additionally we may use less space, since a large array no
longer needs to be allocated in the very beginning.
我知道链表、哈希表和 BST 的基础知识，但我无法理解这些行。它到底是什么意思？这个最终的数据结构会是 Trie 树吗？
该部分的完整 文本指出，最后一段是您询问的内容：
A hash table is a data structure that maps keys to values for highly efficient lookup. In a
very simple implementation of a hash table, the hash table has an underlying array and
a hash function. When you want to insert an object and its key, the hash function maps
the key to an integer, which indicates the index in the array. The object is then stored at
that index.
Typically, though, this won't quite work right. In the above implementation, the hash
value of all possible keys must be unique, or we might accidentally overwrite data. The
array would have to be extremely large—the size of all possible keys—to prevent such
"collisions."
Instead of making an extremely large array and storing objects at index hash (key), we
can make the array much smaller and store objects in a linked list at index hash (key) %
array_length.To get the object with a particular key, we must search the linked list for
this key.
Alternatively, we can implement the hash table with a binary search tree. We can then
guarantee an 0(log n) lookup time, since we can keep the tree balanced. Additionally,
we may use less space, since a large array no longer needs to be allocated in the very
beginning.
所以他们在谈论使用 BST（二叉搜索树）来处理 冲突。 使用 BST 实际上没有意义 sole 数据结构，因为正确调整哈希的全部要点是查找的顺序是 O(1)，much 比 O(log n) 来自 BST。最重要的是，使用 BST 完全 实现哈希 table 意味着它不是 实际上 哈希 table ： -)
但是，请考虑一下，当您在哈希 table 中发生冲突时，处理它们的常用方法是让每个存储桶都包含其项目的链表。在退化的情况下（所有项目散列到同一个桶），你最终只有一个链表并且 O(1) 变成 O(n).
因此，您拥有的不是每个桶的链表，而是 BST。然后，在单个存储桶有很多项目（前面提到的冲突）的情况下，您不再有 O(n) 搜索复杂性。
您使用散列函数在 O(1) 中找到桶，如果存在冲突，则在 O(log n) 中搜索 BST。在最好的情况下（每个桶一个项目），它仍然是 O(1)。最坏的情况变成 O(log n) 而不是 O(n).
最初我对这个理论唯一关心的是他们还讨论了不再需要大量分配的事实。如果它是一个共享 hash/BST 组合，你 仍然 需要分配整个散列 table 这样看起来不协调。
然而，从上下文来看("...因为大数组不再需要分配..."), 看来他们的意思是他们可以使双重数据结构的散列 table 部分更小，因为冲突的处理效率更高。换句话说，您可以使用 100 元素散列 table 而不是带有冲突链表的 1000 元素散列 table，因为冲突不会对搜索时间造成如此大的破坏，如果您使用 BST。
您在这里混淆了几个术语。
想法是用数组和 BST 以两层方式实现散列 table。如果没有冲突，人们仍然会向散列中添加值，但如果有冲突，则可以解决使用 BST 检索冲突元素的性能。
A trie 完全不同；根据您尝试存储的内容，您可能无法将其应用于哈希函数。
O(logN) 边界将是最坏的情况，如果 tree.Lets 以这种方式看待它。
我们插入 45、33、55、66、22，然后我们将 45 作为根节点，33 和 55 在第 1 层，22 和 66 在第 2 层..
所以，如果你要散列值 45，它仍然是一个 O(1) 操作......只有当你在 level2 中查找节点时，它才接近 O(logN)....这棵树可以是 RB tree/AVL 树，这样它就不会退化为链表....你失去了一些时间效率，但在 space 效率中弥补了它..
还有一个优点是您无需担心散列中的冲突 table。
http://www.cs.rit.edu/~ib/Classes/CS233_Spring08-09/Slides/Week9_Hashing.pdf
基本上，您将动态分配节点，并且没有 space 被浪费在散列 table 中未使用的桶上...比如说，您将使用静态散列 table 具有预先确定的大小 (busckets)，那么，这将导致 space 低效的实施。
来自 破解编码面试，第 71 页：
Alternatively, we can implement hash table with a BST. We can then guarantee an O(log n) lookup time, since we can keep the tree balanced. Additionally we may use less space, since a large array no longer needs to be allocated in the very beginning.
我知道链表、哈希表和 BST 的基础知识，但我无法理解这些行。它到底是什么意思？这个最终的数据结构会是 Trie 树吗？
该部分的完整 文本指出，最后一段是您询问的内容：
A hash table is a data structure that maps keys to values for highly efficient lookup. In a very simple implementation of a hash table, the hash table has an underlying array and a hash function. When you want to insert an object and its key, the hash function maps the key to an integer, which indicates the index in the array. The object is then stored at that index.
Typically, though, this won't quite work right. In the above implementation, the hash value of all possible keys must be unique, or we might accidentally overwrite data. The array would have to be extremely large—the size of all possible keys—to prevent such "collisions."
Instead of making an extremely large array and storing objects at index hash (key), we can make the array much smaller and store objects in a linked list at index hash (key) % array_length.To get the object with a particular key, we must search the linked list for this key.
Alternatively, we can implement the hash table with a binary search tree. We can then guarantee an 0(log n) lookup time, since we can keep the tree balanced. Additionally, we may use less space, since a large array no longer needs to be allocated in the very beginning.
所以他们在谈论使用 BST（二叉搜索树）来处理 冲突。 使用 BST 实际上没有意义 sole 数据结构，因为正确调整哈希的全部要点是查找的顺序是 O(1)，much 比 O(log n) 来自 BST。最重要的是，使用 BST 完全 实现哈希 table 意味着它不是 实际上 哈希 table ： -)
但是，请考虑一下，当您在哈希 table 中发生冲突时，处理它们的常用方法是让每个存储桶都包含其项目的链表。在退化的情况下（所有项目散列到同一个桶），你最终只有一个链表并且 O(1) 变成 O(n).
因此，您拥有的不是每个桶的链表，而是 BST。然后，在单个存储桶有很多项目（前面提到的冲突）的情况下，您不再有 O(n) 搜索复杂性。
您使用散列函数在 O(1) 中找到桶，如果存在冲突，则在 O(log n) 中搜索 BST。在最好的情况下（每个桶一个项目），它仍然是 O(1)。最坏的情况变成 O(log n) 而不是 O(n).
最初我对这个理论唯一关心的是他们还讨论了不再需要大量分配的事实。如果它是一个共享 hash/BST 组合，你 仍然 需要分配整个散列 table 这样看起来不协调。
然而，从上下文来看("...因为大数组不再需要分配..."), 看来他们的意思是他们可以使双重数据结构的散列 table 部分更小，因为冲突的处理效率更高。换句话说，您可以使用 100 元素散列 table 而不是带有冲突链表的 1000 元素散列 table，因为冲突不会对搜索时间造成如此大的破坏，如果您使用 BST。
您在这里混淆了几个术语。
想法是用数组和 BST 以两层方式实现散列 table。如果没有冲突，人们仍然会向散列中添加值，但如果有冲突，则可以解决使用 BST 检索冲突元素的性能。
A trie 完全不同；根据您尝试存储的内容，您可能无法将其应用于哈希函数。
O(logN) 边界将是最坏的情况，如果 tree.Lets 以这种方式看待它。 我们插入 45、33、55、66、22，然后我们将 45 作为根节点，33 和 55 在第 1 层，22 和 66 在第 2 层..
所以，如果你要散列值 45，它仍然是一个 O(1) 操作......只有当你在 level2 中查找节点时，它才接近 O(logN)....这棵树可以是 RB tree/AVL 树，这样它就不会退化为链表....你失去了一些时间效率，但在 space 效率中弥补了它..
还有一个优点是您无需担心散列中的冲突 table。 http://www.cs.rit.edu/~ib/Classes/CS233_Spring08-09/Slides/Week9_Hashing.pdf
基本上，您将动态分配节点，并且没有 space 被浪费在散列 table 中未使用的桶上...比如说，您将使用静态散列 table 具有预先确定的大小 (busckets)，那么，这将导致 space 低效的实施。