0706. Design HashMap

0706. Design HashMap

一月 05, 2017

706. Design HashMap

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); // 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.

思路

设计一个HashMap的几点:

  • 设计一个合适的散列函数;
  • 定义装载因子阈值,并且设计动态扩容策略;
  • 选择合适的散列冲突解决方法。

工业级的HashMap主要采用链表法,有的库为了优化还采用红黑树。

这里就粗暴的用两个链表来实现。

  • 时间复杂度 O(N)
  • 空间复杂度 O(N)

代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
use std::cell::RefCell;
use std::rc::{Rc, Weak};

#[derive(Clone, Debug)]
pub struct MyLinkedList {
len: i32,
head: Option<Rc<RefCell<Node>>>,
tail: Option<Rc<RefCell<Node>>>,
}

#[derive(Clone, Debug)]
struct Node {
pub key: i32,
pub val: i32,
pub prev: Option<Weak<RefCell<Node>>>,
pub next: Option<Rc<RefCell<Node>>>,
}

impl Node {
pub fn new(key: i32, val: i32) -> Self {
Node {
key,
val,
prev: None,
next: None,
}
}
}


impl MyLinkedList {
pub fn new() -> Self {
let ret = MyLinkedList {
len: 0,
head: Some(Rc::new(RefCell::new(Node::new(0, 0)))),
tail: Some(Rc::new(RefCell::new(Node::new(0, 0)))),
};
ret.head.as_ref().unwrap().borrow_mut().next = ret.tail.clone();
ret.tail.as_ref().unwrap().borrow_mut().prev = Some(Rc::downgrade(ret.head.as_ref().unwrap()));
ret
}

pub fn push(&mut self, key: i32, val: i32) {
if let Some(p) = self.find_by_key(key) {
p.borrow_mut().val = val;
return;
}

let p = self.tail.clone().unwrap();
let p = p.borrow().prev.as_ref().unwrap().upgrade().clone().unwrap();


let next = p.borrow().next.clone().unwrap();
let prev = p;


let node = Rc::new(RefCell::new(Node::new(key, val)));
node.borrow_mut().prev = Some(Rc::downgrade(&prev));
node.borrow_mut().next = Some(next.clone());

next.borrow_mut().prev = Some(Rc::downgrade(&node));
prev.borrow_mut().next = Some(node);

self.len += 1;
}

#[inline]
fn find_by_key(&self, key: i32) -> Option<Rc<RefCell<Node>>> {
let mut p = self.head.clone().unwrap();
for _ in 0..self.len {
let next = p.borrow().next.clone().unwrap();
p = next;
if p.borrow().key == key {
return Some(p);
}
}
None
}

pub fn get(&self, key: i32) -> i32 {
self.find_by_key(key).map(|p| p.borrow().val).unwrap_or(-1)
}

pub fn remove_by_key(&mut self, key: i32) {
if let Some(p) = self.find_by_key(key) {
let prev = p.borrow().prev.as_ref().unwrap().upgrade().clone().unwrap();
let next = p.borrow().next.clone().unwrap();

prev.borrow_mut().next = Some(next.clone());
next.borrow_mut().prev = Some(Rc::downgrade(&prev));
self.len -= 1;
}
}
}


struct MyHashMap {
map: Vec<Option<MyLinkedList>>,
}

/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl MyHashMap {

/** Initialize your data structure here. */
fn new() -> Self {

Self {
map: vec![None; 1001],
}
}


/** value will always be non-negative. */
fn put(&mut self, key: i32, value: i32) {

let idx = (key % 1001) as usize;
if self.map[idx].is_none() {
self.map[idx] = Some(MyLinkedList::new());
}
self.map[idx].as_mut().unwrap().push(key, value);

}

/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
fn get(&self, key: i32) -> i32 {
let idx = (key % 1001) as usize;
match self.map[idx].as_ref() {
None => -1,
Some(sub_map) => sub_map.get(key)
}
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
fn remove(&mut self, key: i32) {
let idx = (key % 1001) as usize;
if let Some(sub_map) = self.map[idx].as_mut() {
sub_map.remove_by_key(key);
}
}
}
  • 执行用时: 36 ms
  • 内存消耗: 4.6 MB

题型与相似题

题型

1.哈希表

相似题

代码链接

design_hashmap