src/util/hash.hpp

• View this file on GitHub
• Last update: 2021-12-30 20:52:19+09:00
• Include: #include "src/util/hash.hpp"

Depends on

• src/base.hpp
• src/util/random.hpp

Required by

• src/datastructure/hashmap.hpp
• src/datastructure/hashset.hpp
• src/graph/balancedseparator.hpp
• src/graph/treedecomp.hpp

Verified with

• src/hashmap.test.cpp
• src/hashmap_remove.test.cpp
• src/hashset.test.cpp
• src/hashset_hashmap.test.cpp
• src/treedecomp_width2.test.cpp

Code

#pragma once

#include "base.hpp"
#include "util/random.hpp"

// Reference: Lemire, Daniel., and Owen, Kaser. "Strongly Universal String Hashing Is Fast."
template <uint N = 100> struct Hasher {
  private:
    static ull offset;
    static array<ull, N> seed;

    template <uint I = 0>
    struct Encoder {
        ull now = offset;
        Encoder<I + 1> update(uint x) {
            return Encoder<I + 1>{now + x * seed[I]};
        }
        Encoder<I + 1> update(int x) {
            return update(uint(x));
        }
        Encoder<I + 2> update(ull x) {
            return Encoder<I + 2>{now + uint(x) * seed[I] + (x >> 32) * seed[I + 1]};
        }
        Encoder<I + 2> update(ll x) {
            return update(ll(x));
        }
        uint digest() const {
            static_assert(I <= N);
            return uint(now >> 32);
        }
    };

  public:
    static uint hash(uint x) { return Encoder<>{}.update(x).digest(); }
    static uint hash(ull x) { return Encoder<>{}.update(x).digest(); }
    static uint hash(int x) { return hash(uint(x)); }
    static uint hash(ll x) { return hash(ull(x)); }
    template <class T, class U> static uint hash(const pair<T, U>& p) {
        return Encoder<>{}.update(p.first).update(p.second).digest();
    }
};

template <uint N>
ull Hasher<N>::offset = global_runtime_gen().uniform(0ULL, ull(-1));

template <uint N>
array<ull, N> Hasher<N>::seed = []() {
    array<ull, N> seed;
    for (uint i = 0; i < N; i++) {
        seed[i] = global_runtime_gen().uniform(0ULL, ull(-1));
    }
    return seed;
}();

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.10.1/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: base.hpp: line -1: no such header

Back to top page