leetcode_rust/
design_hashmap.rs

1#![allow(dead_code)]
2
3use std::collections::LinkedList;
4use std::iter;
5
6type Pair = (i32, i32);
7
8struct MyHashMap {
9    bucket: Vec<LinkedList<Pair>>,
10    len: i32,
11}
12
13impl MyHashMap {
14    /** Initialize your data structure here. */
15    fn new() -> Self {
16        let len: i32 = 2047;
17        let bucket = iter::repeat(LinkedList::new())
18            .take(len as usize)
19            .collect::<Vec<LinkedList<Pair>>>();
20        Self { bucket, len }
21    }
22
23    /** value will always be non-negative. */
24    fn put(&mut self, key: i32, value: i32) {
25        match self._find(key) {
26            Some(pair) => {
27                (*pair).1 = value;
28            }
29            None => {
30                let index = self._hash(key);
31                let list = &mut self.bucket[index];
32                list.push_front((key, value));
33            }
34        }
35    }
36
37    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
38    fn get(&mut self, key: i32) -> i32 {
39        match self._find(key) {
40            Some(pair) => (*pair).1,
41            None => -1,
42        }
43    }
44
45    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
46    fn remove(&mut self, key: i32) {
47        match self._find(key) {
48            None => {}
49            // zero never be used
50            Some(val) => {
51                (*val).1 = -1;
52            }
53        }
54    }
55
56    #[inline]
57    pub fn contains(&mut self, key: i32) -> bool {
58        match self._find(key) {
59            Some(_) => true,
60            None => false,
61        }
62    }
63
64    #[inline]
65    fn _find(&mut self, key: i32) -> Option<&mut Pair> {
66        let index = self._hash(key);
67        let list = &mut self.bucket[index];
68        for val in list.iter_mut() {
69            if (*val).0 == key {
70                return Some(val);
71            }
72        }
73
74        None
75    }
76
77    #[inline]
78    fn _hash(&self, key: i32) -> usize {
79        key as usize % self.len as usize
80    }
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86
87    #[test]
88    fn test1() {
89        let mut obj = MyHashMap::new();
90        obj.put(1, 1);
91        obj.put(2, 2);
92        let res = obj.get(1);
93        assert_eq!(res, 1);
94        let res = obj.get(3);
95        assert_eq!(res, -1);
96        obj.put(2, 1);
97        let res = obj.get(2);
98        assert_eq!(res, 1);
99        obj.remove(2);
100        let res = obj.get(2);
101        assert_eq!(res, -1);
102    }
103}
leetcode_rust/design_hashmap.rs

leetcode_rust/
design_hashmap.rs
