Data structure – hash table – implemented using binary search tree
From cracking the code interview, page 71:
I know the basics of linked list, hash table and BST, but I can't understand these lines What does it mean? Will the final data structure be trie?
Solution
The last paragraph is the paragraph you asked:
So they talk about using BST (binary search tree) to deal with conflicts Using BST as the only data structure actually makes no sense, because the whole point of the correctly adjusted hash is that the lookup is about O (1), which is better than o (log n) A BST. most importantly, using BST to fully implement a hash table means that it is not actually a hash table: -)
However, please note that when you have conflicts in the hash table, the common way to deal with them is to have each bucket contain a linked list of its items In the case of degradation (all items are hashed to the same bucket), there is only one linked list, and O (1) becomes o (n)
Therefore, you have a BST instead of a linked list of each bucket Then, in the case of a single bucket with multiple items (conflicts mentioned earlier), you no longer have o (n) search complexity
If there is a conflict, use the hash function to find the bucket in O (1), and then search for BST in O (log n). In the best case (one item per barrel), it is still o (1) The worst case then becomes o (log n) instead of O (n)
The only thing I was initially concerned about this theory was that they also discussed the fact that large allocations were no longer needed If it is a shared hash / BST combination, you still need to allocate the entire hash to make it look uncoordinated
However, from the context ("... Because there is no need to allocate large arrays..."), they mean that they can make the hash table part of a dual data structure because conflict processing is more efficient In other words, if BST is used, a 100 element hash table can be used instead of a 1000 element hash table with a linked list, because the conflict will not cause much damage to the search time