// In this example, the chaining method, also known as close dressing,
// was used to deal with the collision.
class HashTable {
constructor() {
this.table = new Array(127) // there are 127 ASCII sybmols
this.size = 0
}
_hash (key) {
let hash = 0
key = key.toString()
for (let i = 0; i < key.length; i++) {
hash += key[i].charCodeAt()
}
return hash % this.table.length
}
loadFactor () {
return (this.size / this.table.length).toFixed(3)
}
display () {
this.table.forEach((value, index) => {
console.log(index, ':', (value.length > 1) ? value : value[0])
})
}
insert (key, value) {
const index = this._hash(key)
if (this.table[index]) {
for (let i = 0; i < this.table[index].length; i++) {
if (this.table[index][i][0] === key) {
this.table[index][i][1] = value
return
}
}
this.table[index].push([key, value])
} else {
this.table[index] = []
this.table[index].push([key, value])
}
this.size++
}
retrieve (key) {
const entry = this._hash(key)
if (this.table[entry]) {
for (let i = 0; i < this.table[entry].length; i++) {
if (this.table[entry][i][0] === key) {
return this.table[entry][i][1]
}
}
}
return undefined
}
delete (key) {
const index = this._hash(key)
if(this.table[index] && this.table[index].length) {
for (let i = 0; i < this.table[index].length; i++) {
if (this.table[index][i][0] === key) {
this.table[index].splice(i, 1)
this.size--
return true
}
}
} else {
return false
}
}
}
const ht = new HashTable()
ht.insert('Ford', 250)
ht.insert('Audi', 320)
ht.insert('Bugatti', 457)
ht.insert('U', 100) // will collide with Bugatti
ht.display()
// [Log]:
// 6 : [ 'Audi', 320 ]
// 14 : [ 'Ford', 250 ]
// 85 : [ [ 'Bugatti', 457 ], [ 'U', 100 ] ]
console.log(ht.loadFactor()) // [Log]: 0.031
console.log('
retrieved: ', ht.retrieve('Ford')) // retrieved: 250
console.log('retrieved: ', ht.retrieve('Audi')) // retrieved: 320
console.log('retrieved: ', ht.retrieve('Bugatti')) // retrieved: 457
console.log('retrieved: ', ht.retrieve('U')) // retrieved: 100
console.log('
' + ht.delete('U')) // true
ht.display()
// [Log]:
// 6: [ 'Audi', 320 ]
// 14: [ 'Ford', 250 ]
// 85: [ 'Bugatti', 457 ]
// A hash table is data structure that uses a an array and a hashing function to store and lookup data stored in key value pairs.
// It also implements a collision strategy to handle multiple hashes that may produce the same index.
// In my example I will use seperate chaining to handle hash collisions, which means we can store multiple key value pairs in the same index using a map or an array, or a linked list. I will be using maps.
class HashTable {
constructor(size = 0) {
this.size = size;
this.hashMap = new Array(size)
for(let i = 0; i < this.size; i++) {
this.hashMap[i] = new Map();
}
}
// Hash our key and return the outputed idx % our hashtable size
hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % this.size;
}
// Insert key value pair at hashed idx
insert(key, value) {
const idx = this.hash(key);
this.hashMap[idx].set(key, value);
return;
}
// Remove an item at hashed idx
remove(key) {
let idx = this.hash(key);
let removedItem = this.hashMap[idx].get(key);
if(removedItem) {
// Remove the item and return it
this.hashMap[idx].delete(key);
return console.log('REMOVED: ' + removedItem);
}
return null;
}
// Retrieve a value at hashed idx
retrieve(key) {
let idx = this.hash(key);
let value = this.hashMap[idx].get(key);
if(value) {
return console.log('RETRIEVED: ' + value);
}
return null;
}
}
// Instantiate a new hash table with a size of 10;
const myHashTable = new HashTable(10);
// Let pretends in a game when we reach a certain level, we get a reward. And this hashtable stores the rewards and levels needed.
// Inserting
myHashTable.insert("level-1", 'shortsword');
myHashTable.insert("level-5", 'longsword');
myHashTable.insert("level-9", 'poisen arrows');
// Print out the table
console.log(myHashTable);
// Removing
myHashTable.remove("level-1");
// Print out the table
console.log(myHashTable);
// Retrieving
myHashTable.retrieve("level-5");
myHashTable.retrieve("level-1");
// Print out the table
console.log(myHashTable);
// JavaScript's Object type is a special hash table
// The most common example of a Hash Table in JavaScript is the Object data type,
// where you can pair the object's property value with a property key.
In the following example, the likes object contain what people like by having their
name "John" as Key and "Playing Football" as the value.
let likes = {
John: "Playing Football",
Jane: "Watching Soap Operas"
}
More details
https://www.freecodecamp.org/news/javascript-hash-table-associative-array-hashing-in-js/