706. Design HashMap

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

Implement MyHashMap class:

• MyHashMap() initializes the object with an empty map.
• void put(key, value) inserts a (key, value) pair into the HashMap. If the key already exists, update the corresponding value.
• int get(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]

Bucket of Vecs (linear scan for the key):

#![allow(unused)]
fn main() {
#[allow(dead_code)]
struct MyHashMap {
    buckets: Vec<Vec<(i32, i32)>>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
#[allow(dead_code)]
impl MyHashMap {
    // time O(1), space O(n)
    pub fn new() -> Self {
        Self {
            buckets: vec![Vec::new(); 1000],
        }
    }

    fn hash(key: i32) -> usize {
        key as usize % 1000
    }

    // time O(k), space O(1)
    pub fn put(&mut self, key: i32, value: i32) {
        let idx = Self::hash(key);
        for pair in self.buckets[idx].iter_mut() {
            if pair.0 == key {
                pair.1 = value;
                return;
            }
        }
        self.buckets[idx].push((key, value));
    }

    // time O(k), space O(1)
    pub fn get(&self, key: i32) -> i32 {
        let idx = Self::hash(key);
        for pair in &self.buckets[idx] {
            if pair.0 == key {
                return pair.1;
            }
        }
        -1
    }

    // time O(k), space O(1)
    pub fn remove(&mut self, key: i32) {
        let idx = Self::hash(key);
        if let Some(pos) = self.buckets[idx].iter().position(|p| p.0 == key) {
            self.buckets[idx].remove(pos);
        }
    }
}
}