AVL Tree or HashTable for storing relatively big data?

Question

I have been looking to implement a data structure for my project. I came across AVL tree and Hash Table. As I am a beginner so I'm in dilemma what data structure I use for large data. The main operation will be mostly searching through the database efficiently.

AVL Tree seems to be very good option to store around 120000 entries(object) of data and keep the search time to O(logn), however I stumble upon a perfect hashing concept. It states it expected the search time is constant O(1), if collision occur then it would use secondary hash function that will still have access time of O(1) if I'm not mistaken.

perfect hashing function according to Introduction to Algorithm by Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stien is :- h(k) = ((3k + 42) mod 101) mod size(number of enteries)

Data that I'm storing is from text file, converting each line into an object. All those objects will be inserted all at once in data structure. After that main operation I have to use is search through the data structure.

Bus -> street1 -street2- street3- destination, this line would be converted into an object. So search would be like return the route bus1 took to reach destination5.

Any suggestions which one would be more reliable and efficient for time and space complexity?

Answer 1

For search dominant operation, supported insert, delete, find only there are huge benefits in using the Hash Table.

• the memory footprint is low, only colliding entries require pointer, one per entry while AVL requires two pointers per entry.
• access time is expected $\mathcal O(1)$, say in the worst case 5, which gives one hash calculation and 5 equality tests while AVL has 25 full comparissons for 120000 entries in the worst case.
• rehashing could be avoided with maximal capacity known in advance, otherwise it would be rare operation.

What would opt for AVL?

• traversal queries, looking for ranges etc.
• access to sorted data.
• inexact queries, looking for nearest neighbour (at the cost of additional pointers).

By the way the perfect hash table is commonly refered to as having no collisions, which requires static setting, rehashing. What you refer to is probably dynamic perfect hashing, a two-tier scheme with guaranteed deterministic constant lookup.

If you have all data (or substantial amount) it is beneficial to sort data and create balanced tree to avoid inserting nodes one by one. (Something like DSW algorithm would help).
In that case the hash table may be constructed without collisions at all for initial data, leaving space for future elements and work really fast.

For the search part, none of the structures would help. If I understood correctly, your data is a graph, so both presented structures will help with indexing only and the Hash Table is the winner.

Sidenote:
To store compactly textual data something like Trie or Directed Acyclic Word Graph would be better. The edited part about search would require a graph, path finding algorithm and auxiliary indexing data structure, in your case probably Hash Table or DAWG used as map.