# AVL Tree or HashTable for storing relatively big data?

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?

• Data grow with time means if I add more objects later. Bus -> street1 -street2- street3- destination, so search would be like return the route bus1 took to reach destination5. – Reboot Oct 16 '17 at 5:16
• It changes your question, quite a bit. Maybe you are taking the wrong approach, I would encourage you to edit the question and include exact task, because it seems that you would benefit from using graph (it seems that there are some traversals and path finding involved) and second structure, a hash table pointing to streets / stops etc. – Evil Oct 16 '17 at 5:23
• I have included the changes in my question, to make to clear to understand. Thanks! – Reboot Oct 16 '17 at 5:30
• I agree with @Evil here. You have two interesting data structure problems: representing a graph, and efficiently managing labels on the vertices and/or edges. – Pseudonym Oct 16 '17 at 5:49
• I encourage you to post separate question with exact task you have, constraints and expected sizes of data. Also if you could, please delete obsolete comments. – Evil Oct 16 '17 at 6:04

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.