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