ModErn Text Analysis
META Enumerates Textual Applications
probing.h
Go to the documentation of this file.
1 
10 #ifndef META_HASHING_PROBING_H_
11 #define META_HASHING_PROBING_H_
12 
13 #include <cstddef>
14 #include <cstdint>
15 
16 #include "meta/config.h"
18 #include "meta/util/likely.h"
19 
20 namespace meta
21 {
22 namespace hashing
23 {
24 namespace probing
25 {
26 
27 class linear
28 {
29  public:
30  linear(std::size_t hash, std::size_t capacity) : hash_{hash}, capacity_{capacity}
31  {
32  hash_ %= capacity_;
33  }
34 
38  std::size_t probe()
39  {
40  return hash_++ % capacity_;
41  }
42 
43  private:
44  std::size_t hash_;
45  std::size_t capacity_;
46 };
47 
49 {
50  public:
51  linear_nomod(std::size_t hash, std::size_t capacity)
52  : hash_{hash}, max_{capacity - 1}
53  {
54  hash_ %= capacity;
55  }
56 
60  std::size_t probe()
61  {
62  hash_++;
63  if (hash_ > max_)
64  hash_ = 0;
65  return hash_;
66  }
67 
68  private:
69  std::size_t hash_;
70  std::size_t max_;
71 };
72 
73 class binary
74 {
75  public:
76  binary(std::size_t hash, std::size_t capacity)
77  : hash_{hash}, step_{0}, capacity_{capacity}
78  {
79  hash_ %= capacity;
80  }
81 
85  std::size_t probe()
86  {
87  // discard hashes that fall off of the table
88  for (; (hash_ ^ step_) >= capacity_; ++step_)
89  ;
90  return hash_ ^ step_++;
91  }
92 
93  private:
94  std::size_t hash_;
95  std::size_t step_;
96  std::size_t capacity_;
97 };
98 
99 template <class T, std::size_t Alignment = 64>
101 {
102  public:
103  using probe_entry = typename hash_traits<T>::probe_entry;
104 
105  static_assert(Alignment > sizeof(probe_entry),
106  "Alignment should be larger than sizeof(T)");
107  const static std::size_t block_size = Alignment / sizeof(probe_entry);
108 
109  binary_hybrid(std::size_t hash, std::size_t capacity)
110  : hash_{hash}, step_{0}, max_{capacity - 1}
111  {
112  hash_ %= capacity;
113 
114  // find the index of the last (potentially) partial block
115  auto last_block_start = capacity & ~(block_size - 1);
116  if (META_UNLIKELY(hash_ >= last_block_start))
117  {
118  step_ = block_size;
119  idx_ = hash_;
120  }
121  else
122  {
123  // idx_ is the index of the start of the next block. If this is off
124  // the table the condition in probe() will fix it.
125  idx_ = (hash_ | (block_size - 1)) + 1;
126  }
127  }
128 
129  std::size_t probe()
130  {
131  if (META_LIKELY(step_ < block_size))
132  {
133  return hash_ ^ step_++;
134  }
135  else
136  {
137  if (META_UNLIKELY(idx_ > max_))
138  idx_ = 0;
139  return idx_++;
140  }
141  }
142 
143  private:
144  std::size_t hash_;
145  std::size_t step_;
146  std::size_t idx_;
147  std::size_t max_;
148 };
149 
150 // http://stackoverflow.com/questions/2348187
151 // /moving-from-linear-probing-to-quadratic-probing-hash-collisons
153 {
154  public:
155  quadratic(std::size_t hash, std::size_t capacity)
156  : hash_{hash}, capacity_{capacity}, step_{0}
157  {
158  hash_ &= (capacity_ - 1);
159  }
160 
165  std::size_t probe()
166  {
167  auto next = (hash_ + (step_ * (step_ + 1)) / 2) & (capacity_ - 1);
168  ++step_;
169  return next;
170  }
171 
172  private:
173  std::size_t hash_;
174  std::size_t capacity_;
175  std::size_t step_;
176 };
177 }
178 }
179 }
180 #endif
Definition: probing.h:152
A generic, randomly seeded hash function.
Definition: hash.h:343
Definition: probing.h:27
std::size_t probe()
Definition: probing.h:60
std::size_t probe()
Definition: probing.h:165
Definition: probing.h:100
The ModErn Text Analysis toolkit is a suite of natural language processing, classification, information retrieval, data mining, and other applications of text processing.
Definition: analyzer.h:25
Definition: probing.h:48
Definition: probing.h:73
std::size_t probe()
Definition: probing.h:38
std::size_t probe()
Definition: probing.h:85