How Hash Tables Work

By creating an array and pushing the value into it, it allows for multiple items to be placed in the index spot.

There is a methodology called “linear probing” which means that, instead of sharing, the key will search for the next open index and store itself in that.

Probing aside, let’s say we added another object to our array and it looked like this:obj = {"apple":"pie", "peach":"cobbler"}And our hashing method hashes both “apple” and “peach” and produces the same number, 3.

Our hash would look like this, unmasked:[undefined, undefined, undefined, [["apple", "pie"], ["peach","cobbler"]], undefined]SearchingIf we were to search the object like so — obj[“peach”] the hash class would break down “peach” into a number which it would use as an index.

It then search for content at that index.

If there is an array, it iterates through that array checking the first item of each subarray to see whether or not it matches the entered key, in this case “peach”.

If there is a match, it would return the second item in that array.

A method to do just that is below:get(key){ let idx = this.

_hash(key); let keyMapIdx = this.

keyMap[idx] if(!keyMapIdx){ return undefined; } else if(keyMapIdx){ for(let i = 0; i < keyMapIdx.

length; i++){ if(keyMapIdx[i][0] === key){ return keyMapIdx[i][1] } } } return undefined }And violá we have our searching method for our hash.

A great, efficient way of storing all our data we need quick access to.


. More details

Leave a Reply