代码之家  ›  专栏  ›  技术社区  ›  lornova

Std::Unordered_映射中的键与哈希

  •  1
  • lornova  · 技术社区  · 6 年前

    我经常需要一个容器,其中散列与任意对象相关联(如果两个不同的对象具有相同的散列,理论上可能发生冲突)。

    在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++中,有一个使用散列的内置容器,并且基于这些散列有一个查找接口吗?

    2 回复  |  直到 6 年前
        1
  •  2
  •   Wizard    6 年前

    最初的 unordered_map 被称为 hash_map 然后,ISO C++委员会明智地重命名它,因为 std::map std::unordered_map 第一个使用二叉树,而第二个使用哈希, 但是 第一个是有序的,而第二个保证恒定的时间复杂性。

    所以事实是 标准:无序地图 在内部使用散列仅仅是一个实现细节:您只需要提供 std::hash 专业化如果 关键 是自定义类型(键通常是自定义类型)。除此之外,您应该忘记这个容器的内部散列。

    尽管有一些评论,但是如果你的密钥是哈希,那么C++ C++ 98的实现绝对没有错。你可以在C++和GT=11中继续使用它,在可能的情况下将它更新和整理到新的语言设施。

        2
  •  2
  •   Yakk - Adam Nevraumont    6 年前

    您有一个映射而不是散列映射;您的密钥是散列这一事实与容器无关。

    唯一显著的特点是你很少关心哈希的顺序,所以无序映射可能是最好的。

    使用旧的解决方案,将地图替换为无序地图,替换 less 操作与 equal 以及一个哈希(可能向下)到64位。例如,经典指针哈希 reinterpret_cast<unit_ptr>( key ) .