Hash Tables
Continuation of my intro to Data Structures and Algorithms series.
Hash tables are used to store key-values pairs. Anyone familiar with the Ruby coding language knows hashes well, they are present in other languages as well but go by different names, like in Python their called Dictionaries. Hashes are not ordered and they are FAST!!!
How fast? Well after we get done the big O time complexity of all our functions best case scenario will be O(1). Before we get there let’s talk about the components that make a hash table. First, we need our hashing algorithm to convert keys into valid array indices. We will implement a hash table by using an array.
Second, we need to deal with collisions, which happens when a hash function maps two different keys to the same table address. There are two conventions of thought dealing with collisions: Chain Probing and Linear Probing.
First our hash function, our function needs to be FAST this function is the backbone of our Table, so this determines our speed. Speaking of determining our function must be deterministic, the keys must be distribute keys uniformly.
function hash(key, arrayLen){
let total = 0;/*
The line below is to spread out the keys more uniformly. Prime numbers are useful for this purpose. But math is complicated, so knowing why is not in my realm of knowledge.
*/
let WEIRD_PRIME = 31;
for(let i = 0; i < Math.min(key.length, 100); i++){
/*
The purpose of the above line is for speed, whichever number is smaller the key.length or the number 100 to limit our loop. If you pass a string with more than 100 chars and the first 100 characters are the same then we change this line but for general purpose this works.
*/
let char = key[i]
let value = char.charCodeAt(0) - 96;
total = (total + WEIRD_PRIME + value) % arrayLen;
}
return total;
}
Next we need to add this to our Hash Table class. Our Hash Table will have a default size of a prime number and it will be an array with the length of our prime number. We used 53 as our prime number.
class HashTable {
constructor(size=53){
this.keyMap = new Array(size);
}_hash(key) {
let total = 0;
let WEIRD_PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
let char = key[i];
let value = char.charCodeAt(0) - 96
total = (total * WEIRD_PRIME + value) % this.keyMap.length;
}
return total;
}
}
Next, dealing with our collisions. Again, collisions happen when a hash function maps two different keys to the same table address. Even with a large array and with a great hash function, collisions are inevitable. Chain Probing/ Separate Probing is one of our conventions to deal with collisions. This method stores things together in the same index. Linear probing is also a convention of collisions and this one everything gets its own index by searching for a free index in our array. We will be implementing the separate chaining method while creating our set and get functions.
The set function accepts a key and a value, hashes the key, and stores the key-value pair in the hash table array via separate chaining.
set(key, value){
let index = this._hash(key);
/* The line below checks if the index is already occupied with some key/value pairs. If it is empty create a new array, else push it to the end of the array.
*/
if(!this.keyMap[index]){
this.keyMap[index] = [];
}
this.keyMap[index].push([key, value]);
}The get function accepts a key, hashes the key, retrieves the key-value pair in the hash table and if the key isn’t found, return undefined.
get(key){
let index = this._hash(key);
if(this.keyMap[index]){
for(let i = 0; i < this.keyMap[index].length; i++){
if(this.keyMap[index][i][0] === key){
return this.keyMap[index][i][1]
}
}
}
return undefined;
}Add these two to our class.
class HashTable {
constructor(size=53){
this.keyMap = new Array(size);
}_hash(key) {
let total = 0;
let WEIRD_PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
let char = key[i];
let value = char.charCodeAt(0) - 96
total = (total * WEIRD_PRIME + value) % this.keyMap.length;
}
return total;
}set(key, value){
let index = this._hash(key);
// below line check if the index is already
// occupied with some key/value pairs.
// If it is empty create a new array
// else push it to the end of the array.
if(!this.keyMap[index]){
this.keyMap[index] = [];
}
this.keyMap[index].push([key, value]);
}
get(key){
let index = this._hash(key);
if(this.keyMap[index]){
for(let i = 0; i < this.keyMap[index].length; i++){
if(this.keyMap[index][i][0] === key){
return this.keyMap[index][i][1]
}
}
}
return undefined;
}
}
These two function handles most of our functionality in our class but we can go a little further.
We have to retrieve all of our keys and all of our values. These functions are pretty similar they both must loop through the hash table and return an array of the keys or values. We must deal with duplicates in both functions.
values(){
let valuesArr = [];
for(let i = 0; i < this.keyMap.length; i++){
if(this.keyMap[i]){
for(let j = 0; j < this.keyMap[i].length; j++){
if(!valuesArr.includes(this.keyMap[i][j][1])){
valuesArr.push(this.keyMap[i][j][1])
}
}
}
}
return valuesArr;
}keys(){
let keysArr = [];
for(let i = 0; i < this.keyMap.length; i++){
if(this.keyMap[i]){
for(let j = 0; j < this.keyMap[i].length; j++){
// handles duplicate
if(!keysArr.includes(this.keyMap[i][j][0])){
keysArr.push(this.keyMap[i][j][0])
}
}
}
}
return keysArr;
}
This was by far my favorite data structure. Thank you for taking the time walking through this data structure with me have a nice day.
