CODEWITHSUNDEEP
performancedata-structureshashmaphashtableavl-tree
Matt
Matt

Reputation: 11327

When is an AVL tree better than a hash table?

More specifically, are there any operations that can be performed more efficiently if using an AVL tree rather than a hash table?

Upvotes: 4

Views: 11249

Answers (3)

progga
progga

Reputation: 1

Also wanted to keep in mind two more points:

  • AVL three/Red black three require rebalance after putting new element, so it blocks whole table for insert, which makes this not very usable for multithreaded applications
  • Hash tables works fine if they have enough free space, like 30%, otherwise you need to create bigger hashttable and rehash, move data. So basically if you have hash table that grows more and more this is not effective because of too many rebalancing. But you could work more effectively with key-lock and you didn’t need to lock all datastructure like three

Upvotes: 0

Stefan
Stefan

Reputation: 28531

An obvious difference, of course, is that with AVL trees (and other balanced trees), you can have persistency: you can insert/remove an element from the tree in O(log N) space-and-time and end up with not just the new tree, but also get to keep the old tree.

With a hash-table, you generally cannot do that in less than O(N) time-and-space.

Another important difference is the operations needed on the keys: AVL tress need a <= comparison between keys, whereas hash-tables need an = comparison as well as a hash function.

Upvotes: -1

user448810
user448810

Reputation: 17876

I generally prefer AVL trees to hash tables. I know that the expected-time O(1) complexity of hash tables beats the guaranteed-time O(log n) complexity of AVL trees, but in practice constant factors make the two data structures generally competitive, and there are no niggling worries about some unexpected data that evokes bad behavior. Also, I often find that sometime during the maintenance life of a program, in a situation not foreseen when the initial choice of a hash table seemed right, that I need the data in sorted order, so I end up rewriting the program to use an AVL tree instead of a hash table; do that enough times, and you learn that you may as well just start with AVL trees.

If your keys are strings, ternary search tries offer a reasonable alternative to AVL trees or hash tables.

Upvotes: 6

Related Questions