Hash Tables

As far as data structures go, hash tables are the most important one to understand for web development. Hashing is how encryption works. A hash table has a bunch of buckets. Each bucket is where the hash table stores key value pairs.

Consider:

var allBuckets = [ [],[],[],[] ];
var moreBuckets = [ [],[],[],[],[],[],[],[] ];
// Inserting a key 'x' with value 10
// 1) Use hash function to get bucket index
// 2) Push key-value pair into bucket (what to do for existing //keys)?
// 3) If # of key-value pairs > max length
// - Get more buckets! (usually double the # of buckets)
// - Redistribute key-value pairs from old buckets to new buckets
var bucketIndex = hashFn('x') % allBuckets.length //=> 0, 1, 2, or 3
allBuckets[bucketIndex].push(['x', 10]);
var bucketIndex = hashFn('g') % allBuckets.length //=> 1
allBuckets[bucketIndex].push(['x', 10]);
function hashFn(key){ 
var number = ...;
return number
}
// Steps to find item:
// 1) Use hash function to get bucket index
// 2) Iterate through bucket, search for key 'x'
// 3) if found
// return value for key 'x'
// else
// return null

The goal is to maintain a small bucket size. If you try to insert a tuple (an array with two values, in this case a key-value pair) into a full bucket, your code should add more buckets and rehash all the items, then distribute them across the new buckets.

Like what you read? Give Brian Small a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.