1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Reboot
    Oct 16, 2017 at 5:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – Evil
    Oct 16, 2017 at 5:23
  • $\begingroup$ I have included the changes in my question, to make to clear to understand. Thanks! $\endgroup$
    – Reboot
    Oct 16, 2017 at 5:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – Pseudonym
    Oct 16, 2017 at 5:49
  • $\begingroup$ 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. $\endgroup$
    – Evil
    Oct 16, 2017 at 6:04

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.