Design HashMap Problem

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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 - Using Array of LinkedList

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

static class Entry {
	int key;
	int val;
	Entry next;

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

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

Full Implementation

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

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

	static class Entry {
		int key;
		int val;
		Entry next;

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

	/**
	 * 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;
	}
}