-
Notifications
You must be signed in to change notification settings - Fork 2
/
HashMap.h
135 lines (113 loc) · 2.75 KB
/
HashMap.h
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
#ifndef HASHMAP_H
#define HASHMAP_H
#include "HashNode.h"
#include <QString>
template <class T>
class HashMap
{
public:
//Constructor / Destructor
HashMap();
~HashMap();
void put(QString,T);
HashNode<T>* get(QString);
void remove(QString);
QString printHtml();
private:
HashNode<T> **table;
unsigned long hashFunc(QString);
};
template <class T>
HashMap<T>::HashMap(){
table = new HashNode<T>*[2000]();
}
template <class T>
HashMap<T>::~HashMap(){
for (int i = 0; i < 2000; ++i) {
HashNode<T> *entry = table[i];
while (entry != NULL) {
HashNode<T> *prev = entry;
entry = entry->next;
delete prev;
}
table[i] = NULL;
}
// destroy the hash table
delete [] table;
}
template <class T>
unsigned long HashMap<T>::hashFunc(QString key){
return qHash(key) % 1999 + 1;
}
template <class T>
void HashMap<T>::put(QString key, T value) {
unsigned long hashValue = hashFunc(key);
HashNode<T> *prev = NULL;
HashNode<T> *entry = table[hashValue];
while (entry != NULL && entry->key != key) {
prev = entry;
entry = entry->next;
}
if (entry == NULL) {
entry = new HashNode<T>(key, value);
if (prev == NULL) {
// insert as first
table[hashValue] = entry;
} else {
prev->next = entry;
}
} else {
// just update the value
entry->data = value;
}
}
template <class T>
void HashMap<T>::remove(QString key) {
unsigned long hashValue = hashFunc(key);
HashNode<T> *prev = NULL;
HashNode<T> *entry = table[hashValue];
while (entry != NULL && entry->key != key) {
prev = entry;
entry = entry->next;
}
if (entry == NULL) {
// key not found
return;
}
else {
if (prev == NULL) {
// remove first bucket of the list
table[hashValue] = entry->next;
} else {
prev->next = entry->next;
}
delete entry;
}
}
template <class T>
HashNode<T>* HashMap<T>::get(QString key){
unsigned long hashValue = hashFunc(key);
HashNode<T> *entry = table[hashValue];
while (entry != NULL) {
if (entry->key == key) {
return entry;
}
entry = entry->next;
}
return NULL;
}
template <class T>
QString HashMap<T>::printHtml()
{
QString html = "<table>";
for(int i=0;i<2000;i++){
HashNode<T>* entry = table[i];
while(entry != NULL){
html += "<tr><td><font color=\"darkkhaki\">" + entry->key + "</font></td><td> -> </td><td>" + entry->data + "</td></tr>";
entry = entry->next;
}
}
html += "</table>";
return html;
}
#endif // HASHMAP_H