What are Hash Tables and How to Implement Them Part 1

I’ve been asked this question one too many times now to not write about it.

Hash Table Review: A hash table, often called a hash map, is a data structure that maps keys to values. Hash tables combine lookup, insert, and delete operations efficiently by sending the key to a hash function that performs arithmetic operations on it. The result, called the hash value or hash, is an index of the key-value pair. This data structure is used in many types of computer software, and usually, the operation returns the same hash for a given key.

The performance of a hash table can be measured by three dimensions: the hash function, size of the hash table, and collision handling method.

Hash tables are made up of an object that holds the data. The data is in the form of an array with key-value entries in the table. The size of the data is relative to the amount of data.

Hash tables are highly recommended for algorithms that provide search and data retrieval operations, as the average time complexity is O(1), thus being more efficient compared to other lookup data structures. Hash tables are used for database indexing, caches, unique data representation, lookup in an unsorted array, and lookup in a sorted array using binary search.

What is a Hash Function?

A hash function (or mapping function) determines the index of the key-value pair. It should be a one-way function and produce a different hash for each key. In JavaScript, these hash tables are generally implemented using arrays since they provide access to elements in constant time. The hash function helps limit the range of the keys to the boundaries of the array, so the function should convert a large key into a smaller key.

Hash Table Collision

In a hash table, every slot in the hash table is supposed to store a single element. However, when this premise is broken, it is known as a hash table. Fortunately, there are different approaches to resolving this issue, such as linear probing, chaining, resizing the array or list, and double hashing. Linear probing skips an index that’s already filled, chaining uses pointers to keep track of hash values that are already used, resizing the array creates more available hash values thus lowering collision probability, and double hashing creates a backup hash value in case the first value is already taken.

How to Implement a Hash Table

To implement a hash table, the three general overview steps are creating a hash table class, add a hash function, and implement a method for adding key/value pairs to our table.

In the constructor of creating the hash table, the properties values, length, and size will be stored.

Then, we implement a hashing function, which takes the provided key and returns a hash that’s calculated using an arithmetic modulus.

Lastly, we create a method to insert key/value pairs.

The actual code will be Part 2!