2
$\begingroup$

I need an efficient data structure for maintaining a set of values. Here, $n_1$ is the number of insertions per unit time; $n_2$ is the number of deletions per unit time; $k$ is the number of searches per unit time.

I have 4 possible use cases:

  1. $k \gg n_1,n_2$ with limited memory
  2. $n_1 \gg k,n_2$ with limited memory
  3. $k, n_1, n_2$ are comparable with limited memory
  4. $k, n_1, n_2$ are comparable with unlimited memory

I have decided to use a doubly linked list for the second case and a direct address table for the fourth case.

My question is about the first and the third cases. Both Hash Table and Tree (AVL or Red-Black) look promising. Should I choose the Hash Table with an amortised constant time or the Tree with a $\log n$ worst case time?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ Your call... the decision might depend on other considerations, like programming language available, the structure is already being used in other parts of the program, development time, developer familiarity, ... $\endgroup$ – vonbrand Mar 15 '14 at 18:03
  • $\begingroup$ @vonbrand Does it mean that both are equally good in both the cases setting aside the external parameters you mentioned above? $\endgroup$ – Priyatham Mar 15 '14 at 18:10
  • 1
    $\begingroup$ Program both and see which works faster. $\endgroup$ – Yuval Filmus Mar 15 '14 at 22:32
  • $\begingroup$ The first Case does not relate the numbers of Insertions and Deletions. If the former dominate, your internal Data structures will grow steadily until the available Memory is exhausted. Close to That Time You will have to Delete entries by Force and update your structures accordingly which i think Will be easier and more flexible using Hash tables (which in theory are favored by the relative frequencies of searches anyway; however, in a concrete implementation the actual Parameter values and the complexity of the hashing function affect the results) $\endgroup$ – collapsar Mar 16 '14 at 11:10
  • $\begingroup$ In Case 3 the best Choice depends on whether your Data structure will fit into the available Memory given the expected number of items it will contain. If it doesn't fit, the Data structure Must be enhanced with some sort of paging scheme which i suspect be easiest with Hash tables. $\endgroup$ – collapsar Mar 16 '14 at 11:19
1
$\begingroup$

Depending on how limited the memory is, the best choice for 1 could be a sorted array: Binary search is fast, insertions and deletions are rare and memory overhead is negligible.

For number 2 a (unsorted) singly linked list is better than a doubly linked one, since we (presumably) don't perform any operations that benefit from the backlinks and thus can save the memory (and maintenance time) required for them.

For number 3, unless the hash function and data don't play nicely with each other, the hash table will likely be faster than a tree. If the load factor does not get too low, it will also be more space efficient, since a binary tree with $n$ keys needs $\sim 2n$ pointers.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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