That is half 2 of a two-part article on hash tables. Within the first a part of this text we checked out what hash tables are, how they work, and the assorted components of a hash desk. On this half, we are going to implement a hash desk in Javascript, so let’s start.
Our hash desk goes to have 4 principal strategies and we’re going to be utilizing separate chaining to deal with collisions. We’ll use Map objects within the buckets/slots to retailer the information (keys and values). The 4 principal strategies of our hash desk are:
-
Put: Add a key and worth to the desk.
-
Get: Discover and return the worth of a key.
-
Take away: Delete a key and worth from the desk.
-
IsPresent: Examine if a key’s current within the desk.
Hash Perform
Earlier than we begin constructing our hash desk, we have to first make our hash perform.
const hashFunc = (key, measurement) => {
let hash = 0;
for (let i = 0; i < key.size; i++) {
hash += key.charCodeAt(i)
}
return hash % measurement
}
The hash perform takes in 2 parameters, the important thing and the scale of the desk. Every character in the secret’s transformed to UTF-16 code utilizing the charCodeAT string technique and added up, the ensuing worth is modded(%) by the scale of the desk, it is suggested that the scale be a first-rate quantity to scale back the probabilities of collision. The worth we get from the equation is returned and will probably be utilized in storing and retrieving knowledge in different features.
Hash Desk
class HashTable {
constructor(){
this.measurement = 97,
this.desk = Array(this.measurement)
}
}
The category constructor has solely 2 properties, the scale of the desk (97) and the array itself, hash tables use static arrays to retailer the information. The dimensions of a static array is ready when it’s created and won’t change until explicitly modified, in contrast to dynamic arrays that change with a rise within the knowledge inside them.
Put Methodology
put(key, knowledge){
let hashCode = hashFunc(key, this.measurement)
if(!this.desk[hashCode]){
this.desk[hashCode] = new Map();
this.desk[hashCode].set(key, knowledge);
}else {
this.desk[hashCode].set(key, knowledge)
}
}
The primary technique of our hash desk is the put technique, because the identify implies, it places knowledge into the desk; it takes 2 parameters the important thing and the information. Let’s break down the way it works.
Methodology Break-Down
- Get the hash code from the
hashFuncby passing it the important thing and the desk measurement property. - Examine if that bucket is occupied; if it isn’t occupied create a brand new map object and set the information in it.
- If that desk is occupied then simply insert the information into the map object that we all know will probably be there.
Get Methodology
get(key){
let hashCode = hashFunc(key, this.measurement)
if(this.desk[hashCode]){
return this.desk[hashCode].get(key)
}else {
return "no such knowledge"
}
}
The get technique takes a key and returns the information that’s paired with that key within the desk.
Methodology Break-Down
-
First, get the hash code from
hashFunc. -
Examine if there’s knowledge in that place of the desk; if sure, get the worth of the important thing from the map object and return it.
-
If that place within the desk is empty, let the person know the information would not exist.
Take away Methodology
take away(key){
let hashCode = hashFunc(key, this.measurement)
if(this.desk[hashCode]){
let knowledge = this.desk[hashCode].get(key);
this.desk[hashCode].delete(key)
return knowledge
}else {
return "no such knowledge"
}
}
This technique deletes knowledge from a desk.
Methodology Break-Down
-
First, get the hash code from
hashFunc. -
Examine if there’s knowledge in that place of the desk; if sure, get the worth of the important thing from the map object and retailer it in a variable; delete the important thing and worth from the map object, and return the variable.
-
If that place within the desk is empty, let the person know the information would not exist.
IsPresent Methodology
isPresent(key){
let hashCode = hashFunc(key, this.measurement)
if(this.desk[hashCode]){
return this.desk[hashCode].has(key);
}
}
It is a easy technique to find out if a key already exists within the desk.
Methodology Break-Down
-
First, get the hash code from
hashFunc. -
Examine if there’s knowledge in that place of the desk; if sure, test if the map object there has any keys that match the given key and return the end result.
Full Code
const hashFunc = (key, measurement) => {
let hashCode = 0;
for (let i = 0; i < key.size; i++) {
hashCode += key.charCodeAt(i)
}
return hashCode % measurement
}
class HashTable {
constructor(){
this.measurement = 97,
this.desk = Array(this.measurement)
}
put(key, knowledge){
let hashCode = hashFunc(key, this.measurement)
if(!this.desk[hashCode]){
this.desk[hashCode] = new Map();
this.desk[hashCode].set(key, knowledge);
}else {
this.desk[hashCode].set(key, knowledge)
}
}
get(key){
let hashCode = hashFunc(key, this.measurement)
if(this.desk[hashCode]){
return this.desk[hashCode].get(key)
}else {
return "no such knowledge"
}
}
take away(key){
let hashCode = hashFunc(key, this.measurement)
if(this.desk[hashCode]){
let knowledge = this.desk[hashCode].get(key);
this.desk[hashCode].delete(key)
return knowledge
}else {
return "no such knowledge"
}
}
isPresent(key){
let hashCode = hashFunc(key, this.measurement)
if(this.desk[hashCode]){
return this.desk[hashCode].has(key);
}
}
}
Conclusion
This brings us to the tip of this text on Hash Tables and this sequence on knowledge buildings. I realized quite a bit from writing these articles and it has helped me higher perceive and internalize sure ideas about programming and what it means to be a developer. My subsequent sequence will probably be on algorithms the place unwell cowl subjects similar to recursion, time complexity, house complexity, sorting and many others; I hope you will give them a learn. The code for this text might be discovered right here. Thanks for making it this far and see you quickly.
