Hash Table
All about Hash Tables
A hash table is a data structure that converts a value into a "hash" key and stores it into an array, allowing for fast access to values based on keys.
One of the good features of a Hash Table is that various methods runs in amortized constant time (e.g. search). Other methods like insertion or deletion runs in constant time.
Although this data structure is not recommended nowadays since there are better solutions (hashmap) or already built-in in programming languges, it is worth learning how it works unders the hood.
Hashing
The hashing method can accept a string, integer, or float number. It will return a integer that will represent the index of the array to be stored.
function hashCode(string) {
const R = 31 // prime
let hash = 0
for (let i=0; i < string.length; i++) {
hash = (R * hash + (+string[i])) % M
}
return Math.floor(hash)
}Collision Resolution
Given that the number of keys to store (e.g. individual ATM transactions over the entire state of Maryland for a large bank organization) is enormous and the available space to store them in computer memory is much smaller, collisions are inevitable, even with an excellent hash function.
Then it is important to develop collision resolution methods, whose job is to determine how an insertion of a key that collides with an existing key is resolved. There are 4 ways to resolve them.
Separate Chaining
In the image, we're using a linked list because in that way we can store collided keys.
Note that it is not necessary that we employ a linked list for implementing the collision "chains". We could just as well use an AVL Tree, a Red-Black or B-Tree, or a SkipList!
The benefit of using a linked list for our collision chains is that we can insert very fast (by adding to the front or by adding to the back with a tail pointer).
The drawback is that we have linear time for search, but with relatively large and a good hash function, we are hoping that the collision chains will, on average, have length , which is still linear time but offers a favorable constant of .
class SeparateChainingHashTable implements HashTable {
private table: KVPairList[]; // array to store hashed keys
private size: number;
private primeGenerator: PrimeGenerator;
private hash(key: string): number {
// mask the first bit to filter away negative values.
return (key.hashCode() & 0x7fffffff) % table.length;
}
constructor () {
this.count = 0;
this.primeGenerator = new PrimeGenerator();
// intialize internal storage
this.table = Array(primeGenerator.getCurrPrime()).fill(new KVPairList())
}
public put(key: string, value: string): Probes {
// add the key value pair to the linked list
this.table[this.hash(key)].addBack(key, value);
size++;
// The `Probes` object tracks the number of accesses to the `table` array.
return new Probes(value, 1);
}
public get(key: string): Probes {
return this.table[this.hash(key)].getValue(key);
}
public remove(key: string): Probes {
// remove the key value pair from the list
let probe = this.table[this.hash(key)].removeByKey(key);
// if the value is not null, then the key is found
if (probe.getValue() != null) {
size--;
}
return probe;
}
public containsKey(key: string): boolean {
return this.table[this.hash(key)].containsKey(key);
}
public containsValue(value: string): boolean {
for (let i = 0; i < this.table.length; i++) {
if (this.table[i].containsValue(value)) {
return true;
}
}
return false;
}
public size(): number{
return this.size;
}
public capacity(): number{
return table.length;
}
// Enlarges this hash table. At the very minimum,
// this method should increase the capacity of the hash table
// and ensure that the new size is prime.
public enlarge(): void {
let copy: KVPair[];
// Copy all the elements in the table to the list
for (let i = 0; i < this.table.length; i++) {
for (let pair of this.table[i]) {
copy.add(pair);
}
}
// create a new table with the next prime
this.table = new KVPairList[primeGenerator.getNextPrime()];
this.size = 0;
// initialize the new table
for (int i = 0; i < this.table.length; i++) {
this.table = Array(this.table.length).fill(new KVPairList())
}
// put all the elements in the list to the new table
for (let pair of copy) {
this.put(pair.getKey(), pair.getValue());
}
}
// Shrinks this hash table. At the very minimum,
// this method should decrease the size of the hash table
// and ensure that the new size is prime.
public shrink(): void {
let copy: KVPair[];
// Copy all the elements
for (let i = 0; i < this.table.length; i++) {
for (let pair of this.table[i]) {
copy.add(pair);
}
}
// create a new table with the previous prime
this.table = new Array(primeGenerator.getNextPrime())
this.size = 0;
// initialize at each index of the new table
for (let i = 0; i < this.table.length; i++) {
this.table[i] = new KVPairList();
}
// put all the elements in the copy list to the new table
for (let pair of copy) {
this.put(pair.getKey(), pair.getValue());
}
}
}