I\'ve been learning about using a hashtable to efficiently check for items in a

Question

I've been learning about using a hashtable to efficiently check for items in a list without looping through the whole thing, but there's one thing that I don't get:

Why hashed keys?

It seems like:

var wordList = {
   'aa'    : ['aa'],
   'aah'   : ['aah'],
   'ahhed' : ['aahed']
};
Would work just as well as:

var wordList = {
   '/* hashed value of aa*/'    : ['aa'],
   '/* hashed value of aah*/'   : ['aah'],
   '/* hashed value of aahed*/' : ['aahed']
};
What's the performance difference between looking up a hashed key and a simple name key?

Explanation / Answer

Because you still need a way to search the associative array. The hash table is your search mechanism; it gives you O(1) performance for any given key search.

What is your underlying search mechanism, if it's not a hash table? A Binary Search Tree? That's good for very large tables, but it's not O(1); it's O(log n). If you don't have a search mechanism at all (i.e. you're searching the entire array from top to bottom to find your key), your performance is O(n).

If your keys are already ordered, you can use a Binary Search without maintaining a tree; that is also O(log n) performance.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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