When implementing a dictionary (\'I want to look up customer data by their custo

Question

When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL library implements dictionaries (they call them maps) using (balanced) binary search trees, and the .NET framework uses hash tables under the hood.

What are the advantages and disadvantages of these data structures? Is there some other option that is reasonable in certain situations?

Note that I'm not particularly interested in cases where the keys have a strong underlying structure, say, they are all integers between 1 and n or something.

Explanation / Answer

A whole treatise could be written on this topic; I'm just going to cover some salient points, and I'll keep the discussion of other data structures to a minimum (there are many variants indeed). Throughout this answer, n is the number of keys in the dictionary.

The short answer is that hash tables are faster in most cases, but can be very bad at their worst. Search trees have many advantages, including tame worst-case behavior, but are somewhat slower in typical cases.

Balanced binary search trees have a fairly uniform complexity: each element takes one node in the tree (typically 4 words of memory), and the basic operations (lookup, insertion, deletion) take O(lg(n)) time (guaranteed asymptotic upper bound). More precisely, an access in the tree takes about log2(n) comparisons.

Hash tables are a bit more variable. They require an array of around 2n pointers. Access to one element depends on the quality of the hash function. The purpose of a hash function is to disperse the elements. A hash table

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.