Why does Google sparsehash open-source library has two implementations: a dense hashtable and a sparse one?

我尝试编写代码以将 sparse_hash_map 的类型序列化为文件，但不知何故它不起作用，令人信服地告诉我这个错误消息：

/usr/local/include/sparsehash/sparsetable:1763:13: error: no matching function for call to object of type 'CharPointerToIntSerializer'

似乎 mymap.serialize 方法工作得很好，这是 mymap2.unsiialize 方法失败了，关于下面这段代码中的问题有什么想法吗？

google 的稀疏哈希表如何处理冲突？即，当 2 个元素映射到同一个桶时，它如何决定将新（碰撞）元素放在哪里？我正在阅读稀疏哈希表背后的主要实现思想是什么？但该答案并未涵盖碰撞的想法。

我有一个 uint64_t 到向量的映射。对于大小为 4MB 的字符串输入，与 unordered_map(~4s) 相比，该映射需要非常长的时间（~70s）来构建。同样，对于大小约为 150MB 的字符串输入，120 秒与 2400 秒。

Unordered_map 一般比 google sparse hash 快，但是时间上的差别很大。对于从 int 到 int 的映射，稀疏哈希比无序映射慢约 2 倍。

我不明白这个时差背后的原因。

代码片段：

这是程序上 /usr/bin/time 的结果

<gtest/gtest.h>所有以某种方式包含但<google/dense_hash_map>未能为我构建的测试用例。通常后者是间接包含的，但我可以重现这样的问题：

问题：

所以 sparsehash 包含/usr/include/c++/5/tr1/tuple而 gtest 包含/usr/include/c++/5/tuple并将其放在gtest-port.h 的 tr1 命名空间中：

我可以理解为什么这会导致问题，但到目前为止我不明白为什么这似乎只发生在我的设置中。git clone我定期（然后）安装了 google-sparsehash ./configure && make && sudo make install，我的项目是一个 CMake 项目，它有一个用于 googletest 的 git 子模式并将其构建为依赖项/子文件夹。此设置适用于所有不（间接）包含 sparsehash 标头的测试。

-DGTEST_HAS_TR1_TUPLE=0 -DGTEST_USE_OWN_TR1_TUPLE=0编辑：所以如果我添加为编译器标志，它似乎可以编译。我不知道为什么这是必要的，如果这是正确的做法

本周我一直试图发现一个不寻常的内存行为：当我用一个线程运行我的代码时，我有一个特定的内存占用，但如果我用多个线程运行它，那么内存占用会增加很多，而没有明显的原因。

我知道由于多线程程序的不确定性可能会发生奇怪的事情，因此最好使用一些确定性的方法来调试它。然而，即使在这种非常确定的情况下，我也看不出为什么内存占用会增加。

这是我能够编写的重现问题的最小程序：

测试.cpp

该程序的想法非常简单：

• 使用循环将已知且预定的 1 亿个键序列插入哈希表
• 观看程序每 100 毫秒在控制台上转储它到目前为止插入了多少键，以及将要插入的下一个键是什么
• 等到操作系统杀死程序

因此，目标是验证对于预定义的插入序列，无论有多少线程将数据推送到哈希表中，内存消耗都是相同的，即插入键的数量大致相同（我不介意如果有几个关键的差异，例如由于操作系统决定终止应用程序）。那么差异可能是巨大的。

该insert_data函数使用一个简单的自旋循环来保证插入顺序，即数字 0、128、256 等等……（使用锁/互斥体没有区别）。

我在以下环境中运行该程序：

• 具有 4GB 内存的 Debian 8.3 Linux VM
• 使用swapoff -a没有交换内存
• -O3带有标志的 GCC 4.9.2

这些是上述代码以不同数​​量的THREADS变量运行时的结果：

线程 = 1

线程 = 2

线程 = 4

如您所见，所有三个测试都将特定键标识1717986944为触发哈希表调整大小的键，并且所有这些都发生在同一个插入键 n 处。13421773，这证实了无论运行线程的数量如何，插入总是严格按照相同的顺序发生。

但是，THREADS=1比THREADS=2多插入了 3556052 个键（对应于 434MB），并且比THREADS=4多插入了 6602521 个键（对应于 805MB） 。

谁能解释我为什么即使在如此确定的条件下我也会有如此奇怪的内存消耗？我真的错过了什么吗？

所以，我是 C++ 的菜鸟，我正在尝试使用sparse_hash_map但我无法弄清楚为什么在从文件中读取行时插入到地图中不起作用，但是当我对字符串进行硬编码时它会起作用。

它总是只插入文件的第一行，但在使用硬编码字符串时有效。

/usr/src/test.data

我的代码是用 g++ (Debian 4.9.2-10) 4.9.2 编译的

__cplusplus 199711L

我使用自述文件（./configure、make、make install）中的注释安装了库

我必须实现给定固定长度的代码 Trie。每个代码都是一个整数序列，考虑到某些模式是常见的，我决定实现一个 Trie 来存储所有代码。鉴于它们的字典顺序，我还需要遍历代码，并且我期望使用数百万（可能是数十亿）的代码。

这就是为什么我考虑将这个特定的 Trie 实现为字典，其中每个键都是给定前缀的索引。假设键 0 有一个他的前缀子项列表，对于每个子项，我将相应的条目保存在字典中...示例：如果我的第一个插入是代码 231，那么字典将如下所示：

这样，如果我的第二次插入是 243，则字典将以这种方式更新：

我的问题是我一直在为这个目的使用向量，并且因为将所有字典都保存在 contiguos 内存中可以让我在迭代它时获得更好的性能。现在，当我需要处理问题的 BIG 实例时，由于调整向量的大小，我无法处理数百万个代码（内存消耗可能高达 200GB）。现在我已经尝试了谷歌的向量稀疏散列，我的问题是，你有什么建议吗？还有其他选择吗？有没有其他方法可以使用整数作为键来提高性能？我知道我不会有任何碰撞，因为每个键都会与其他键不同。

最好的问候，昆汀

我试图编译这个项目：https ://github.com/ccshiro/corecraft 我使用的是 Ubuntu 16.04，我已经安装了：gcc 4.9、5.0、6.0；g++ 4.9、5.0；铛; cmake3; 和 libsparsehash-dev 。

我收到了这个错误：

这里Map.cpp，这里/usr/include/google/sparsehash/hashtable-common.h

我尝试在 Google 上搜索“collect2：错误：ld 返回 1 退出状态”错误，发现代码中可能是西里尔字母或非拉丁字母符号，但我在上面的这 2 个文件中没有发现错误。在问题跟踪器上，我还从另一个人那里发现了同样的错误https://github.com/ccshiro/corecraft/issues/5

我不是 C++ 程序员，所以我不明白这里有什么问题，谁能帮我解决这个问题？

考虑这个简单的程序：

使用 GCC 8.2 和-Wclass-memaccess（或-Wall）编译会产生警告：

问题是：

1. 它是未定义的行为吗？
2. 您能否建议可以应用于应用程序代码的修复或解决方法（不是通过更改 Sparsehash 或避免使用它）？
3. （奖励积分）你能构造一个实际上因此而行为不端的程序（使用 std::string 或你自己的非平凡类型）吗？到目前为止，我在使用 std::string 作为键类型的代码中没有看到任何问题，尽管 std::string 必须是非常常用的键类型。

我在这里提出了一个问题：https ://github.com/sparsehash/sparsehash/issues/149