pragma once include List cpp template typename T1 typename T2 struct P

 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
#pragma once
#include "List.cpp"
template <typename T1, typename T2>
struct Pair_t {
T1 first;
T2 second;
};
template <typename key_t, typename val_t, unsigned long (*hash)(key_t), int (*cmp)(key_t, key_t), unsigned long max_size>
class HashTable {
public:
List<Pair_t<key_t, val_t>>* table = nullptr;
HashTable(){
table = new List<Pair_t<key_t, val_t>>[max_size]();
}
void insert(key_t key, val_t val){
unsigned long h = hash(key) % max_size;
Node<Pair_t<key_t, val_t>>* new_node = new Node<Pair_t<key_t, val_t>>(Pair_t<key_t, val_t>({key, val}));
table[h].push_back(new_node);
}
Node<Pair_t<key_t, val_t>>* find(key_t key){
unsigned long h = hash(key) % max_size;
Node<Pair_t<key_t, val_t>>* cur = table[h].head_;
while (cur != nullptr){
if (cmp(key, cur->val.first) == 0){
return cur;
}
cur = cur->next_;
}
return cur;
}
~HashTable(){
delete [] table;
}
};
const unsigned long MAX_NUM_LINES = 364245;
const unsigned long MAX_NUM_CHARS = 32 * MAX_NUM_LINES;