Hashtables
Hashing: Basically, a hash code turns a key into an integer. It’s very important that hash codes are deterministic: their output is determined only by their input. Hash codes should never have randomness to them. The same key should always produce the same hash code.
Challenge:
Implementation: Hash Tables Specifications Read all of these instructions carefully. Name things exactly as described. Do all your work in a your data-structures-and-algorithms public repository. Create a new branch in your repo named as noted below. Follow the language-specific instructions for the challenge type listed below. Update the “Table of Contents” - in the README at the root of the repository - with a link to this challenge’s README file. Challenge Setup & Execution Branch Name: hashtable
Challenge Type: New Implementation
Features Implement a Hashtable Class with the following methods:
add Arguments: key, value Returns: nothing This method should hash the key, and add the key and value pair to the table, handling collisions as needed. get Arguments: key Returns: Value associated with that key in the table contains Arguments: key Returns: Boolean, indicating if the key exists in the table already. hash Arguments: key Returns: Index in the collection for that key Structure and Testing Utilize the Single-responsibility principle: any methods you write should be clean, reusable, abstract component parts to the whole challenge. You will be given feedback and marked down if you attempt to define a large, complex algorithm in one function definition.
Write tests to prove the following functionality:
Adding a key/value to your hashtable results in the value being in the data structure Retrieving based on a key returns the value stored Successfully returns null for a key that does not exist in the hashtable Successfully handle a collision within the hashtable Successfully retrieve a value from a bucket within the hashtable that has a collision Successfully hash a key to an in-range value Ensure your tests are passing before you submit your solution.
Approach & Efficiency
Arrays actually have fast access. If we know the index of the information we want we can access that information in O(1) time. The reason why searching for a piece of data in a collection is O(N) isn’t because the array is slow, it’s just that we have to look through all N things in the collection.
Hash maps take advantage of an array’s O(1) read access. Instead of adding elements to an array from beginning to end, a hash map uses a “hash function” to place each item at a precise index location, based off it’s key.
Basically, the hash function takes a key and returns an integer. We use the integer to determine where the key/value pair should be placed in the array. The hash code is calculated in constant time and writing to an array at one index is O(1) so the hash map has O(1) access.
The hash code is used again to read something from the hash map. Take the key, run it through the hash code to get a number, use that number to index the array. Calculating the hash code and reading an array at that index is all constant time to the hash map has O(1) read access!
Code Link:
API
- hash: Arguments: key, value Returns: nothing This method should hash the key, and add the key and value pair to the table, handling collisions as needed.
- get: Arguments: key Returns: Value associated with that key in the table
- contains: Arguments: key Returns: Boolean, indicating if the key exists in the table already.
- add: Arguments: key Returns: Index in the collection for that key