A hash table is a data structure that maps keys to values for fast access. From the key, the correct value can be stored and found. The time complexity is close to constant O(1). The hash table is one of the most used data structures. This post has a hash table implementation in Java, JavaScript, and Python.

hash table implementation

Table of Content


Define classes

The first thing is to define the Entry class, which is a key-value pair. It has two attributes, key and value. Their data type can be anything such as Integer, String, or a customer-defined class.

After defining the Entry class, we can define a HashTable class. The HashTable has two attributes, buckets and maxSize. buckets is an array of entries. However, two keys may generate an identical hash value, which causes both keys to point to the same bucket. Multiple entries coming to the same bucket form a list. So buckets is an array of lists of entries. maxSize is the initial length of buckets.

Java

Javascript

Python


Hashing and hash function

Hashing is a technique to map a range of keys to a range of indices of the buckets. If both ranges are similar, no hash function is necessary. The key values can be used directly as array indices.

But more often the range of the indices is much smaller than the range of the keys. The hash function hashes(converts) a number in a large range into a number in a smaller range. Using the modulo operator(%) is an easy and common hash function. The formula is:

hashCode = key % maxSize.

hashCode is the index of buckets. key in the key of the input entry. maxSize is the max length of buckets. To distribute hashCode more evenly over the array, maxSize is suggested to be a prime number.

Java

JavaScript

Python


The put method in hash table implementation

The put operation saves a (key, value) entry to buckets. First, it calls hashFunc() to get the hashCode, i.e. the index to access the right bucket. If the bucket’s list is null, create a new list. Then add the new entry of the given (key, value) pair to the list.

Java

JavaScript

Python

Doodle

hash table put


Delete

Delete by key is to delete all entries with that key. The first thing is to call hashFunc to get the hashCode to access the right bucket. Then compare the key with each entry’s key in the list. To be thread-safe, a new list is created to back up the entries whose key is not the same as the input key. If all entries in the list are deleted, set the list in this bucket to null. Otherwise, reset the list of this bucket to the new list.

Java

JavaScript

Python

Doodle

hash table delete


Get

The get operation is to get the value by the key. Call hashFunc() to get the hashCode to access the right bucket. Then compare the key with each entry’s key in the list. Return the first matched entry’s value.

If there is only one item in the list, the time complexity is O(1). If there are many items in the list, access time is O(n) in the worst scenario. n is the length of this list.

Java

JavaScript

Python

Doodle

hash table get


Print

Print is to print all entries in the Hash table. It loops through each bucket and prints elements in the list. If the list is empty, skip it.

Java

JavaScript

Python

Doodle

hash table print


Free download

Download hash table implementation in Java, JavaScript and Python
Download combined Data Structures implementations in Java
Download combined Data Structures implementations in JavaScript
Download combined Data Structures implementations in Python


What’s the difference between an array and a hash table?

The element in an array is accessed by the index. The index is a number. The element in a hash table is accessed by a key. The key can be any data type, i.e. number, string, or object. So a hash map is more versatile.