CluE  1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
carterwegman.h
Go to the documentation of this file.
1 #ifndef CARTERWEGMAN_H
2 #define CARTERWEGMAN_H
3 
4 #include <limits>
5 
6 #include "hashfunction.h"
7 #include "primegenerator.h"
8 #include "../misc/randomness.h"
9 
10 namespace CluE
11 {
12 
16 template<typename U, typename H> class CarterWegman : public HashFunction<U,H>
17 {
18 public:
19  CarterWegman(U universeSize, H hashingSpaceSize = std::numeric_limits<H>::max());
20 
21  virtual H operator()(U const & element) const;
22 
26  void setOffset(H offset);
27 
31  H getOffset() const;
32 
33 private:
34  unsigned long lValue;
35  unsigned long mValue;
36  unsigned long nValue;
37  unsigned long long pPrime;
39  H offset;
40 };
41 
42 template<typename U, typename H> CarterWegman<U,H>::CarterWegman(U universeSize, H hashingSpaceSize) :
43  hashingSpaceSize(hashingSpaceSize),
44  offset(0)
45 {
47  std::uniform_int_distribution<unsigned long long> dis(0, hashingSpaceSize-1);
48  PrimeGenerator pg;
49 
50  lValue = dis(gen);
51  mValue = dis(gen);
52  nValue = dis(gen);
53  pPrime = pg.getPrime(hashingSpaceSize, hashingSpaceSize*2, 0.00001);
54 }
55 
56 template<typename U, typename H> H CarterWegman<U,H>::operator()(U const & element) const
57 {
58  return H(((lValue * element * element + mValue * element + nValue) % pPrime) % hashingSpaceSize) + offset;
59 }
60 
61 template<typename U, typename H> void CarterWegman<U,H>::setOffset(H offset)
62 {
63  this->offset = offset;
64 }
65 
66 template<typename U, typename H> H CarterWegman<U,H>::getOffset() const
67 {
68  return offset;
69 }
70 
71 }
72 
73 #endif
Encapsulates an STL random generator.
unsigned long long pPrime
Definition: carterwegman.h:37
unsigned long nValue
Definition: carterwegman.h:36
Base class template for any hash function mapping an element from universe U to hashing space H...
Definition: hashfunction.h:10
CarterWegman(U universeSize, H hashingSpaceSize=std::numeric_limits< H >::max())
Definition: carterwegman.h:42
unsigned long lValue
Definition: carterwegman.h:34
unsigned long mValue
Definition: carterwegman.h:35
Universal hashing.
Definition: carterwegman.h:16
static RandomGenerator getRandomGenerator()
Definition: randomness.h:23
unsigned long long getPrime(unsigned long long lowerBound, unsigned long long upperBound, double errorProbability)
Returns a number [lowerBound, upperBound] which is prime with probablity 1-errorProbability.
void setOffset(H offset)
Sets the hash value offset (default is 0)
Definition: carterwegman.h:61
virtual H operator()(U const &element) const
Definition: carterwegman.h:56
H getOffset() const
Gets the hash value offset (default is 0)
Definition: carterwegman.h:66
Generates numbers which are (most likely) prime numbers.