[LeetCode] Problem 706 - Design HashMap

Posted on | In ,

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

To be specific, your design should include these functions:

put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.

get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.

remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example

1
2
3
4
5
6
7
8
9
MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);          // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found)

Note

  • All keys and values will be in the range of [0, 1000000].
  • The number of operations will be in the range of [1, 10000].
  • Please do not use the built-in HashMap library.

Code

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
private int size = 1000;
private Node[] map;

private class Node{
    int key;
    int value;
    Node next;

    public Node (int key, int value){
        this.key = key;
        this.value = value;
    }
}

public MyHashMap() {
    map = new Node[size];

    for (int i = 0; i < size; i++)
        map[i] = new Node(-1, -1);
}

public void put(int key, int value) {
    int hash = hash(key);
    Node p = find(map[hash], key);

    if (p.next == null)
        p.next = new Node(key, value);
    else
        p.next.value = value;
}

public int get(int key) {
    int hash = hash(key);
    Node p = find(map[hash], key);

    return p.next == null ? -1 : p.next.value;
}

public void remove(int key) {
    int hash = hash(key);
    Node p = find(map[hash], key);

    if (p.next != null)
        p.next = p.next.next;
}

private int hash(Integer x){
    return x.hashCode() % size;
}

private Node find(Node n, int key) {
    Node p = null;

    while (n != null && n.key != key) {
        p = n;
        n = n.next;
    }

    return p;
}