krpra krpra - 1 year ago 110
C Question

Hashing With AVL Trees

I was working on a search program in C. I used hashing data structure. I just stored a word once and from that word I pointed to the strings in which that word exists. So whenever a user give a word, all the strings containing that word will be given.

But instead of using a linked list, I used an AVL Tree in hashing. In short the next node in the key is pointing to root of an AVL tree. This can reduce the time complexity from O(n) to O(log n).

Suppose one node has thousands of strings connected together. Is it good to use hashing with AVL tree. (I also tried Tries Data structure for this.)

Is there is any better algorithm for this?

Answer Source

Suppose one node has thousands of strings connected together. Is it good to use hashing with AVL tree.

No. At that point, you're hardly even using a hash table anymore -- if you're happy with O(log n) performance, use the tree directly, without the hash table at the top.

If you have "thousands of strings" under a single hash bucket, your hash table is way too small -- ideally, most buckets should have at most one object in them. Use a larger hash table to get the O(1) insert/lookup performance that hash tables can provide.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download