std::unordered_map / std::unordered_set

std::unordered_map<K, V> и std::unordered_set<K> — ассоциативные контейнеры на основе хэш-таблицы (обычно chaining — раздельные цепочки бакетов), где поиск/вставка/удаление в среднем случае занимают O(1), в отличие от std::map/std::set, реализованных на сбалансированном дереве с O(log n). Элементы не хранятся в каком-либо предсказуемом порядке — порядок обхода зависит от хэш-функции и внутреннего числа бакетов.std::unordered_map<K, V> and std::unordered_set<K> are associative containers backed by a hash table (typically chaining — separate bucket lists), where lookup/insert/erase take O(1) on average, unlike std::map/std::set, which are implemented on a balanced tree with O(log n). Elements aren't stored in any predictable order — iteration order depends on the hash function and the internal bucket count.

std::map<std::string, int> m;
m["b"] = 2; m["a"] = 1;
// обход — всегда по возрастанию ключа: a, b// iteration — always in ascending key order: a, b

std::unordered_map<std::string, int> m;
m["b"] = 2; m["a"] = 1;
// обход — в произвольном, непредсказуемом порядке// iteration — in an arbitrary, unpredictable order

До C++11 хэш-таблицы существовали только вне стандарта — как надстройка компиляторов или как часть Boost/TR1:Before C++11, hash tables existed only outside the standard — as compiler extensions or as part of Boost/TR1:

Стандартная реализация — хэш-таблица с раздельными цепочками (separate chaining): массив бакетов, каждый бакет — связный список элементов с одинаковым хэшем по модулю числа бакетов. Вставка вычисляет hash(key) % bucket_count, помещает элемент в соответствующий бакет; при превышении load factor таблица автоматически увеличивает число бакетов и перехэширует все элементы (rehash) — операция O(n), но амортизированная по всем вставкам.The standard implementation is a hash table with separate chaining: an array of buckets, each bucket a linked list of elements sharing the same hash modulo the bucket count. Insertion computes hash(key) % bucket_count and places the element into the corresponding bucket; once the load factor is exceeded, the table automatically grows the bucket count and rehashes all elements (rehash) — an O(n) operation, but amortized across all insertions.

#include <unordered_map>

std::unordered_map<std::string, int> counts;
counts["apple"]++;   // хэш "apple" → бакет → вставка/инкремент, O(1) в среднем// hash "apple" → bucket → insert/increment, O(1) average

// управление внутренним состоянием хэш-таблицы:// managing the hash table's internal state:
counts.reserve(1000);              // заранее выделить бакеты, избежать rehash// pre-allocate buckets, avoid a rehash
std::cout << counts.load_factor(); // элементов / бакетов// elements / buckets
std::cout << counts.bucket_count();

// пользовательский тип ключа требует свою хэш-функцию:// a custom key type requires its own hash function:
struct Point { int x, y; };
struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};
struct PointEq {
    bool operator()(const Point& a, const Point& b) const {
        return a.x == b.x && a.y == b.y;
    }
};
std::unordered_map<Point, int, PointHash, PointEq> byPoint;

Минимальная хэш-таблица только с insert/find, без erase и без итераторов — этого обычно достаточно, чтобы продемонстрировать понимание chaining, load factor и rehash за отведённое время.A minimal hash table with just insert/find, no erase and no iterators — that's usually enough to demonstrate an understanding of chaining, load factor, and rehash within the time given.

hash_map.hpp

template <class K, class V, class Hash = std::hash<K>>
class SimpleHashMap {
    struct Entry { K key; V value; };
    std::vector<std::list<Entry>> buckets_;
    size_t size_ = 0;
    Hash hasher_;

    size_t bucket_index(const K& key) const {
        return hasher_(key) % buckets_.size();
    }

    void rehash_if_needed() {
        if (size_ <= buckets_.size()) return;   // load factor > 1.0// load factor > 1.0
        std::vector<std::list<Entry>> old = std::move(buckets_);
        buckets_.assign(old.size() * 2, {});     // рост в 2 раза — амортизация O(1)// 2x growth — O(1) amortized
        size_ = 0;
        for (auto& bucket : old)
            for (auto& e : bucket)
                insert(e.key, e.value);          // перевставка с новым bucket_index// reinsert with the new bucket_index
    }
public:
    explicit SimpleHashMap(size_t initial_buckets = 16)
        : buckets_(initial_buckets) {}

    void insert(const K& key, const V& value) {
        size_t idx = bucket_index(key);
        for (auto& e : buckets_[idx]) {
            if (e.key == key) { e.value = value; return; }  // обновление// update
        }
        buckets_[idx].push_back({key, value});
        ++size_;
        rehash_if_needed();
    }

    V* find(const K& key) {
        auto& bucket = buckets_[bucket_index(key)];
        for (auto& e : bucket) {
            if (e.key == key) return &e.value;
        }
        return nullptr;   // не найдено// not found
    }
};

Частые дополнительные вопросы: почему рост буферов идёт в 2 раза, а не на фиксированный шаг (та же амортизационная логика, что у std::vector — иначе rehash на каждой вставке даёт O(n) на операцию, а не амортизированный O(1)); что будет при плохой хэш-функции (деградация до одного гигантского бакета — O(n) worst case, см. грабли ниже); и как добавить erase() (удаление элемента из списка бакета — тривиально, в отличие от open addressing, где удаление требует tombstone-меток).Common follow-up questions: why buffers grow by 2x rather than a fixed step (the same amortization logic as std::vector — otherwise a rehash on every insertion gives O(n) per operation instead of amortized O(1)); what happens with a bad hash function (degrades to one giant bucket — O(n) worst case, see gotchas below); and how to add erase() (removing an element from a bucket's list is trivial, unlike open addressing, where deletion requires tombstone markers).

• cppreference — std::unordered_map
• cppreference — std::unordered_set
• WG21 N2456 — Working Draft, Unordered Associative Containers