-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathHashMap.cc
More file actions
91 lines (80 loc) · 2.29 KB
/
HashMap.cc
File metadata and controls
91 lines (80 loc) · 2.29 KB
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
#include <stdio.h>
#include <iostream>
template <typename KEY, typename VALUE>
KEY Node<KEY, VALUE>::getKey() {
return key;
}
template <typename KEY, typename VALUE>
VALUE Node<KEY, VALUE>::getValue() {
return value;
}
template <typename KEY, typename VALUE>
HashMap<KEY, VALUE>::HashMap():n(0), head(kHASHSIZE) {
for (int i = 0; i < kHASHSIZE; i++) {
Node<KEY, VALUE> *temp = new Node<KEY, VALUE>();
head[i] = temp;
}
}
template <typename KEY, typename VALUE>
int HashMap<KEY, VALUE>::size() {
return n;
}
template <typename KEY, typename VALUE>
bool HashMap<KEY, VALUE>::empty() {
return n == 0;
}
template <typename KEY, typename VALUE>
int HashMap<KEY, VALUE>::insert(KEY key, VALUE value) {
unsigned long long hv = HashValue(key);
int p = hv % kHASHSIZE;
for (Node<KEY, VALUE> *ptr = head[p]; ptr->next; ptr = ptr->next)
if (ptr->next->key == key) return 1;
Node<KEY, VALUE> *node = new Node<KEY, VALUE>(key, value);
node->next = head[p]->next;
head[p]->next = node;
++n;
return 0;
}
template <typename KEY, typename VALUE>
Node<KEY, VALUE> *HashMap<KEY, VALUE>::find(KEY key) {
unsigned long long hv = HashValue(key);
int p = hv % kHASHSIZE;
for (Node<KEY, VALUE> *ptr = head[p]; ptr->next; ptr = ptr->next)
if (ptr->next->key == key) return ptr->next;
return NULL;
}
template <typename KEY, typename VALUE>
void HashMap<KEY, VALUE>::clear() {
n = 0;
for (int i = 0; i < kHASHSIZE; i++) {
if (head[i]->next) delete head[i]->next;
}
}
template <typename KEY, typename VALUE>
int HashMap<KEY, VALUE>::erase(KEY key) {
unsigned long long hv = HashValue(key);
int p = hv % kHASHSIZE;
for (Node<KEY, VALUE> *ptr = head[p]; ptr->next; ptr = ptr->next)
if (ptr->next->key == key) {
Node<KEY, VALUE> *temp = ptr->next;
ptr->next = temp->next;
temp->next = NULL;
delete temp;
--n;
return 0;
}
return 1;
}
template<typename KEY, typename VALUE>
unsigned long long HashMap<KEY, VALUE>::HashValue(KEY key) {
return (unsigned long long)(key);
}
template<typename KEY, typename VALUE>
VALUE &HashMap<KEY, VALUE>::operator [] (const KEY &index) {
Node<KEY, VALUE> *ptr = find(index);
if (ptr != NULL) return ptr->value;
VALUE *value = new VALUE();
insert(index, *value);
ptr = find(index);
return ptr->value;
}