-
Notifications
You must be signed in to change notification settings - Fork 203
/
hash_manager.h
74 lines (55 loc) · 1.36 KB
/
hash_manager.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
#ifndef CONFLUO_CONTAINER_SKETCH_HASH_MANAGER_H_
#define CONFLUO_CONTAINER_SKETCH_HASH_MANAGER_H_
#include <vector>
#include "rand_utils.h"
namespace confluo {
namespace sketch {
/**
* Pairwise-independent hash
*/
class pairwise_indep_hash {
public:
static const size_t PRIME;
pairwise_indep_hash();
pairwise_indep_hash(size_t a, size_t b);
template<typename T>
size_t apply(T elem) const {
static std::hash<T> hash;
return (a_ * hash(elem) + b_) % PRIME;
}
template<typename T>
typename std::enable_if<!std::is_unsigned<T>::value, bool>::type apply(T elem) {
return (a_ * elem + b_) % PRIME;
}
static pairwise_indep_hash generate_random();
private:
size_t a_, b_;
};
class hash_manager {
public:
/**
* Constructor.
* @param num_hashes number of hashes
*/
explicit hash_manager(size_t num_hashes = 0);
/**
* Guarantee enough hashes are intialized.
* @param num_hashes number of hashes
*/
void guarantee_initialized(size_t num_hashes);
/**
* Hash element.
* @param hash_id id of hash to use
* @param elem element to hash
* @return hashed value
*/
template<typename T>
size_t hash(size_t hash_id, T elem) const {
return hashes_[hash_id].template apply<T>(elem);
}
private:
std::vector<pairwise_indep_hash> hashes_;
};
}
}
#endif /* CONFLUO_CONTAINER_SKETCH_HASH_MANAGER_H_ */