JavaScript Hash Table
Hash table is one of the most important data structures in computing. A hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. In JavaScript we don’t have any built-in hash table.
While many programming languages support associative arrays (hash tables or arrays with named indexes, JavaScript does not. In JavaScript arrays use numbered indexes.
Doesn't JavaScript already do this?
If you use a named index, JavaScript will redefine the array to a standard object.
Hash table is like a bucket -= Represented as an empty array in this case = -
var allBuckets = [[], [], [], []]
In order to insert a value inside our buckets,
//insert a key “x” with the value 10
1. Use has function to get bucket index
3. Push key-value pair into bucket (what about existing keys?)
3. If # of key-value pairs > 12 -Get more buckets! (Usually double the # of buckets) -Redistrubute key-value pairs from old buckets to new buckets.
//hasFn(key) % allBuckets.length // => 0, 1, 2, or 3
var bucketIndex = hashFn(‘x’) % allBuckets.length //=> 1
allbuckets[bucketIndex].push([‘x’, 10])
var bucketIndex = hashFn(‘g’) % allBuckets.length //=> 1
allbuckets[bucketIndex].push([‘g’, 10])
Reading a key ‘x’
1. Use hash function to get bucket index
2. Iterate through, searching for key ‘x’
3. If found, return
