Hash Set
(ds/hash_table/hash_set.hpp)

View this file on GitHub
Last update: 2026-06-21 04:34:53+09:00
Include: #include "ds/hash_table/hash_set.hpp"

Overview

HashSet is a flat open-addressing hash set. It is intended as a faster and more hack-resistant replacement for std::unordered_set in competitive programming.

Hashes are passed through a salted splitmix64 mixer, which helps avoid adversarial collisions for common integral keys. The table uses linear probing and rebuilds before the load factor reaches about 70%.

Pointers returned by find remain valid until the set is modified.

Template Parameters

T: The key type.
Hash: Hash function. Defaults to std::hash<T>.
KeyEqual: Equality predicate. Defaults to std::equal_to<T>.

Constructors

HashSet() Constructs an empty set. ($O(1)$)
HashSet(std::size_t reserve_count) Constructs an empty set with enough buckets for about reserve_count keys. ($O(1)$)
HashSet(std::initializer_list<T> init) Constructs a set from an initializer list. Duplicate keys are ignored. Expected $O(N)$
HashSet(Iterator first, Iterator last) Constructs a set from a range. Duplicate keys are ignored. Expected $O(N)$

Methods

Method	Description	Complexity
`int size() const`	Returns the number of keys.	$O(1)$
`bool empty() const`	Returns whether the set is empty.	$O(1)$
`std::size_t bucket_count() const`	Returns the number of buckets.	$O(1)$
`double load_factor() const`	Returns `size() / bucket_count()`.	$O(1)$
`void clear()`	Removes all keys.	$O(B)$
`void reserve(std::size_t count)`	Reserves enough buckets for about `count` keys.	Expected $O(N)$
`bool insert(const T& key)`, `bool insert(T&& key)`	Inserts `key`; returns whether a new key was inserted.	Expected $O(1)$
`bool erase(const T& key)`	Removes `key`; returns whether a key was removed.	Expected $O(1)$
`const T* find(const T& key) const`	Returns a pointer to `key`, or `nullptr` if it does not exist.	Expected $O(1)$
`bool contains(const T& key) const`	Returns whether `key` exists.	Expected $O(1)$
`int count(const T& key) const`	Returns `1` if `key` exists, otherwise `0`.	Expected $O(1)$
`std::vector<T> to_vector() const`	Returns all keys in bucket order.	$O(B)$

Example

#include "ds/hash_table/hash_set.hpp"

#include <iostream>

int main() {
    m1une::ds::HashSet<long long> st = {3, 1, 3, 5};

    st.insert(2);
    st.erase(3);

    std::cout << st.contains(5) << "\n";  // 1
    std::cout << st.count(3) << "\n";     // 0
}

Depends on

ds/hash_table/hash_common.hpp

Verified with

verify/ds/hash_table/hash_set.test.cpp

Code

#ifndef M1UNE_HASH_SET_HPP
#define M1UNE_HASH_SET_HPP 1

#include "hash_common.hpp"

#include <algorithm>
#include <cstddef>
#include <functional>
#include <initializer_list>
#include <utility>
#include <vector>

namespace m1une {
namespace ds {

template <typename T, typename Hash = std::hash<T>, typename KeyEqual = std::equal_to<T>>
struct HashSet {
   private:
    static constexpr unsigned char EMPTY = 0;
    static constexpr unsigned char DELETED = 1;
    static constexpr std::size_t npos = static_cast<std::size_t>(-1);

    std::vector<unsigned char> ctrl;
    std::vector<detail::Slot<T>> data;
    std::size_t _size = 0;
    std::size_t _deleted = 0;
    Hash hasher;
    KeyEqual key_equal;

    std::size_t mask() const {
        return ctrl.size() - 1;
    }

    std::size_t make_hash(const T& key) const {
        return detail::mixed_hash(key, hasher);
    }

    static unsigned char fingerprint(std::size_t h) {
        return static_cast<unsigned char>(2 + (h >> (sizeof(std::size_t) * 8 - 7)));
    }

    static bool occupied(unsigned char c) {
        return c >= 2;
    }

    T* value_at(std::size_t i) {
        return data[i].ptr();
    }

    const T* value_at(std::size_t i) const {
        return data[i].ptr();
    }

    void destroy_all() {
        for (std::size_t i = 0; i < ctrl.size(); i++) {
            if (occupied(ctrl[i])) data[i].destroy();
        }
    }

