Как адаптировать неупорядоченный контейнер STL для хранения только значений пары ключ-значение?

Question

Новый стандарт C ++ 11 содержит неупорядоченные контейнеры. В частности, std::unordered_map<Key, Value> сохраняет std::pair<Key, Value> в местоположении на основе std::hash<Key> (хэш-функция по умолчанию). Аналогично, std::unordered_set<Key> хранит ключ в местоположении на основе std::hash<Key>.

Мой вопрос: как можно хранить только Значение пары ключ-значение в месте на основе std::hash<Key>? Это было бы полезно, если использовать совершенную хеш-функцию , то есть ту, для которой разные ключи отображаются на разные хеш-индексы (поэтому разрешение коллизий никогда не требуется).

unordered_set использует только ключ, а unordered_map использует и ключ, и значение, поэтому неупорядоченные контейнеры STL в новом стандарте C ++ 11, по-видимому, не допускают такой настройки. Что было бы хорошим способом получить такую ​​структуру данных из существующих контейнеров STL?

В более общем смысле, как можно хранить std::pair<T, Value> в местоположении на основе std::hash<Key>, где T - это тип, представляющий подпись Ключа? Например. если Key является большой структурой данных, я хотел бы вычислить 64-битный хеш-ключ и разделить его на две 32-битные части: старшие 32 бита вместе со значением образуют std::pair<uint32_t, Value>, а нижние 32 бита определяют местоположение где хранится эта пара.

Приложение, где это было бы полезно, например, компьютерные шахматы, где позиция (несколько килобайт в некоторых программах) в качестве типа ключа хэшируется в 64-разрядный ключ, из которого только верхние 32 бита и некоторая информация, связанная с поиском, в качестве типа значения сохраняются как std::pair ( обычно всего 16 байт) в местоположении на основе младших 32 битов хеш-ключа.

Answer 1

Мой вопрос таков: как можно хранить только пару «Значение ключа-значения» в месте на основе std :: hash?Это было бы полезно, если используется идеальная хеш-функция, то есть та, для которой разные ключи отображаются на разные хеш-индексы (поэтому разрешение коллизий никогда не требуется).

Идеальной хеш-функции недостаточно.Вы не только должны гарантировать отсутствие коллизий хешей, вы также должны убедиться в отсутствии коллизий bucket .Черт возьми, вам даже нужно убедиться, что количество сегментов никогда никогда не изменится, поскольку ваша структура данных не может обнаружить хэш ключа.

Answer 2

Возможно, я все понял неправильно, но почему бы не просто std::unordered_map<uint32_t, std::pair<uint32_t, Value>> с некоторыми полезными вспомогательными функциями для вставки и извлечения?

// demonstration with 32bit 'hash' and 16bit 'lo' and 'hi'
#include <unordered_map>
#include <string>
#include <stdint.h>
#include <iostream>

int main(){
    typedef std::unordered_map<uint16_t, std::pair<uint16_t, std::string>> map_type;
    map_type m;
    std::string key = "hello", value = "world";
    uint32_t hash = std::hash<std::string>()(key);
    uint16_t lo = hash & 0xFFFF, hi = hash >> 16; // make a nice function for this
    m.insert(std::make_pair(lo, std::make_pair(hi, value))); // and this
    auto it = m.find(lo); // and this
    std::cout << "hash: " << hash << '\n'
              << "lo: " << it->first << '\n'
              << "hi: " << it->second.first << '\n'
              << "lo | (hi << 16): " << (it->first | (uint32_t(it->second.first) << 16)) << '\n'
              << "value: " << it->second.second << '\n';
}

Живая демонстрация на Ideone .

Выход:

hash: 1335831723
lo: 11435
hi: 20383
lo | (hi << 16): 1335831723
value: world

Answer 3

Не существует универсального способа выполнения операций с хешем без постоянного доступа к значениям хеша. Например, предположим, что хеш внутренне использует дерево. Чтобы добавить новый узел в хеш, вам нужно сравнить его значение хеша со значением хеша существующих узлов в дереве. Как вы можете это сделать, если вы не сохранили их значения в дереве?

То, что вы просите, вероятно, не невозможно, но ни один из типичных алгоритмов хеширования не может этого сделать. И, похоже, в этом нет никакого смысла, вам нужно хранить что-то , чтобы сделать коллекцию доступной, и трудно понять, как что-то кроме хеша могло бы работать так же хорошо, как и хеш, так как это то, что вы ищете.

Если хеш "слишком большой", используйте хеш хеша. (Конечно, тогда вам придется иметь дело с хэш-коллизиями.)

Answer 4

Реализуйте свою функцию хеширования для типа, который вы хотите использовать в качестве ключа, а затем создайте тип для хранения хеш-значения и специализируйте std :: hash для этого типа, чтобы просто возвращать хеш-значение. Теперь вы можете вычислить хеш, отбросить данные, используемые для вычисления хеша, и вставить значение и его хеш в карту.

Чтобы получить значение, вы каким-то образом воссоздаете ключевые данные, а затем можете заново вычислить значение хеша и затем выполнить поиск на карте этого хеша.

Answer 5

Поскольку хэши C ++ 11 на самом деле имеют тип size_t, вы можете сделать что-то вроде:

template <typename T>
struct with_hash
{
    size_t hash;
    T value;
};

template<> struct std::hash<with_hash>
{
    typedef size_t result_type;
    typedef with_hash argument_type;
    size_t operator()(const with_hash &x)
    {
         return x.hash;
    }
};

template <typename T>
using perfectly_hashed = std::unordered_set< with_hash<T> >;

Здесь и там есть еще немного синтаксического сахара ...