cuckoo hash table

ソースコード

  1raise NotImprementedError
  2
  3#pragma GCC target("avx2")
  4#pragma GCC optimize("O3")
  5#pragma GCC optimize("unroll-loops")
  6
  7
  8#include <vector>
  9#include <random>
 10#include <cassert>
 11#include <iostream>
 12using namespace std;
 13
 14class CuckooHashTable {
 15  private:
 16    using u64 = unsigned long long;
 17    int n;
 18    vector<u64> T1, T2;
 19    int msk, xor1, xor2;
 20    int size;
 21    int max_loop;
 22    const u64 NIL = 0;
 23    static constexpr const u64 K1 = 0x517cc1b727220a95;
 24    static constexpr const u64 K2 = 0xbf58476d1ce4e5b9;
 25
 26    void rehash() {
 27        random_device rd;
 28        mt19937 gen(rd());
 29        uniform_int_distribution<int> dis(0, msk);
 30        xor1 = dis(gen);
 31        xor2 = dis(gen);
 32        for (u64 key : T1) {
 33            if (key != NIL) insert(key);
 34        }
 35        for (u64 key : T2) {
 36            if (key != NIL) insert(key);
 37        }
 38    }
 39
 40    int bit_length(const int x) const {
 41        if (x == 0) return 0;
 42        return 32 - __builtin_clz(x);
 43    }
 44
 45    void rebuild() {
 46        vector<u64> old_T1 = T1;
 47        vector<u64> old_T2 = T2;
 48        size = 0;
 49        msk = (1<<bit_length(T1.size()-1))-1;
 50        T1.resize(2*old_T1.size());
 51        T2.resize(2*old_T2.size());
 52        fill(T1.begin(), T1.end(), 0);
 53        fill(T2.begin(), T2.end(), 0);
 54        random_device rd;
 55        mt19937 gen(rd());
 56        uniform_int_distribution<int> dis(0, msk);
 57        xor1 = dis(gen);
 58        xor2 = dis(gen);
 59        max_loop = 3*bit_length(T1.size());
 60        for (u64 key : old_T1) {
 61            if (key != NIL) insert(key);
 62        }
 63        for (u64 key : old_T2) {
 64            if (key != NIL) insert(key);
 65        }
 66    }
 67
 68    int h1(const u64 key) const {
 69        return (((((key>>32)&msk) ^ (key&msk) ^ xor1)) * (CuckooHashTable::K1 & msk)) & msk;
 70    }
 71
 72    int h2(const u64 key) const {
 73        return (((((key>>32)&msk) ^ (key&msk) ^ xor2)) * (CuckooHashTable::K2 & msk)) & msk;
 74    }
 75
 76    void innert_insert(u64 key) {
 77        if (contains(key)) return;
 78        for (int i = 0; i < max_loop; ++i) {
 79            swap(key, T1[h1(key)]);
 80            if (key == NIL) return;
 81            swap(key, T2[h2(key)]);
 82            if (key == NIL) return;
 83        }
 84        rehash();
 85        innert_insert(key);
 86    }
 87
 88  public:
 89    CuckooHashTable() : T1(1, 0), T2(1, 0), msk(0), xor1(0), xor2(0), size(0), max_loop(1) {}
 90
 91    bool contains(const u64 key) const {
 92        return T1[h1(key)] == key || T2[h2(key)] == key;
 93    }
 94
 95    void insert(u64 key) {
 96        assert(key != NIL);
 97        size++;
 98        if (size*2 > T1.size()) rebuild();
 99        innert_insert(key);
100    }
101
102    void clear() {
103        fill(T1.begin(), T1.end(), NIL);
104        fill(T2.begin(), T2.end(), NIL);
105        size = 0;
106    }
107};
108
109#include "titan_cpplib/algorithm/random.cpp"
110using u64 = unsigned long long;
111void solve() {
112    titan23::Random rnd;
113    unordered_set<u64> s;
114    CuckooHashTable h;
115    int q = 1e7;
116    for (int i = 0; i < q; ++i) {
117        u64 v = rnd.rand_u64();
118        s.insert(v);
119        h.insert(v);
120        assert(h.contains(v));
121    }
122}
123
124int main() {
125    ios::sync_with_stdio(false);
126    cin.tie(0);
127    solve();
128    return 0;
129}

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/cuckoo_hash_table.cpp