    void reset(std::size_t bucket_count) {
        destroy_all();
        bucket_count = detail::bit_ceil(std::max<std::size_t>(16, bucket_count));
        ctrl.assign(bucket_count, EMPTY);
        data.clear();
        data.resize(bucket_count);
        _size = 0;
        _deleted = 0;
    }

    std::size_t find_index_with_hash(const T& key, std::size_t h) const {
        const unsigned char fp = fingerprint(h);
        std::size_t i = h & mask();
        while (true) {
            const unsigned char c = ctrl[i];
            if (c == EMPTY) return npos;
            if (c == fp && key_equal(*value_at(i), key)) return i;
            i = (i + 1) & mask();
        }
    }

    std::size_t find_index(const T& key) const {
        return find_index_with_hash(key, make_hash(key));
    }

    template <typename U>
    void insert_existing(U&& key, std::size_t h) {
        std::size_t i = h & mask();
        while (occupied(ctrl[i])) i = (i + 1) & mask();
        ctrl[i] = fingerprint(h);
        data[i].construct(std::forward<U>(key));
        _size++;
    }

    void rebuild(std::size_t bucket_count) {
        std::vector<unsigned char> old_ctrl = std::move(ctrl);
        std::vector<detail::Slot<T>> old_data = std::move(data);

        ctrl.clear();
        data.clear();
        bucket_count = detail::bit_ceil(std::max<std::size_t>(16, bucket_count));
        ctrl.assign(bucket_count, EMPTY);
        data.resize(bucket_count);
        _size = 0;
        _deleted = 0;

        for (std::size_t i = 0; i < old_ctrl.size(); i++) {
            if (occupied(old_ctrl[i])) {
                T* value = old_data[i].ptr();
                insert_existing(std::move(*value), make_hash(*value));
                old_data[i].destroy();
            }
        }
    }

    void ensure_for_insert() {
        const std::size_t used = _size + _deleted;
        if ((used + 1) * 10 >= ctrl.size() * 7) {
            rebuild(ctrl.size() * 2);
        } else if (_deleted > _size && (_size + 1) * 10 < ctrl.size() * 7) {
            rebuild(ctrl.size());
        }
    }

    template <typename U>
    bool insert_impl(U&& key) {
        ensure_for_insert();

        const std::size_t h = make_hash(key);
        const unsigned char fp = fingerprint(h);
        std::size_t first_deleted = npos;
        std::size_t i = h & mask();
        while (true) {
            const unsigned char c = ctrl[i];
            if (occupied(c)) {
                if (c == fp && key_equal(*value_at(i), key)) return false;
            } else if (c == DELETED) {
                if (first_deleted == npos) first_deleted = i;
            } else {
                const std::size_t pos = first_deleted == npos ? i : first_deleted;
                if (first_deleted != npos) _deleted--;
                ctrl[pos] = fp;
                data[pos].construct(std::forward<U>(key));
                _size++;
                return true;
            }
            i = (i + 1) & mask();
        }
    }

   public:
    HashSet() : hasher(Hash()), key_equal(KeyEqual()) {
        reset(16);
    }

    explicit HashSet(std::size_t reserve_count, Hash hash_fn = Hash(), KeyEqual equal_fn = KeyEqual())
        : hasher(std::move(hash_fn)), key_equal(std::move(equal_fn)) {
        reset(detail::bucket_count_for(reserve_count));
    }

    HashSet(std::initializer_list<T> init, Hash hash_fn = Hash(), KeyEqual equal_fn = KeyEqual())
        : HashSet(init.size(), std::move(hash_fn), std::move(equal_fn)) {
        for (const T& x : init) insert(x);
    }

    template <typename Iterator>
    HashSet(Iterator first, Iterator last, Hash hash_fn = Hash(), KeyEqual equal_fn = KeyEqual())
        : HashSet(0, std::move(hash_fn), std::move(equal_fn)) {
        while (first != last) {
            insert(*first);
            ++first;
        }
    }

    HashSet(const HashSet& other) : hasher(other.hasher), key_equal(other.key_equal) {
        ctrl.assign(other.ctrl.size(), EMPTY);
        data.resize(other.data.size());
        for (std::size_t i = 0; i < other.ctrl.size(); i++) {
            ctrl[i] = other.ctrl[i];
            if (occupied(other.ctrl[i])) data[i].construct(*other.value_at(i));
        }
        _size = other._size;
        _deleted = other._deleted;
    }

