首页 > itarticle > [leetcode] problem 706 – design hashmap

[leetcode] problem 706 – design hashmap

admin 11月 13, 2020 0

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

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(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

private int size = 1000;
private Node[] map;

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

    public  (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;
}