hash set

ソースコード

  1#include <vector>
  2#include <random>
  3#include <iostream>
  4#include <cassert>
  5
  6using namespace std;
  7
  8// HashSet
  9namespace titan23 {
 10
 11    class HashSet {
 12      private:
 13        using u64 = unsigned long long;
 14        static constexpr const u64 K = 0x517cc1b727220a95;
 15        static constexpr const int M = 2;
 16        vector<u64> exist;
 17        vector<u64> keys;
 18        int msk, xor_;
 19        int size;
 20
 21        constexpr int hash(const u64 &key) const {
 22            return (((((key>>32)&msk) ^ (key&msk) ^ xor_)) * (HashSet::K & msk)) & msk;
 23        }
 24
 25        pair<int, bool> get_pos(const u64 &key) const {
 26            int h = hash(key);
 27            while (true) {
 28                if (!(exist[h>>6]>>(h&63)&1)) return {h, false};
 29                if (keys[h] == key) return {h, true};
 30                h = (h + 1) & msk;
 31            }
 32        }
 33
 34        int bit_length(const int x) const {
 35            if (x == 0) return 0;
 36            return 32 - __builtin_clz(x);
 37        }
 38
 39        void rebuild() {
 40            vector<u64> old_exist = exist;
 41            vector<u64> old_keys = keys;
 42            exist.resize(HashSet::M*old_exist.size()+1);
 43            fill(exist.begin(), exist.end(), 0);
 44            keys.resize(HashSet::M*old_keys.size());
 45            size = 0;
 46            msk = (1<<bit_length(keys.size()-1))-1;
 47            random_device rd;
 48            mt19937 gen(rd());
 49            uniform_int_distribution<int> dis(0, msk);
 50            xor_ = dis(gen);
 51            for (int i = 0; i < (int)old_keys.size(); ++i) {
 52                if (old_exist[i>>6]>>(i&63)&1) {
 53                    insert(old_keys[i]);
 54                }
 55            }
 56        }
 57
 58      public:
 59        HashSet() : exist(1, 0), keys(1), msk(0), xor_(0), size(0) {}
 60
 61        HashSet(const int n) {
 62            int s = 1<<bit_length(n);
 63            s *= HashSet::M;
 64            assert(s > 0);
 65            exist.resize((s>>6)+1, 0);
 66            keys.resize(s);
 67            msk = (1<<bit_length(keys.size()-1))-1;
 68            random_device rd;
 69            mt19937 gen(rd());
 70            uniform_int_distribution<int> dis(0, msk);
 71            xor_ = dis(gen);
 72            size = 0;
 73        }
 74
 75        bool contains(const u64 key) const {
 76            return get_pos(key).second;
 77        }
 78
 79        void insert(const u64 key) {
 80            const auto [pos, is_exist] = get_pos(key);
 81            if (is_exist) return;
 82            exist[pos>>6] |= 1ull<<(pos&63);
 83            keys[pos] = key;
 84            ++size;
 85            if (HashSet::M*size > keys.size()) rebuild();
 86        }
 87
 88        //! keyがすでにあればtrue, なければ挿入してfalse / `O(1)`
 89        bool contains_insert(const u64 key) {
 90            const auto [pos, is_exist] = get_pos(key);
 91            if (is_exist) return true;
 92            exist[pos>>6] |= 1ull<<(pos&63);
 93            keys[pos] = key;
 94            ++size;
 95            if (HashSet::M*size > keys.size()) rebuild();
 96            return false;
 97        }
 98
 99        //! 全ての要素を削除する / `O(n/w)`
100        void clear() {
101            this->size = 0;
102            fill(exist.begin(), exist.end(), 0);
103        }
104
105        int len() const {
106            return size;
107        }
108    };
109} // namespaced titan23

仕様

Warning

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