blob: ee3b9b5e8bca7e61c2b16a711be308f675732885 (
plain) (
blame)
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
|
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include<iostream>
const int N = 10;
template<typename K>
struct List {
std::string key;
K data;
List* next;
List(std::string key, K data) {
this->key = key;
this->data = data;
next = nullptr;
}
};
template<typename K>
class HashTable {
public:
HashTable();
HashTable(const HashTable&) = delete;
HashTable& operator=(const HashTable&) = delete;
~HashTable();
void Put(std::string key, K data); //add element
K Get(std::string key); //search for element
void Remove(std::string key); //remove element
private:
List<K>** hashTable;
unsigned HashFunction(std::string key);
List<K>* CheckKeyUniqueness(std::string key, int index);
};
#endif // !HASHTABLE_H
template<typename K>
HashTable<K>::HashTable() {
hashTable = new List<K>*[N];
for (int i = 0; i < N; i++)
hashTable[i] = nullptr;
}
template<typename K>
HashTable<K>::~HashTable() {
for (int i = 0; i < N; i++) {
List<K>* current = hashTable[i];
while (current != nullptr) {
List<K>* next = current->next;
delete current;
current = next;
}
}
delete hashTable;
}
template<typename K>
void HashTable<K>::Put(std::string key, K data) {
unsigned result = HashFunction(key);
if (CheckKeyUniqueness(key, result) != nullptr)
return;
List<K>* newList = new List<K>(key, data);
newList->next = hashTable[result];
hashTable[result] = newList;
}
template<typename K>
K HashTable<K>::Get(std::string key) {
unsigned result = HashFunction(key);
List<K>* iter = hashTable[result];
while (iter->key != key)
iter = iter->next;
if (iter != nullptr)
return iter->data;
else
throw std::logic_error("Can't find this element.\n");
}
template<typename K>
void HashTable<K>::Remove(std::string key) {
unsigned result = HashFunction(key);
List<K>* iter = hashTable[result];
List<K>* prev = iter;
if (iter == hashTable[result] && iter->key == key) {
hashTable[result] = iter->next;
delete iter;
return;
}
while (iter->key != key) {
prev = iter;
iter = iter->next;
}
prev->next = iter->next;
delete iter;
}
template<typename K>
unsigned HashTable<K>::HashFunction(std::string key) {
int keyLength = key.length();
int result = keyLength;
for (int i = 0; i < keyLength; i++)
result = (result << 4) ^ (result >> 8) ^ (key[i]);
return result % N;
}
template<typename K>
List<K>* HashTable<K>::CheckKeyUniqueness(std::string key, int index) {
List<K>* iter = hashTable[index];
while (iter != nullptr) {
if (iter->key == key)
return iter;
iter = iter->next;
}
return nullptr;
}
|
