0%

706. Design HashMap

题目

原题在此

解析

参考wiki, 实现HashMap, 需要考虑的有如下几点:

  1. 均匀分布的散列函数
  2. 冲突处理
  3. 动态扩容

面试能把这几点说清楚就差不多了. 这题不应该标记简单…

代码

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
// template <typename K, typename V>
class MyHashMap {
public:
/** Initialize your data structure here. */
MyHashMap() {
length = 0;
v.resize(20);
}

/** value will always be non-negative. */
void put(int key, int value) {
// ref from http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html
// As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs.
// Higher values decrease the space overhead but increase the lookup cost (reflected in most of the
// operations of the HashMap class, including get and put).
// The expected number of entries in the map and its load factor should be taken into account when setting
// its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is
// greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
if(double(length / v.size()) > 0.5) expand();
int idx = hash(key);
auto head = v[idx];
auto tmp = head;
while(tmp) {
if(key == tmp -> key) {
tmp -> value = value;
return;
}
tmp = tmp -> next;
}
Node* node = new Node(key, value);
node -> next = head;
v[idx] = node;
length++;
}

/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
// int idx = hash(key);
Node* node = v[hash(key)];
while(node) {
if(key == node -> key) return node -> value;
node = node -> next;
}
return -1;
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
int idx = hash(key);
auto node = v[idx];
Node* prev = NULL;
while(node) {
if(key == node -> key) {
--length;
prev ? prev -> next = node -> next : v[idx] = node -> next;
}
prev = node;
node = node -> next;
}
}

private:
struct Node;
vector<Node*> v;
int length;

// Dynamic resizing
void expand() {
vector<Node*> tmp(v.size());
v.swap(tmp);
v.resize(v.size() * 2);
length = 0;
for(auto &node : tmp) {
while(node) {
put(node -> key, node -> value);
node = node -> next;
}
}
}

// knuth multiplicative hash
int hash(int key){
return (long long)key * 2654435761 % v.size();
}

// template <typename K, typename V>
struct Node {
Node(const int &key, const int &value) : key(key), value(value), next(NULL) {}
int key;
int value;
Node* next;
};
};

/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap* obj = new MyHashMap();
* obj->put(key,value);
* int param_2 = obj->get(key);
* obj->remove(key);
*/