ключ против хэша в std :: unordered_map

Question

Мне часто нужен контейнер, в котором хэш связан с произвольным объектом (теоретически возможны коллизии, если два разных объекта имеют одинаковый хэш).

В C ++ 98 я бы использовал template<class Key, class T> class std::map, используя Key в качестве хеша, вычисленного на T:

struct object;
typedef std::string object_hash;

object_hash compute_hash(const object& obj);

std::map<object_hash, object> hash_map;

object_hash insert_or_assign(const object& obj)
{
    object_hash hash = compute_hash(obj);
    hash_map[hash] = obj;
    return hash;
}

std::pair<bool, object> get_at(const object_hash& hash)
{
    std::map<object_hash, object>::iterator iter = hash_map.find(hash);
    if( iter == hash_map.end() )
        return std::pair<bool, object>(false, object());
    else
        return std::pair<bool, object>(true, iter->second);
}

Но начиная с C ++ 11 мы хэшировали контейнеры, поэтому я ожидал что-то вроде:

template<class T, class Key = std::hash<T>> class std::hashed_map

с требованием предоставить пользовательский std::hash для типа T, но вместо этого у нас есть

template<class Key, class T, class Hash = std::hash<Key>> class unordered_map

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

Похоже на то, что я ожидал:

template<class Key, class Hash = std::hash<Key>> class unordered_set

но нет функций поиска на основе хэша.

В современном C ++ есть встроенный контейнер, который использует хэши и имеет интерфейсы поиска на основе этих хэшей?

Answer 1

Первоначально unordered_map назывался hash_map, затем комитет ISO C ++ мудро переименовал его, поскольку важное различие между std::map и std::unordered_map состоит в , а не в том, что первый использует двоичные деревья, в то время как последний использует хеши, , но , что первое упорядочено, а второе гарантирует сложность с постоянным временем.

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

Несмотря на некоторые комментарии, если ваш ключ - хеш, то в вашей реализации C ++ 98 нет ничего плохого. Вы можете продолжать использовать его в C ++> = 11, обновляя и по возможности добавляя его к новым языковым возможностям.

Answer 2

У вас есть карта, а не хэш-карта; тот факт, что ваш ключ является хешем, не имеет отношения к контейнеру.

Единственная существенная особенность заключается в том, что вы редко заботитесь о порядке хэшей; так что неупорядоченная карта, вероятно, лучше.

Возьмите старое решение, замените карту неупорядоченной картой, замените операцию less на equal и хэш (возможно, вниз) до 64 бит. Например, классический хэш указателя просто reinterpret_cast<unit_ptr>( key ).