W2D5 - Hash Maps
Hashes
This Friday we created our own hash map data structure. I’ve always heard that hashes are amazing because they can set and access their elements in O(1) time. I finally learned how that works. Actually, sometimes when you insert an element into a hash, the time taken will be proportional to the number of elements in the hash. As your number of elements increases, this case occurs less and less often. The occurrence is rare enough that the average (amortized) time does not depend on the number of elements n.
Hash Functions
A hash uses a hash function in order to get a uniform distribution of elements into the “buckets” where they are stored. The hash function must have several properties. It should output data that is
deterministic
uniformly distributed
unpredictable
highly sensitive (opposite of a continuous function)
This basically means that if the input is 2 I will get the exact same crazy thing like “d81e3f” every time (deterministic yet unpredictable), and if the input is 3 (very close to 2) I will get something like “947a2b” (uniformly distributed and highly sensitive). Sometimes you also want a hash function to have other properties too. You may want it to be fast, for example. You may even want it to be slow for use in cryptography.
The Results
My pair and I played with a few different combinations of operations until we successfully built a hash function that satisfied most of these properties. Our function did fail to be highly sensitive in one way (swapping two elements of an array and hashing yields the negative of the original hashed array). Besides this, it behaves very well. Using a linked list and a few other structures, we built our hash map.
