std :: unordered_map如果已知输入大小，如何优化批量插入

Question

[如果我知道要在std::unordered_map中插入大量数据（大约一百万个条目），我是否可以做一些事来提高性能？ （就像std::vector::reserve可以保留足够的内存空间，以避免在我大致知道批量插入之前的数据大小时避免重新分配）

更具体地说，哈希图中的键是具有自定义哈希功能的2D平面中的坐标，如下所示

using CellIndex = std::pair<int32_t, int32_t>;

struct IdxHash {
  std::size_t operator()(const std::pair<int32_t, int32_t> &idx) const { return ((size_t)idx.second << 31) ^ idx.first; }
};

std::unordered_map<CellIndex, double, IdxHash> my_map;

// bluk insert into my_map
...

Answer 1

std::unordered_map通常实现为具有链接列表的链式哈希表。因此，插入std::unordered_map的平均时间是恒定的，在最坏的情况下，插入容器的时间是线性的。这种最坏的插入情况对应于哈希表元素必须为[[rehashed的情况，因为表中的当前存储桶数量不足以满足load factor，因此需要重新分配数组需要水桶。

记住这一点，如果您事先知道要插入std::unordered_map的元素数，则应考虑std::unordered_map::reserve()，以防止在插入时发生重新哈希。这样，您将避免存储桶阵列重新分配和重新哈希的发生。

std::unordered_map::reserve()

与std::unordered_map::insert() with hint一样，std::unordered_map::insert()成员函数有些重载，即所谓的

hint

：std::map

此提示迭代器可用于提供一些其他信息，这些信息可用于加快插入速度。但是，insert()中这些成员函数的存在只是出于接口兼容性的原因，以使其接口更适合于通用编程。因此，它们不会缩短插入时间。
关于散列函数
您的散列函数的完美程度与插入时间无关紧要，仅取决于它计算密钥散列的速度。但是，当通过键在哈希表中查找元素时，它变得很重要。

Answer 2

insert()为iterator insert(const_iterator hint, const value_type& value); 个元素准备无序容器。相比之下，std::unordered_map为reserve(x)个元素准备无序容器。

同样关于您的哈希函数，如果您希望它返回一对坐标的唯一值，那么它应该返回x。 rehash(x)将为x/max_load_factor()和((size_t)idx.second << 32) ^ idx.first返回相同的值。