What is a hashmap?
other references: hash, hash table, map, dictionary, unordered-map, collection, associative-array
A hashmap is a data structure containing an unordered collection of keys that are mapped to values using hashing.
Because of their array-like format, hashmaps map key labels to corresponding array indices where values are stored.
This removes the limitation of sequential numerical indices for ordering data, in turn allowing the use of flexible keys instead!
Properties
Key/Value
When using hashmaps, data is stored in the form of key/value pairs. The key, used to reference the data, can be any data type. Yes, even an object or an array can be a key when using a hashmap! Similarly, values in hashmaps are allowed to be null.
Hashing
Hashing is a term used to describe the manipulation of a string or input key, and representing it with a hash value. This hash value is typically determined by an algorithm or hash function.
Hashing functions are used to return indexes in the array where the value will be stored. Hashing functions take keys as inputs and return an index with the hashmap’s array. Hashing functions are deterministic, meaning the hashing function always returns the same index when provided the same key. Hashing functions must be predictable and consistent to retrieve the stored value via the key. A good hash function should be efficient and assign unique keys.
The three most common hash functions are Arithmetic Modular, Truncation, and Folding. Sometimes collisions occur when a hash function generates the same index for more than one key. Four common strategies to handle collisions include Chaining, Open Addressing or resizing the Array or List, Linear probing, and Double Hashing.
Collisions
A collision occurs when multiple keys hash to the same index. This is a situation in which two or more keys produce the same hash value, subsequently occupying the same array index. When this happens, you need to make sure that you can differentiate between conflicting keys.
Chaining, specifically separate chaining is one way to resolve this. This happens by storing multiple key-value pairs at the index in question. In this situation, you store all the key-pairs that collide in a linked-list and parse through them.
Open addressing is another approach to dealing with collisions. In this situation, all elements are stored in the hash table itself. This means that, at any given point, the hashmap's size must be greater than or equal to the number of keys stored in it.
Another solution, linear probing, involves linearly probing for the next open slot. To insert an element using a given key, compute to find the index at which there is an available slot and place the value in question there. If the slot is full, find the next available index to store the value. Otherwise, try for the next index. Repeat this process until an available slot is found in the hashmap.
The last solution, double hashing, uses the idea of applying a second hash function to the key when a collision occurs.
In this instance, hashString1() and hashString2() are hash functions and this.length represents the size of our hashmap. We repeat by increasing i when a collision occurs. This can be thought of as:
(hashString1(key) + i * hashString2(key)) % this.length
Implementation of Hashmap Class
Class
Use the constructor method to create and initialize your hashmap object.
class HashMap() {
constructor() {
this.hashMap = {}
this.length = 0
}
}
Hash Function
Hash functions take keys as inputs and return an index with the hashmap’s array.
The hash function below uses the built-in Javascript method charCodeAt() to cumulatively sum the input string values to assign an index value in memory.
hashString(str) {
let outputHash = 0
for (let i = 0; i < str.length; i++) {
const charCode = str.charCodeAt(i)
outputHash += charCode
}
return outputHash
}
Set
When adding values to a hashmap the first thing to do is create a hash for the key. If the key doesn’t exist, instantiate the existence of the index in the object, store it to an empty array, and increment the length counter. Then save the key and value into the hashmap object.
set(key, val) {
let hashIndex = this.hashString(key)
if (!this.hashMap[hashIndex]) {
this.hashMap[hashIndex] = []
this.length++
}
this.hashMap[hashIndex][key] = val
}
Get
One of the key benefits of a hashmap is its search speed. To retrieve values in a hashmap we use the hashing function to generate the index and then directly access that index and return the value at the hashed index (if present).
get(key) {
const hashIndex = this.hashString(key)
if (this.hashMap.hasOwnProperty(hashIndex) $$ this.hashMap[hashIndex].hashOwnProperty(key)) {
return this.hashMap[hashIndex][key]
} else {
return null
}
}
Delete
In order to delete a key/value pair in a hashmap, pass the key to the delete method. First, we use the hashing function to generate our index. Next, we store the value being returned from our get method in our variable. If that value exists, delete the key. Check to see if the key/value pair is empty, if not, delete the index of the hashmap entry and also decrement the hashmap length by 1.
delete(key) {
const hashIndex = this.hashString(key);
let value = this.get(key);
if (value) delete this.hashMap[hashIndex][key];
if (!Object.keys(this.hashMap[hashIndex]).length) {
delete this.hashMap[hashIndex];
this.length--;
}
}
Syntax to store, retrieve, and delete entries
Use the .set and .get methods to add/update and retrieve a specified key/value pair within a hashmap. Use .delete method to remove a key/value pair from hashmap.
var usCities = new Hashmap();
usCities.set("New York City", "8,442,233");
usCities.set("San Antonio", "1,509,976");
usCities.set("San Diego", "1,410,898");
console.log(usCities.get("New York City")); // 8,442,233
console.log(usCities);
// Hashmap { hashmap:
{ 810: ['San Diego': '1,410,898'],
1050: ['San Antonio': '1,509,976'],
1192: ['New York City': '8,442,233'] },
length: 3 }
usCities.delete("San Diego")
// Hashmap { hashMap:
{ 1050: ['San Antonio': '1,509,976'],
1192: ['New York City': '8,422,233'] },
length: 2 }
Time and Space Complexity Chart
Connect with the authors on Linkedin: Aram Martin and Rudy Becker
Cover photo by Simon Migaj on Unsplash
Charts made with Excalidraw
Top comments (1)
Interesting article. When I think of hash maps I think of them as an array of "buckets", with each bucket being an array of length 2 ([key, value]).
Initializing your hashmap as an empty Javascript object and assigning the keys as properties of that object you are essentially just using the baked in javascript definition of a hash map in your implementation of a hash map. Javascript objects are already hashmaps in their implementation. I hope that makes sense.