Hash table implementation

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.

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

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]);		
	}

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

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);	
	}

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

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)

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 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

	//Calculate hashcode by key, Time O(1), Space O(1)
	public int hashFunc(K key) {
		return Integer.parseInt(key.toString()) % maxSize;
	}

//Calculate hashcode by key, Time O(1), Space O(1)

public int hashFunc(K key) {

return Integer.parseInt(key.toString()) % maxSize;

}

JavaScript

	//Calculate hashcode by key, Time O(1), Space O(1)
	hashFunc(key) {
		return key % this.maxSize;
	}

//Calculate hashcode by key, Time O(1), Space O(1)

hashFunc(key) {

return key % this.maxSize;

}

Python

    #Calculate hashcode by key, Time O(1), Space O(1)
    def hashFunc(self, key):
        return int(key) % self.maxSize

#Calculate hashcode by key, Time O(1), Space O(1)

def hashFunc(self, key):

return int(key) % self.maxSize

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

	//Add an entry, Time O(1), Space O(1) 
	public void put(K key, V value) {
		int x = hashFunc(key);
		if (x < 0) {	
			System.out.println("invalid hash code");
			return;
		}
		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);
	}

//Add an entry, Time O(1), Space O(1)

public void put(K key, V value) {

int x = hashFunc(key);

if (x < 0) {

System.out.println("invalid hash code");

return;

}

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

	//Add an entry, Time O(1), Space O(1) 
	put(key, value) {
		var x = this.hashFunc(key);
		if (x < 0)
			return;
		if (this.buckets[x] == null) 
            this.buckets[x] = new Array();
		var list = this.buckets[x];
		var entry = new Entry(key, value);
		list.push(entry);
	}

//Add an entry, Time O(1), Space O(1)

put(key, value) {

var x = this.hashFunc(key);

if (x < 0)

return;

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

    #Add an entry, Time O(1), Space O(1)
    def put(self, key, value):
        x = self.hashFunc(key)
        if x < 0:
            return
        if self.buckets[x] == None:
            self.buckets[x] = []
        list = self.buckets[x]
        entry = Entry(key, value)
        list.append(entry)

#Add an entry, Time O(1), Space O(1)

def put(self, key, value):

x = self.hashFunc(key)

if x < 0:

return

if self.buckets[x] == None:

self.buckets[x] = []

list = self.buckets[x]

entry = Entry(key, value)

list.append(entry)

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

	//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 (x < 0) {	
			System.out.println("invalid hash code");
			return;
		}
        if (buckets[x] == null)
        	return;
        LinkedList<Entry<K, V>> list = buckets[x];
        LinkedList<Entry<K, V>> newList = new LinkedList<>(); //copy to another list
        for (Entry<K, V> entry : list) {
        	if (!entry.key.equals(key)) {
                newList.add(entry);
        	}
        }
        buckets[x] = (newList.size() == 0) ? null: new LinkedList<>(newList); 
    }

//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 (x < 0) {

System.out.println("invalid hash code");

return;

}

if (buckets[x] == null)

return;

LinkedList<Entry<K, V>> list = buckets[x];

LinkedList<Entry<K, V>> newList = new LinkedList<>(); //copy to another list

for (Entry<K, V> entry : list) {

if (!entry.key.equals(key)) {

newList.add(entry);

}

buckets[x] = (newList.size() == 0) ? null: new LinkedList<>(newList);

}

JavaScript

	//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 (x < 0)
			return;
        if (this.buckets[x] == null)
        	return;
        var list = this.buckets[x];
        var newList = new Array();
        for (let entry of list) {
        	if (entry.key !== key) 
                newList.push(entry);
        }
		this.buckets[x] = (newList.length == 0)? null: new Array(newList); 
    }

//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 (x < 0)

return;

if (this.buckets[x] == null)

return;

var list = this.buckets[x];

var newList = new Array();

for (let entry of list) {

if (entry.key !== key)

newList.push(entry);

}

