Here we will see how to create a custom HashMap uaing Java language. We have seen the built-in implementation of HashMap in Java API and we know how HashMap works and its usages.

The intention of this example is not to create a rigid HashMap that provides the same functionalities as Java API provides but to give an idea how you can create your own HashMap.

We know also how HashMap works internally and here also we will look into the internal works of HashMap with same basic functionalities.

The complete example code of custom HashMap is given below

package com.jeejava.map;

public class HashMap<K, V> {

	private Entry<K, V>[] entryTable;
	private int initialCapacity = 16;

	@SuppressWarnings("unchecked")
	public HashMap() {
		entryTable = new Entry[initialCapacity];
	}

	@SuppressWarnings("unchecked")
	public HashMap(int capacity) {
		initialCapacity = capacity;
		entryTable = new Entry[initialCapacity];
	}

	public void put(K key, V value) {
		if (key == null) {
			throw new RuntimeException("null key is not allowed");
		}
		// hash value of the key
		int hashValue = hashValue(key);
		// create the entry
		Entry<K, V> entry = new Entry<K, V>(key, value, null);

		// if no entry found at the hash value index of the entry table then put
		// the value
		if (entryTable[hashValue] == null) {
			entryTable[hashValue] = entry;
		} else {// if found then put the value in a linked list
			Entry<K, V> previous = null;
			Entry<K, V> current = entryTable[hashValue];
			while (current != null) {
				if (current.k.equals(key)) {
					if (previous == null) {
						entry.next = current.next;
						entryTable[hashValue] = entry;
					} else {
						entry.next = current.next;
						previous.next = entry;
					}
				}
				previous = current;
				current = current.next;
			}
			previous.next = entry;
		}

	}

	public V get(K key) {
		if (key == null) {
			return null;
		}
		// hash value of the key
		int hashValue = hashValue(key);
		if (entryTable[hashValue] == null) {
			return null;
		} else {
			Entry<K, V> temp = entryTable[hashValue];
			while (temp != null) {
				if (temp.k.equals(key)) {
					return temp.v;
				}
				temp = temp.next;
			}
		}
		return null;
	}

	public boolean remove(K key) {
		if (key == null) {
			return false;
		}
		// hash value of the key
		int hashValue = hashValue(key);
		if (entryTable[hashValue] == null) {
			return false;
		} else {
			Entry<K, V> previous = null;
			Entry<K, V> current = entryTable[hashValue];
			while (current != null) {
				if (current.k.equals(key)) {
					if (previous == null) {
						entryTable[hashValue] = entryTable[hashValue].next;
						return true;
					} else {
						previous.next = current.next;
						return true;
					}
				}
				previous = current;
				current = current.next;
			}
			return false;
		}
	}

	public boolean containsKey(K key) {
		int hashValue = hashValue(key);
		if (entryTable[hashValue] == null) {
			return false;
		} else {
			Entry<K, V> current = entryTable[hashValue];
			while (current != null) {
				if (current.k.equals(key)) {
					return true;
				}
				current = current.next;
			}
		}
		return false;
	}

	public int size() {
		int count = 0;
		for (int i = 0; i < entryTable.length; i++) {
			if (entryTable[i] != null) {
				int nodeCount = 0;
				for (Entry<K, V> e = entryTable[i]; e.next != null; e = e.next) {
					nodeCount++;
				}
				count += nodeCount;
				count++;// consider also vertical count
			}
		}
		return count;
	}

	private int hashValue(K key) {
		return Math.abs(key.hashCode()) % initialCapacity;
	}

	private static class Entry<K, V> {
		private K k;
		private V v;
		private Entry<K, V> next;

		public Entry(K k, V v, Entry<K, V> next) {
			this.k = k;
			this.v = v;
			this.next = next;
		}

	}

}

In the above class, we have private class Entry<K, V> that stores key/value pair in a bucket location in linked list fashion. We also compute the hash value(bucket location) of entry table using method hashValue(). We have two contsructors in the HashMap class, one is with default capacity and another is having capacity passed by client when HashMap object gets constructed.

Now method

put(K k, V v)

In this method first we calculate the bucket location(hash value) and check if bucket location is empty, then simply put the new entry. If there is already any entries in the bucket location then we iterate through the entries and at the last we put our new entry.

get(K k)

In this method if we find any entry then we check the equality for key and return the value for the corresponding entry.

remove(K k)

If we find any entry then simply de-link the node from linked list and return true.

containsKey(K k)

determines if any entry is present in the entry table.

size()

returns the number of non-nullable elements from the entry table. Here we need to consider node counts of each linked list as well as vertical count for each bucket location.

Create below test class to test the above HashMap class

package com.jeejava.map;

public class HashMapTest {

	public static void main(String[] args) {
		HashMap<String, String> map = new HashMap<>(3);
		map.put("1", "Hello");
		map.put("2", "World");

		System.out.println("Size: " + map.size());

		String hello = map.get("1");
		String world = map.get("2");

		System.out.println(hello + " " + world);

		System.out.println("Contains Key 1: " + map.containsKey("1"));
		System.out.println("Contains Key 2: " + map.containsKey("2"));
		System.out.println("Contains Key 3: " + map.containsKey("3"));

		map.put("3", "Dummy");

		System.out.println("Contains Key 3: " + map.containsKey("3"));
		System.out.println("Size: " + map.size());

		map.remove("3");

		System.out.println("Contains Key 3: " + map.containsKey("3"));
		System.out.println("Size: " + map.size());

		HashMap<String, String> map2 = new HashMap<>();
		map2.put("1", "Hello");
		map2.put("2", "World");
		map2.put("3", "Hello");
		map2.put("4", "World");
		map2.put("5", "Hello");
		map2.put("6", "World");
		map2.put("7", "Hello");
		map2.put("8", "World");
		map2.put("9", "Hello");
		map2.put("10", "World");
		map2.put("11", "Hello");
		map2.put("12", "World");
		map2.put("13", "Hello");
		map2.put("14", "World");
		map2.put("15", "Hello");
		map2.put("16", "World");

		System.out.println("map2 size: " + map2.size());
		System.out.println("Get Key 1: " + map2.get("1"));
		System.out.println("Get Key 11: " + map2.get("11"));
		System.out.println("Get Key 6: " + map2.get("6"));
		System.out.println("Get Key 16: " + map2.get("16"));
	}

}

Output

Size: 2
Hello World
Contains Key 1: true
Contains Key 2: true
Contains Key 3: false
Contains Key 3: true
Size: 3
Contains Key 3: false
Size: 2
map2 size: 16
Get Key 1: Hello
Get Key 11: Hello
Get Key 6: World
Get Key 16: World

Thanks for reading.

Tags:

I am a professional Web developer, Enterprise Application developer, Software Engineer and Blogger. Connect me on Roy Tutorials | TwitterFacebook Google PlusLinkedin | Reddit

Leave a Reply

Your email address will not be published. Required fields are marked *