哈希和访问

Question

我想对我的对象使用哈希存储。这真的比 std::map 更快吗？我的意思是寻找。据我所知，boost过程进行了大量的优化。

而且我不确定我的代码是否正确。在搜索/插入等时它真的使用散列键吗？

using boost::multi_index_container;
using namespace boost::multi_index;

struct Object
{
  std::string name;

  Object(std::string name_): name(name_) {}
};

typedef multi_index_container<
  Object,
  indexed_by<
    hashed_unique<
      BOOST_MULTI_INDEX_MEMBER(Object, std::string, name)
    >
  >
> ObjectSet;

ObjectSet objects;
objects.insert(Object("test1"));
objects.insert(Object("test2"));
objects.insert(Object("test3"));

// And testing:
objects.find("test2");

Answer 1

当您只有一个键时，为什么要使用 Boost 多索引容器？如果您不打算很快添加更多键，则应该使用 std::unordered_map 或 std::map。

至于哈希表与树：

例如，unordered_map 的 GCC 实现永远不会收缩其表，因此，如果您添加大量元素，然后删除其中大部分元素，那么您留下的数据局部性非常糟糕（因此数据局部性很差）缓存性能）。从算法上讲，哈希表可能很有吸引力，但在实际运行的系统中，它们的性能可能比树差，尤其是当元素数量为数百或更少时。

Answer 2

除了最极端的退化情况之外，在任何情况下，在 unordered_map (hash_map) 中使用散列键进行精确匹配查找都比使用 std::map 的底层红黑树更快。

是的，您的代码应该是正确的，假设有一个哈希函数接受 std::string 并返回其内容的哈希值。