this.buckets[x] = (newList.length == 0)? null: new Array(newList);

}

Python

	#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 x < 0:
            return
        if self.buckets[x] == None:
            return
        list = self.buckets[x]
        newList = []
        for entry in list:            
            if str(entry.key) != str(key):
                newList.append(entry)
        self.buckets[x] = None if  len(newList) == 0 else newList

#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 x < 0:

return

if self.buckets[x] == None:

return

list = self.buckets[x]

newList = []

for entry in list:

if str(entry.key) != str(key):

newList.append(entry)

self.buckets[x] = None if len(newList) == 0 else newList

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

	//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 (x < 0) {	
			System.out.println("invalid hash code");
			return null;
		}
		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;		
	}

//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 (x < 0) {

System.out.println("invalid hash code");

return null;

}

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

	//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 (x < 0)
			return null;
		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;		
	}

//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 (x < 0)

return null;

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

	#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 x < 0:
            return None
        if self.buckets[x] == None: 
            return None
        list = self.buckets[x]
        for entry in list:
            if str(entry.key) == str(key): 
                return entry.value
        return None

#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 x < 0:

return None

if self.buckets[x] == None:

return None

list = self.buckets[x]

for entry in list:

if str(entry.key) == str(key):

return entry.value

return None

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

    //Print the whole hash table, Time O(m+n), Space O(1), 
    //m is the size of the buckets, n is number of entries in a hashtable 
	void print() {
		for (int i = 0; i < maxSize; i++) {    		
			LinkedList<Entry<K, V>> list = buckets[i];
			if (list != null) {
				for (Entry<K, V> entry : list)
					System.out.print(entry + " ");
				System.out.println();
			}
		}
	}

//Print the whole hash table, Time O(m+n), Space O(1),

//m is the size of the buckets, n is number of entries in a hashtable

void print() {

for (int i = 0; i < maxSize; i++) {

LinkedList<Entry<K, V>> list = buckets[i];

if (list != null) {

for (Entry<K, V> entry : list)

System.out.print(entry + " ");

System.out.println();

}

JavaScript

    //Print the whole hash table, Time O(m+n), Space O(n), 
    //m is the size of the buckets, n is number of entries in a hashtable 
	print() {
		for (let i = 0; i < this.maxSize; i++) {    		
			let list = this.buckets[i];
			if (list != null) {
				var s = '';
    			for (let entry of list)
            		s += entry + ' ' ;
				console.log(s);
			}
		}
	}

//Print the whole hash table, Time O(m+n), Space O(n),

//m is the size of the buckets, n is number of entries in a hashtable

print() {

for (let i = 0; i < this.maxSize; i++) {

let list = this.buckets[i];

if (list != null) {

var s = '';

for (let entry of list)

s += entry + ' ' ;

console.log(s);

}

Python

    #Print the whole hash table, Time O(m+n), Space O(1), 
    #m is the size of the buckets, n is number of entries in a hashtable 
    def print(self):
        for i in range(0, self.maxSize):     		
            list = self.buckets[i]
            if list != None:
                for entry in list:
                    print(str(entry) , end = " ")
                print()

#Print the whole hash table, Time O(m+n), Space O(1),

#m is the size of the buckets, n is number of entries in a hashtable

def print(self):

for i in range(0, self.maxSize):

list = self.buckets[i]

if list != None:

for entry in list:

print(str(entry) , end = " ")

print()

Doodle

hash table print

Free download

Download hash table implementation in Java, JavaScript and Python
Illustrated Data Structures (Java) Book

Login

Table of Content

Define classes

Java

Javascript

Python

Hashing and hash function

Java

JavaScript

Python

The put method in hash table implementation

Java

JavaScript

Python

Doodle

Delete

Java

JavaScript

Python

Doodle

Get

Java

JavaScript

Python

Doodle

Print

Java

JavaScript

Python

Doodle

Free download