使用哈希图来表示非常大的数据源

题

我有一个非常大的可能数据集，我试图立即将其可视化。该集合本身由数十万个段组成，每个段都映射到一个 id。

我收到了第二个数据源，它为每个段提供更多实时信息，但 id 与我拥有的 id 不对应。

我有数据 id（9 个字符的字符串）到当前 id（长整数）的 1:1 映射。问题是有很多 id，并且传入的数据没有特定的顺序。

我想出的解决方案是使用一个哈希映射将字符串映射到道路 ID。问题是我不知道哈希映射是否足够有效来拥有所有 166k 数据条目。

有人有任何建议和/或哈希算法可供我使用吗？

解决方案

如果你只处理成千上万的数据点，那么采用天真的方式并坚持使用哈希映射可能不会有问题。

即使你有500,000个9个字符的字符串和相同数量的long s，每个项目仍然只有16个字节，或总共8,000,000个字节。即使你将开销增加一倍，16 MB也不会太大而无法在内存中使用。

基本上，首先尝试简单的方法，只有当你的分析告诉你它花了太长时间时才会担心它。

其他提示

Judy Arrays 专为此类设计而设计：<！>“Judy的主要优点是可扩展性，高性能和内存效率。 [...] Judy可以替换许多常见的数据结构，例如数组，稀疏数组，哈希表，B树，二叉树，线性列表，跳过列表，其他排序和搜索算法以及计数函数。<！> quot;

由于对该问题的评论表明主要问题可能是内存使用情况：

用一个 池化或其他小对象优化分配器;假设您有权访问促进你也许可以找到一个直接替代品水池. 。使用更好的小对象分配器可能是您会发现的最大的内存优势。
如果您知道字符串是固定宽度的，您可能需要确保 仅分配足够的空间 来存储它们。例如，使用自定义比较运算符包裹固定长度 char[] 的结构可能比 std::string 更好。std::string 带有额外的动态分配（并为相应的指针使用空间）以及一些额外的大小和容量跟踪开销。（一般情况下，尝试 减少分配数量 留下来的；它减少了开销。）
（假设 STL）查看 std::map 和 std::unordered_map 之间的开销差异（后者目前可能可用，也可能不可用）；一个 基于 RBtree 的 std::map 可能足够接近“哈希图”的查找性能特征，并且可能（或可能不会）具有更高的内存效率，具体取决于您的标准库实现。

您采取的路线应该受到您可以收集的信息的影响 - 尝试了解分配数量和分配大小/对齐开销。

您可以检测您的分配器或插入一些元素，然后看看您在内存使用方面的表现与您认为应该做的相比如何。

由于你的字符串是预先知道的并且具有固定的长度，理论上和实际上最好的解决方案是完美哈希。您可以使用 cmph 来生成它。

根据维基百科，你的密钥需要2.5比特/密钥，或大约50KB。与价值664KB相比，这是可以忽略不计的。

虽然166k数据条目相当小IMO，但您可以查看 google-sparsehash