Hashing

A hash table is a data structure that allows for someone to map keys to values for high efficiency to search for these values. There are multiple implementations of hash tables. In this post we will talk about 2 different implementations both implementations will you an array.

The first thing that needs to be done when creating a hash table is figuring out how to create the key. There are multiple ways to create a key. This implementation will be changing strings into indexes.

function createKey(word) {
    value = 0
    for(letter of word) {
        value += word.charCodeAt(0)
    }
    return value
}

This function will change the word into a key that can then be correlated with a place in an array.

If we know the size of the data set that we want to store in a hash table then we can create an array that is about 1.3 times the size of the data. This is a good rule of thumb that is used so that collisions are minimized when creating a hash table.

function createTable(arr) {
    let table = [...Array(Math.floor(arr.length * 1.3))].map(() => false)
    for(word of arr) {
        key = createKey(word)
        while(table[key % Math.floor(arr.length * 1.3)] != word) {
            if(!table[key % Math.floor(arr.length * 1.3)]) {
                table[key % Math.floor(arr.length * 1.3)] = word
            } else {
                key += 1
            }
        }
    }
    return table
}

This function creates a hash table that places the value into the place of the array that is not filled that is closest to the key. This will allow for quick searching. If you wanted to find out if a value is within the array then this would be a quick way to look up if the value is there.

The second way would be to limit the size of the array but then create a linked list at every index to store the values. this would take care of the collisions and allow for fast lookups.

function createTable(arr) {
    let table = [...Array(10].map(() => false)
    for(word of arr) {
        key = createKey(word) % 10
        spot = table[key]
        if(!spot) {
            table[key] = Node.new()
            table[key].data = word
        } else {
            while(spot.next){
                 spot = spot.next
            }
            spot.next = Node.new()
            spot.next.data = word
        }
    }
    return table
}

Those this may be slower it allows for less space to be taken up because you don't have to create extra space in the array to store nothing.