unordered_map如何工作/优化设计？

Question

我正在另一个论坛上阅读以下帖子,这个帖子似乎对C++内部有很多关于将数千个密钥插入"字典"的知识:

e)Map-Set查找是使用Red-Black或Balanced Tree完成的,每个项目都是"单独"分配的,所以如果你要[按符号]分配500,000个仪器,并指向一个与相关的仪器对象类的指针,字符串有'N'个字节[加上开销],指针有4个字节[加上开销].并包括; 所有仪器上的1分钟,5秒,1秒的价格时间序列以及STD容器中所有这些仪器的完整贸易历史.由于小对象分配开销,这是一个很多的内存和一个很多的浪费!

f)出了名的是,STD Map&Set使用LowerBound [Less Than Compare]通过所有键到FIND,这很慢.

g)有些天才可能会说"不,他们使用未排序的地图"......好吧他们没有,但即使他们这样做,他们仍然在对一个离散分配的元素进行字符串比较.

我在C++中做的是以下(示例);

a)创建一个"自定义"就地String Class-object,它有两个个性; a)字节数组,和b)模数4和在本地边界上对齐的整数数组.b)使用自定义映射和集合,它们是基于2x维度的哈希,其中节点在平坦连续内存区域中分配[可以并且可以动态地重新调整大小].c)String [整数格式]散列由Integer完成,用于管道CPU和键比较类似地完成.

使用这些技术只能在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都是最受欢迎的)

Answer 1

要使用unordered_map你只需要为你的密钥设计一个哈希函数.C++标准库为内置键类型提供一组哈希函数,如:hash<int>或hash<float>.如果你删除unordered_map<int,int>它,它将默认使用hash<int>它的哈希函数.但是如果你想使用你自己的对象作为键,你必须提供自己的哈希函数.

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