Hash table is a data structure that can map keys to values. A hash table uses a hash function to compute a key into an integer (hash value), which indicates the index of the buckets (aka array). From the key, the correct value can be stored and found. The time complexity is close to constant O(1). Hash table is one of the most used data structures. This post has hash table implementation using array and linked list. Code is available in Java, JavaScript and Python.
Table of Content
Define classes
The first thing is to define the Entry class. It has two attributes, key and value. Their data type can be anything such as Integer, String or object.
After defining the Entry, we can define HashTable class. It has two attributes, buckets and maxSize. buckets is an array of list of Entry. maxSize is the max length of the buckets.
Here are the reason why we use list of entries, not Entry itself. The hash function will assign each key to a unique bucket. But it is possible that two keys will generate an identical hash value, which causes both keys to point to the same bucket. this is called Collisions. Multiple (key, value) pairs coming to the same bucket form a list in the bucket. Ideally, hashing is O(1) for all insert, delete, and access. But because of collisions, we cannot guarantee the constant time in the worst case.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
import java.util.LinkedList; class Entry<K, V> { K key; V value; //Constructor, Time O(1), Space O(1) public Entry(K key, V val) { this.key = key; this.value = val; } //Check equality of entry,compare value not object, Time O(1), Space O(1) public boolean equals(Entry<K, V> entry) { if (!this.key.equals(entry.key)) return false; return this.value.equals(entry.value); } //Override, Time O(1), Space O(1) @Override public String toString() { return "(" + key.toString() + ", " + value.toString() + ")"; } } public class HashTable<K, V> { private int maxSize; private LinkedList<Entry<K, V>>[] buckets; //Constructor, Time O(1), Space O(m), m is max size @SuppressWarnings("unchecked") public HashTable(int capacity) { maxSize = capacity; buckets = ((LinkedList<Entry<K, V>>[]) new LinkedList[maxSize]); } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class Entry { //Constructor, Time O(1), Space O(1) constructor(key, val) { this.key = key; this.value = val; } //Check equality of entry, compare value not object, Time O(1), Space O(1) equals(entry) { if ( this.key != entry.key) return false; return this.value == entry.value; } //Override, Time O(1), Space O(1) toString() { return "(" + this.key.toString() + ", " + this.value.toString() + ")"; } } class HashTable { //Constructor, Time O(1), Space O(1) constructor(capacity) { this.maxSize = capacity; this.buckets = new Array(this.maxSize); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Entry: #Constructor, Time O(1), Space O(1) def __init__(self, key, val) : self.key = key self.value = val #Check equality of entry, compare value not object, Time O(1), Space O(1) def equals(self, entry): if str(self.key) != str(entry.key) : return False return str(self.value) == str(entry.value) #Override, Time O(1), Space O(1) def __str__(self): return "(" + str(self.key) + ", " + str(self.value) + ")" class HashTable : #Constructor, Time O(1), Space O(1) def __init__(self,capacity) : self.maxSize = capacity self.buckets = [None]*(self.maxSize) |
Hashing and hash function
Hashing is a technique to map a range of keys to a range of index of the buckets (aka array). 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. A easy and common hash function is to use the modulo operator(%). The formula is:
hashCode = key % maxSize.
hashCode is the index of buckets. key in the key of the input entry. maxSize is max length of buckets. To distribute hashCode more evenly over the array, maxSize is suggested to be prime number.
Load factor is the ratio of items in a hash table to the array size. A load factor of 1, roughly one third of the cells will be empty, one third will hold one item, and one third will hold two or more items. The load factor can be checked as threshold when to rehashing (resize the buckets in the hash table). In Java Collections, HashMap’s load factor is 0.75.
Java
|
1 2 3 4 |
//Calculate hashcode by key, Time O(1), Space O(1) public int hashFunc(K key) { return Integer.parseInt(key.toString()) % maxSize; } |
JavaScript
|
1 2 3 4 |
//Calculate hashcode by key, Time O(1), Space O(1) hashFunc(key) { return key.toString() % this.maxSize; } |
Python
|
1 2 3 |
#Calculate hashcode by key, Time O(1), Space O(1) def hashFunc(self, key) : return int(key) % self.maxSize |
Put in hash table implementation
Put operation is to save a (key, value) pair to the buckets. First it calls hashFunc to get the hashCode, i.e the index of the buckets to access the right bucket. If the bucket’s list is null, create a new list. Then add the new entry of given (key, value) pair to the end of the list.
Java
|
1 2 3 4 5 6 7 8 9 |
//Add an entry, Time O(1), Space O(1) public void put(K key, V value) { int x = hashFunc(key); if (buckets[x] == null) buckets[x] = new LinkedList<Entry<K, V>>(); LinkedList<Entry<K, V>> list = buckets[x]; Entry<K, V> entry = new Entry<K, V>(key, value); list.add(entry); } |
JavaScript
|
1 2 3 4 5 6 7 8 9 |
//Add an entry, Time O(1), Space O(1) put(key, value) { var x = this.hashFunc(key); if (this.buckets[x] == null) this.buckets[x] = new Array(); var list = this.buckets[x]; var entry = new Entry(key, value); list.push(entry); } |
Python
|
1 2 3 4 5 6 7 8 |
#Add an entry, Time O(1), Space O(1) def put(self, key, value) : x = self.hashFunc(key) if self.buckets[x] == None : self.buckets[x] = [] list = self.buckets[x] entry = Entry(key, value) list.append(entry) |
Doodle
Delete
Delete by key is to delete all entries with that key. The same as put, 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. In order to be thread-safe, a new list is created to backup the entries whose key is not the same as the input key. If all entries in the list should be deleted, set the list in this bucket to be null. Otherwise reset the list of this bucket to the new list.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
//Delete all entries by key, Time O(n), Space O(n), n is max length of list in bucket public void delete(K key) { int x = hashFunc(key); if (buckets[x] == null) return; LinkedList<Entry<K, V>> list = buckets[x]; LinkedList<Entry<K, V>> list2 = new LinkedList<>(); //copy to another list for (Entry<K, V> entry : list) { if (!entry.key.equals(key)) { list2.add(entry); } } buckets[x] = (list2.size() == 0) ? null: new LinkedList<>(list2); } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//Delete all entries by key, Time O(n), Space O(n), n is max length of list in bucket delete(key) { var x = this.hashFunc(key); if (this.buckets[x] == null) return; var list = this.buckets[x]; var list2 = new Array(); for (let entry of list) { if (entry.key !== key) list2.push(entry); } this.buckets[x] = (list2.length == 0)? null: new Array(list2); } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
#Delete all entries by key, Time O(n), Space O(n), n is max length of list in bucket def delete(self, key) : x = self.hashFunc(key) if self.buckets[x] == None: return list = self.buckets[x] list2 = [] for entry in list: if str(entry.key) != str(key): list2.append(entry) self.buckets[x] = None if len(list2) == 0 else list2 |
Doodle
Get
Get operation is to get the value by the key. The same as put, 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. 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 worst scenario. n is the length of this list. The average time is dependent on load factor. As load factor increases, the length of list grows. So is the access time.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//Return first found value by key, Time O(n), Space O(1), n is max length of list in bucket public V get(K key) { int x = hashFunc(key); if (buckets[x] == null) return null; LinkedList<Entry<K, V>> list = buckets[x]; for (Entry<K, V> entry : list) { if (entry.key.equals(key)) return entry.value; } return null; } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//Return first found value by key, Time O(n), Space O(1), n is max length of list in bucket get(key) { var x = this.hashFunc(key); if (this.buckets[x] == null) return null; var list = this.buckets[x]; for (let entry of list) { if (entry.key == key) return entry.value; } return null; } |
Python
|
1 2 3 4 5 6 7 8 9 10 |
#Return value by key, Time O(n), Space O(1), n is max length of list in bucket def get(self, key) : x = self.hashFunc(key) if self.buckets[x] == None : return None list = self.buckets[x] for entry in list: if entry.key == key : return entry.value return None |
Doodle
Print
Print is to print all entries in the Hash table. It loops through each bucket and calls a method printList to print elements in the list. If the list is empty, skip it.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//Print the whole hash table, Call printList, Time O(m*n), Space O(1), //m is size of buckets, n is max list size public void print() { for (int i = 0; i < maxSize; i++) { LinkedList<Entry<K, V>> list = buckets[i]; if (list != null) printList(list); } } //Print list in one bucket, Time O(n), Space O(1), n is list size private void printList(LinkedList<Entry<K, V>> list) { for (Entry<K, V> entry : list) System.out.print(entry + " "); System.out.println(); } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//Print the whole hash table, Call printList, Time O(m*n), Space O(n), //m is size of buckets, n is max list size print() { for (let i = 0; i < this.maxSize; i++) { let list = this.buckets[i]; if (list != null) this.printList(list); } } //Print list in one bucket, Time O(n), Space O(n), n is list size printList(list) { if (list.length == 0) return; var s = ''; for (let entry of list) s += entry + " "; console.log(s); } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#Print the whole hash table, Call printList, Time O(m*n), Space O(1), #m is size of buckets, n is max list size def print(self) : for i in range(0 , self.maxSize) : list = self.buckets[i] if list != None: self.printList(list) #Print list in one bucket, Time O(n), Space O(1), n is list size def printList(self, list) : if len(list) == 0: return for entry in list: print(str(entry) , end =" ") print() |
Doodle
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 array and hash table?
The element is array is accessed by index, which is a number. The element in hash map (hash table) is accessed by key. Since key can be any data type, i.e. number, string or object, hash map is more versatile. Now hash map is replacing array to be the underneath data structures for adjacency list in graph and children in trie.