Can you create a hash table made of binary trees?

Question

For instance, if you have a hash table with the array of buckets 26 nodes long, one for each letter of the alphabet. You use that to keep track of names. So when a name "Jed" is added to the J linked list that already has "Jack" and "John", rather than just adding Jed to the end of the linked list, you structure that J bucket as a binary tree and sort the new addition into it, so when you go to search for Jed in the future you can just go straight to the J bucket and then a faster binary search (vs if it was a list of unsorted items).

Answer 1

You can, because the structure used to store the contents of any bucket can be almost anything (list, vector, tree, etc.). However, the buckets are usually pretty lean (1 or 2 objects), and the overhead of creating and maintaining the tree would be more than you'd gain. (You won't see any improvement until there are at least 3 items in the bucket, and even then it'll only be 1/3 of the time if the tree is balanced.) Once you start getting buckets large enough that you might see a performance gain, your hash table should probably be expanded and rehashed. Or you need a better hash algorithm to have fewer collisions.

Answer 2

Not only can you implement your fixed-size case-insensitive hash table using binary tree buckets ... you can implement it with 26-ary trees (or really another one of your top-level hash tables).

This gives you a Trie.

But really any container will work for the buckets of a real hash table, since they're not supposed to contain many collisions.

If, as in your example, the top-level container is not a real hash table (or you expect your hash to perform as badly as just taking the first character) ... you still have the whole universe of data structures to choose from. You want an array of 26 splay trees, or skip lists, or whatever? Knock yourself out.