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?
5
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, by computing an index into the bucket containing your item.
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.
14
Well, if you need to find something in your associative array, you need to iterate through each of the keys, and find equality. This means that in the worst case, you’ll need to iterate through your whole collection to find the good key.
Accessing an array with an index (myArray[0] for example) is instant; it doesn’t require any searching, because the runtime of the languages knows exactly where to find this value.
When using a hashtable, you compute the hash code of a given key to find the associated value. The hashcode is an index in the underlying array of the hashtable. This means that finding a key in a hashtable is as fast as accessing an array by index.
An hashtable’s code is a bit more complex, but this is the general idea.
2