1 | #pragma once |
2 | |
3 | #include <cstdint> |
4 | #include <cstddef> |
5 | |
6 | /* |
7 | * Author: Konstantin Oblakov |
8 | * |
9 | * Maps random ui64 x (in fact hash of some string) to n baskets/shards. |
10 | * Output value is id of a basket. 0 <= ConsistentHashing(x, n) < n. |
11 | * Probability of all baskets must be equal. Also, it should be consistent |
12 | * in terms, that with different n_1 < n_2 probability of |
13 | * ConsistentHashing(x, n_1) != ConsistentHashing(x, n_2) must be equal to |
14 | * (n_2 - n_1) / n_2 - the least possible with previous conditions. |
15 | * It requires O(1) memory and cpu to calculate. So, it is faster than classic |
16 | * consistent hashing algos with points on circle. |
17 | */ |
18 | std::size_t ConsistentHashing(std::uint64_t x, std::size_t n); // Works for n <= 32768 |
19 | std::size_t ConsistentHashing(std::uint64_t lo, std::uint64_t hi, std::size_t n); // Works for n <= 2^31 |
20 | |