# What is a suitable data structure in this scenario?

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?

• 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, ... Mar 15, 2014 at 18:03
• @vonbrand Does it mean that both are equally good in both the cases setting aside the external parameters you mentioned above? Mar 15, 2014 at 18:10
• Program both and see which works faster. Mar 15, 2014 at 22:32
• 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) Mar 16, 2014 at 11:10
• 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. Mar 16, 2014 at 11:19

## 1 Answer

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.