    HashSet(HashSet&& other) noexcept
        : ctrl(std::move(other.ctrl)),
          data(std::move(other.data)),
          _size(other._size),
          _deleted(other._deleted),
          hasher(std::move(other.hasher)),
          key_equal(std::move(other.key_equal)) {
        other.ctrl.clear();
        other.data.clear();
        other._size = 0;
        other._deleted = 0;
    }

    HashSet& operator=(const HashSet& other) {
        if (this == &other) return *this;
        HashSet copy(other);
        *this = std::move(copy);
        return *this;
    }

    HashSet& operator=(HashSet&& other) noexcept {
        if (this == &other) return *this;
        destroy_all();
        ctrl = std::move(other.ctrl);
        data = std::move(other.data);
        _size = other._size;
        _deleted = other._deleted;
        hasher = std::move(other.hasher);
        key_equal = std::move(other.key_equal);
        other.ctrl.clear();
        other.data.clear();
        other._size = 0;
        other._deleted = 0;
        return *this;
    }

    ~HashSet() {
        destroy_all();
    }

    int size() const {
        return static_cast<int>(_size);
    }

    bool empty() const {
        return _size == 0;
    }

    std::size_t bucket_count() const {
        return ctrl.size();
    }

    double load_factor() const {
        return static_cast<double>(_size) / static_cast<double>(ctrl.size());
    }

    void clear() {
        reset(ctrl.size());
    }

    void reserve(std::size_t count) {
        const std::size_t target = detail::bucket_count_for(count);
        if (target > ctrl.size() || _deleted > 0) rebuild(std::max(target, ctrl.size()));
    }

    bool insert(const T& key) {
        return insert_impl(key);
    }

    bool insert(T&& key) {
        return insert_impl(std::move(key));
    }

    bool erase(const T& key) {
        const std::size_t h = make_hash(key);
        const std::size_t i = find_index_with_hash(key, h);
        if (i == npos) return false;
        data[i].destroy();
        ctrl[i] = DELETED;
        _size--;
        _deleted++;
        return true;
    }

    const T* find(const T& key) const {
        const std::size_t i = find_index(key);
        return i == npos ? nullptr : value_at(i);
    }

    bool contains(const T& key) const {
        return find_index(key) != npos;
    }

    int count(const T& key) const {
        return contains(key) ? 1 : 0;
    }

