Design HashMap

Problem

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

• MyHashMap() initializes the object with an empty map.
• void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
• int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Examples

Example 1:

Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now[[1,1]]
myHashMap.put(2, 2); // The map is now[[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now[[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now[[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now[[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now[[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now[[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now[[1,1]]

Constraints

• 0 <= key, value <= 10^6
• At most 10^4 calls will be made to put, get, and remove.

Solution

Method 1 - Chaining (Linked List Buckets)

The map is generally an array-based structure. If we store only one value at each array index, we may have issues with collisions. To handle collisions, we use chaining with linked lists. This is the classic approach for integer keys .

Key points:

• Use a hash function to map keys to array indices.
• Each array index points to a linked list of entries (for collision resolution).
• put, get, and remove operations traverse the linked list at the hashed index.

Pseudocode

1. Compute hash of key to get array index.
2. If no entry at index, insert new node.
3. If entry exists, traverse linked list:
   • If key exists, update value.
   • Else, append new node at end.
4. For get/remove, traverse list at hashed index.

// The map is generally an array based structure. But if we store only one value at array index, we may have issues with collisions.
// Our list class:
static class Entry {
	int key;
	int val;
	Entry next;

	public Entry(int key, int val) {
		this.key = key;
		this.val = val;
		next = null;
	}
}

Approach

Nnw we need hash function, we can use Integer.hashCode() on key.

• Put call - Each time from hash-code, we go to index in array. If we don't see any value there, that is no collision and we simply add the values to map. If there is a collision, there are 2 cases -
  • same key is added to map, so nothing to do just set the latest value.
  • different key is added to map, so just appended it to linked list
• Get call - Use hash function, and get the value. Traverse list and get the values
• Remove call - Use hash function, get the array index and remove the key from linked list

Code

Java

class MyHashMap {
	private static final int SIZE = 10000;
	private Entry[] table;

	/**
	 * Initialize your data structure here.
	 */
	public MyHashMap() {
		table = new Entry[SIZE];
	}

	private int hash(int i) {
		return Integer.hashCode(i);
	}

	/**
	 * value will always be non-negative.
	 */
	public void put(int key, int value) {
		Entry e = new Entry(key, value);
		int code = hash(key) % SIZE;
		if (table[code] == null) {
			table[code] = e;
		} else {
			addOrUpdateNode(table[code], e);
		}
	}

	private void addOrUpdateNode(Entry head, Entry newNode) {
		Entry pre = head;
		while (head != null) {
			if (head.key == newNode.key) {
				head.val = newNode.val;
				return;
			}
			pre = head;
			head = head.next;
		}
		pre.next = newNode;
	}

	/**
	 * Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
	 */
	public int get(int key) {
		int code = hash(key) % SIZE;
		Entry head = table[code];
		while (head != null) {
			if (head.key == key) {
				return head.val;
			}
			head = head.next;
		}
		return -1;
	}

	/**
	 * Removes the mapping of the specified value key if this map contains a mapping for the key
	 */
	public void remove(int key) {
		int code = hash(key) % SIZE;
		Entry head = table[code];
		Entry dummy = new Entry(0, 0), pre = dummy;
		dummy.next = head;
		while (head != null) {
			if (head.key == key) {
				pre.next = head.next;
				break;
			}
			pre = head;
			head = head.next;
		}
		table[code] = dummy.next;
	}
}

Python

class MyHashMap:
	def __init__(self):
		self.size = 10000
		self.table = [[] for _ in range(self.size)]

	def hash(self, key):
		return hash(key) % self.size

	def put(self, key, value):
		idx = self.hash(key)
		for i, (k, v) in enumerate(self.table[idx]):
			if k == key:
				self.table[idx][i] = (key, value)
				return
		self.table[idx].append((key, value))

	def get(self, key):
		idx = self.hash(key)
		for k, v in self.table[idx]:
			if k == key:
				return v
		return -1

	def remove(self, key):
		idx = self.hash(key)
		self.table[idx] = [(k, v) for k, v in self.table[idx] if k != key]

Method 2 - Open Addressing (Linear Probing)

This method demonstrates a hash table implementation using open addressing (linear probing) and a custom hash function. This is a more educational approach, showing how hash tables can be implemented from scratch for string keys or for learning purposes.

Key points:

• Uses a custom hash function (example for string keys).
• Handles collisions with linear probing.
• Includes logic for checking if the table is full.

Pseudocode

1. Compute hash of key to get array index.
2. If slot is empty, insert.
3. If slot is occupied and key matches, update value.
4. If slot is occupied and key does not match, move to next slot (linear probing).
5. For get/search, probe until key is found or all slots checked.

Notes

• The chaining method is a direct solution for Leetcode 706 (integer keys, linked list buckets).
• The open addressing method is a general-purpose educational hash table for string keys, using linear probing.
• Both methods illustrate core hash table concepts and can be compared for learning.

Probability of Collision

Given 100 items, the probability of collision for:

• 23 items is ~50%
• 50 items is 97%
• 70 items is 99.9%

Code

Python

class Dictionary:
	def __init__(self, table_size, prime):
		self.prime = prime
		self.item_count = 0
		self.table_size = table_size
		self.array = [None] * table_size

	def hash(self, key):
		index = 0
		a = 2692
		b = 8523
		for i in range(len(key)):
			index = (a * index + ord(key[i])) % self.table_size
			a = a * b % (self.table_size - 1)
		return index

	def is_full(self):
		return self.item_count >= self.table_size

	def insert(self, key, value):
		index = self.hash(key)
		if self.is_full():
			found = False
			end = (index - 1) % self.table_size
			while index != end:
				if self.array[index][0] == key:
					self.array[index] = [key, value]
					found = True
					break
				index = (index + 1) % self.table_size
			if not found:
				raise Exception("Dictionary is full!")
		else:
			while not self.is_full():
				if self.array[index] is not None and self.array[index][0] == key:
					self.array[index] = [key, value]
					break
				if self.array[index] is None:
					self.array[index] = [key, value]
					self.item_count += 1
					break
				index = (index + 1) % self.table_size

	def search(self, key):
		index = self.hash(key)
		if self.array[index][0] == key:
			return self.array[index][1]
		else:
			end = (index - 1) % self.table_size
			if self.array[end][0] == key:
				return self.array[end][1]
			index = (index + 1) % self.table_size
			while index != end:
				if self.array[index][0] == key:
					return self.array[index][1]
				else:
					index = (index + 1) % self.table_size
			raise KeyError(str(key) + " not found!")

Probability of Collision

Given 100 items, the probability of collision for:

• 23 items is ~50%
• 50 items is 97%
• 70 items is 99.9%