1

我正在另一个论坛上阅读以下帖子，该帖子来自一个似乎对 C++ 内部知识非常了解的关于将数千个键插入“字典”的人：

e) Map and Set 查找是使用红黑树或平衡树完成的，并且每个项目都是“单独”分配的，因此如果您要分配 500,000 个仪器 [按符号] 并带有指向相关仪器对象类的指针，您字符串有'N'个字节[加上开销]，指针有4个字节[加上开销]。并包括；所有工具的一分钟、五秒、一秒价格时间序列和 STD 容器中所有这些工具的完整交易历史。由于小对象分配开销，这是大量的内存和更多的浪费！

f) 众所周知，STD Map & Set 使用 LowerBound [Less Than Compare] 遍历所有键来查找，这非常慢。

g）一些天才可能会说“不，他们使用未排序的地图”......他们没有，但即使他们这样做了，他们仍然在对离散分配的元素进行字符串比较。

我在 C++ 中所做的是以下（示例）；

a）创建一个“自定义”就地字符串类对象，它有两个个性；a) 一个字节数组，和 b) 一个整数数组[模数为 4 并在本机边界上对齐]。b) 使用自定义映射和设置，它们是基于 2x 维度的散列，节点分配在平坦连续内存区域中[可以动态调整大小]。c) String [integer format] Hashing 由 Integer 完成以流水线化 CPU，并且 Key 比较类似地完成。

使用这些只能在 C++、C 或 ASM 中完成的技术，在 .NET、C# 或 Java 中完成的相同操作的性能至少要高 4-5 倍。

http://www.elitetrader.com/vb/showthread.php?s=1eb70fb998d8a51d22050ea53d24db21&threadid=204368&perpage=6&pagenumber=3

如果我大致知道我将插入多少个键，我可以使用哪些技术来设计我自己的 unordered_map 实现，这对于我的特定用途来说比标准实现更有效？

（欢迎任何关于设计散列函数的 101）

4

1 回答 1

6

要使用 aunordered_map您只需为您的 key 设计一个散列函数。C++ 标准库为内置键类型提供了一组散列函数，例如：hash<int>或hash<float>. 如果你取消 aunordered_map<int,int>它默认使用hash<int>它的哈希函数。但是如果你想使用你自己的对象作为key，你必须提供你自己的哈希函数。

优点：虽然 a 中的插入时间较大，但散列通常会在从容器中检索一对时unordered_map<T>提供O(1)复杂性。(key,value)

于 2013-09-07T14:30:51.457 回答