    std::vector<T> to_vector() const {
        std::vector<T> result;
        result.reserve(_size);
        for (std::size_t i = 0; i < ctrl.size(); i++) {
            if (occupied(ctrl[i])) result.push_back(*value_at(i));
        }
        return result;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_HASH_SET_HPP

#line 1 "ds/hash_table/hash_set.hpp"



#line 1 "ds/hash_table/hash_common.hpp"



#include <algorithm>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <new>
#include <type_traits>
#include <utility>

namespace m1une {
namespace ds {
namespace detail {

inline std::uint64_t splitmix64(std::uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

template <typename Key, typename Hash>
std::size_t mixed_hash(const Key& key, const Hash& hash) {
    static const std::uint64_t fixed_random =
        std::chrono::steady_clock::now().time_since_epoch().count();
    return static_cast<std::size_t>(splitmix64(static_cast<std::uint64_t>(hash(key)) + fixed_random));
}

inline std::size_t bit_ceil(std::size_t n) {
    std::size_t result = 1;
    while (result < n) result <<= 1;
    return result;
}

inline std::size_t bucket_count_for(std::size_t expected_size) {
    return bit_ceil(std::max<std::size_t>(16, expected_size * 10 / 7 + 1));
}

template <typename T>
struct Slot {
    alignas(T) unsigned char storage[sizeof(T)];

    T* ptr() {
        return std::launder(reinterpret_cast<T*>(storage));
    }

    const T* ptr() const {
        return std::launder(reinterpret_cast<const T*>(storage));
    }

    template <typename... Args>
    void construct(Args&&... args) {
        ::new (static_cast<void*>(storage)) T(std::forward<Args>(args)...);
    }

    void destroy() {
        if constexpr (!std::is_trivially_destructible_v<T>) {
            ptr()->~T();
        }
    }
};

}  // namespace detail
}  // namespace ds
}  // namespace m1une


#line 5 "ds/hash_table/hash_set.hpp"

#line 8 "ds/hash_table/hash_set.hpp"
#include <functional>
#include <initializer_list>
#line 11 "ds/hash_table/hash_set.hpp"
#include <vector>

namespace m1une {
namespace ds {

template <typename T, typename Hash = std::hash<T>, typename KeyEqual = std::equal_to<T>>
struct HashSet {
   private:
    static constexpr unsigned char EMPTY = 0;
    static constexpr unsigned char DELETED = 1;
    static constexpr std::size_t npos = static_cast<std::size_t>(-1);

    std::vector<unsigned char> ctrl;
    std::vector<detail::Slot<T>> data;
    std::size_t _size = 0;
    std::size_t _deleted = 0;
    Hash hasher;
    KeyEqual key_equal;

    std::size_t mask() const {
        return ctrl.size() - 1;
    }

    std::size_t make_hash(const T& key) const {
        return detail::mixed_hash(key, hasher);
    }

    static unsigned char fingerprint(std::size_t h) {
        return static_cast<unsigned char>(2 + (h >> (sizeof(std::size_t) * 8 - 7)));
    }

    static bool occupied(unsigned char c) {
        return c >= 2;
    }

    T* value_at(std::size_t i) {
        return data[i].ptr();
    }

    const T* value_at(std::size_t i) const {
        return data[i].ptr();
    }

    void destroy_all() {
        for (std::size_t i = 0; i < ctrl.size(); i++) {
            if (occupied(ctrl[i])) data[i].destroy();
        }
    }

    void reset(std::size_t bucket_count) {
        destroy_all();
        bucket_count = detail::bit_ceil(std::max<std::size_t>(16, bucket_count));
        ctrl.assign(bucket_count, EMPTY);
        data.clear();
        data.resize(bucket_count);
        _size = 0;
        _deleted = 0;
    }

    std::size_t find_index_with_hash(const T& key, std::size_t h) const {
        const unsigned char fp = fingerprint(h);
        std::size_t i = h & mask();
        while (true) {
            const unsigned char c = ctrl[i];
            if (c == EMPTY) return npos;
            if (c == fp && key_equal(*value_at(i), key)) return i;
            i = (i + 1) & mask();
        }
    }

    std::size_t find_index(const T& key) const {
        return find_index_with_hash(key, make_hash(key));
    }

    template <typename U>
    void insert_existing(U&& key, std::size_t h) {
        std::size_t i = h & mask();
        while (occupied(ctrl[i])) i = (i + 1) & mask();
        ctrl[i] = fingerprint(h);
        data[i].construct(std::forward<U>(key));
        _size++;
    }

    void rebuild(std::size_t bucket_count) {
        std::vector<unsigned char> old_ctrl = std::move(ctrl);
        std::vector<detail::Slot<T>> old_data = std::move(data);

        ctrl.clear();
        data.clear();
        bucket_count = detail::bit_ceil(std::max<std::size_t>(16, bucket_count));
        ctrl.assign(bucket_count, EMPTY);
        data.resize(bucket_count);
        _size = 0;
        _deleted = 0;

        for (std::size_t i = 0; i < old_ctrl.size(); i++) {
            if (occupied(old_ctrl[i])) {
                T* value = old_data[i].ptr();
                insert_existing(std::move(*value), make_hash(*value));
                old_data[i].destroy();
            }
        }
    }

    void ensure_for_insert() {
        const std::size_t used = _size + _deleted;
        if ((used + 1) * 10 >= ctrl.size() * 7) {
            rebuild(ctrl.size() * 2);
        } else if (_deleted > _size && (_size + 1) * 10 < ctrl.size() * 7) {
            rebuild(ctrl.size());
        }
    }

    template <typename U>
    bool insert_impl(U&& key) {
        ensure_for_insert();

        const std::size_t h = make_hash(key);
        const unsigned char fp = fingerprint(h);
        std::size_t first_deleted = npos;
        std::size_t i = h & mask();
        while (true) {
            const unsigned char c = ctrl[i];
            if (occupied(c)) {
                if (c == fp && key_equal(*value_at(i), key)) return false;
            } else if (c == DELETED) {
                if (first_deleted == npos) first_deleted = i;
            } else {
                const std::size_t pos = first_deleted == npos ? i : first_deleted;
                if (first_deleted != npos) _deleted--;
                ctrl[pos] = fp;
                data[pos].construct(std::forward<U>(key));
                _size++;
                return true;
            }
            i = (i + 1) & mask();
        }
    }

   public:
    HashSet() : hasher(Hash()), key_equal(KeyEqual()) {
        reset(16);
    }

    explicit HashSet(std::size_t reserve_count, Hash hash_fn = Hash(), KeyEqual equal_fn = KeyEqual())
        : hasher(std::move(hash_fn)), key_equal(std::move(equal_fn)) {
        reset(detail::bucket_count_for(reserve_count));
    }

    HashSet(std::initializer_list<T> init, Hash hash_fn = Hash(), KeyEqual equal_fn = KeyEqual())
        : HashSet(init.size(), std::move(hash_fn), std::move(equal_fn)) {
        for (const T& x : init) insert(x);
    }

    template <typename Iterator>
    HashSet(Iterator first, Iterator last, Hash hash_fn = Hash(), KeyEqual equal_fn = KeyEqual())
        : HashSet(0, std::move(hash_fn), std::move(equal_fn)) {
        while (first != last) {
            insert(*first);
            ++first;
        }
    }

    HashSet(const HashSet& other) : hasher(other.hasher), key_equal(other.key_equal) {
        ctrl.assign(other.ctrl.size(), EMPTY);
        data.resize(other.data.size());
        for (std::size_t i = 0; i < other.ctrl.size(); i++) {
            ctrl[i] = other.ctrl[i];
            if (occupied(other.ctrl[i])) data[i].construct(*other.value_at(i));
        }
        _size = other._size;
        _deleted = other._deleted;
    }

    HashSet(HashSet&& other) noexcept
        : ctrl(std::move(other.ctrl)),
          data(std::move(other.data)),
          _size(other._size),
          _deleted(other._deleted),
          hasher(std::move(other.hasher)),
          key_equal(std::move(other.key_equal)) {
        other.ctrl.clear();
        other.data.clear();
        other._size = 0;
        other._deleted = 0;
    }

    HashSet& operator=(const HashSet& other) {
        if (this == &other) return *this;
        HashSet copy(other);
        *this = std::move(copy);
        return *this;
    }

    HashSet& operator=(HashSet&& other) noexcept {
        if (this == &other) return *this;
        destroy_all();
        ctrl = std::move(other.ctrl);
        data = std::move(other.data);
        _size = other._size;
        _deleted = other._deleted;
        hasher = std::move(other.hasher);
        key_equal = std::move(other.key_equal);
        other.ctrl.clear();
        other.data.clear();
        other._size = 0;
        other._deleted = 0;
        return *this;
    }

    ~HashSet() {
        destroy_all();
    }

    int size() const {
        return static_cast<int>(_size);
    }

    bool empty() const {
        return _size == 0;
    }

    std::size_t bucket_count() const {
        return ctrl.size();
    }

    double load_factor() const {
        return static_cast<double>(_size) / static_cast<double>(ctrl.size());
    }

    void clear() {
        reset(ctrl.size());
    }

    void reserve(std::size_t count) {
        const std::size_t target = detail::bucket_count_for(count);
        if (target > ctrl.size() || _deleted > 0) rebuild(std::max(target, ctrl.size()));
    }

    bool insert(const T& key) {
        return insert_impl(key);
    }

    bool insert(T&& key) {
        return insert_impl(std::move(key));
    }

    bool erase(const T& key) {
        const std::size_t h = make_hash(key);
        const std::size_t i = find_index_with_hash(key, h);
        if (i == npos) return false;
        data[i].destroy();
        ctrl[i] = DELETED;
        _size--;
        _deleted++;
        return true;
    }

    const T* find(const T& key) const {
        const std::size_t i = find_index(key);
        return i == npos ? nullptr : value_at(i);
    }

    bool contains(const T& key) const {
        return find_index(key) != npos;
    }

    int count(const T& key) const {
        return contains(key) ? 1 : 0;
    }

    std::vector<T> to_vector() const {
        std::vector<T> result;
        result.reserve(_size);
        for (std::size_t i = 0; i < ctrl.size(); i++) {
            if (occupied(ctrl[i])) result.push_back(*value_at(i));
        }
        return result;
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Hash Set
(ds/hash_table/hash_set.hpp)

Overview

Template Parameters

Constructors

Methods

Example

Depends on

Verified with

Code

Hash Set (ds/hash_table/hash_set.hpp)

Overview

Template Parameters

Constructors

Methods

Example

Depends on

Verified with

Code

Hash Set
(ds/hash_table/hash_set.hpp)