Hash Table

Introduction

Is a data structure that implements an associative array abstract data type, a structure that can map keys to values
A hash table uses a hash function to compute an index, also called a hash code

Hash function

Is a function that maps data of arbitrary size to data of a fixed size

Properties of the good hash function

Is a function that maps data of arbitrary size to data of a fixed size,
Stability: It returns the same output for the same input,
Uniformity: Uniformly distributes the data across the entire set of possible hash values,
Security: Reverse of hash shouldn’t be easy

Hash function example

Let’s write an hash function in Javascript

class HashTable {
    constructor(size) {
        this.data = new Array(size);
    }

    _generateHash(key) {
        let hashValue = 0;
        for (let i = 0; i < key.length; i++) {
            hashValue = (hashValue + key.charCodeAt(i) * i) % this.data.length
        }
        return hashValue;
    }

    set(key, value) {
        let address = this._generateHash(key);
        if (!this.data[address]) {
            this.data[address] = [];
        }
        this.data[address].push([key, value]);
        return this.data;
    }

    get(key) {
        const address = this._generateHash(key);
        const keyValue = this.data[address]
        if (keyValue) {
            for (let i = 0; i < keyValue.length; i++) {
                if (keyValue[i][0] === key) {
                    return keyValue[i][1]
                }
            }
        }
        return undefined;
    }
}

const hashIntance = new HashTable(50);
hashIntance.set('Password1', 2000);;
hashIntance.set('Password2', 500);
console.log(hashIntance._generateHash('Password1'));
console.log(hashIntance._generateHash('Password2'));
// 29
// 37