706. Design HashMap

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

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.

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]]

Code

class MyHashMap {
    private int mod;
    // 每一个bucket中是一个LinkedList
    private List<Bucket> buckets;

    public MyHashMap() {
        this.mod = 2069;
        this.buckets = new ArrayList<>();

        for (int i = 0; i < this.mod; ++i) {
            this.buckets.add(new Bucket());
        }
    }

    public void put(int key, int value) {
        int hashKey = key % this.mod;
        this.buckets.get(hashKey).update(key, value);
    }

    public int get(int key) {
        int hashKey = key % this.mod;
        return this.buckets.get(hashKey).get(key);
    }


    public void remove(int key) {
        int hashKey = key % this.mod;
        this.buckets.get(hashKey).remove(key);
    }
}

class Pair<K, V> {
    public K key;
    public V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
}


class Bucket {
    private List<Pair<Integer, Integer>> bucket;

    public Bucket() {
        this.bucket = new LinkedList<>();
    }

    public Integer get(Integer key) {
        for (Pair<Integer, Integer> pair : this.bucket) {
            if (pair.key.equals(key)) {
                return pair.value;
            }
        }

        return -1;
    }

    public void update(Integer key, Integer value) {
        boolean found = false;
        for (Pair<Integer, Integer> pair : this.bucket) {
            if (pair.key.equals(key)) {
                pair.value = value;
                found = true;
            }
        }

        if (!found) {
            this.bucket.add(new Pair<>(key, value));
        }
    }

    public void remove(Integer key) {
        for (Pair<Integer, Integer> pair : this.bucket) {
            if (pair.key.equals(key)) {
                this.bucket.remove(pair);
                break;
            }
        }
    }
}

假设是平均分布,那么每个 bucket 的大小是 N/K, 所以搜索每个 bucket 的时间复杂度是 O(K/N)

time: O(N/K) space: O(K+M)