人们对各种数据结构的效率提出了类似的问题,但我所读到的都不完全适用于我的场景,所以我想知道人们是否有适合于有效满足以下标准的建议:
- 每个元素都有一个唯一的键。因为每个元素散列到不同的键,所以没有冲突的可能性。EDIT: *键是32位的int型。 *
- 元素都是唯一的,因此可以认为是集合。
- 唯一需要的操作是添加和获取,而不是删除。这些需要很快,因为它们在一次典型的运行中将被使用10万次!
- 元素的保存顺序与无关。
- 速度比内存消耗更重要…虽然它不可能太贪婪的!
我正在为一家公司开发,该公司将在商业上使用该程序,因此任何第三方数据结构都应该没有版权保护或任何东西,但如果STL具有能够有效完成工作的数据结构,那么这将是完美的。
我知道有无数的Hashmap/Dictionary风格的c++数据结构,它们的实现是为了满足不同的标准而构建的,所以如果有人能为这种情况提出一个理想的建议,那将是非常感激的。
多谢编辑:
我在SO上找到了这篇文章,这似乎表明unordered_map会很好?
hash_map和unordered_map通常使用哈希表实现。因此,秩序无法维持。unordered_map插入/删除/查询等于O(1)(常数时间)这里map等于O(log n)这里n是数据结构中的项数。所以unordered_map更快如果你不关心物品的顺序应该优先考虑在地图上。有时您希望保持顺序(按键排序)对于这个map,将是选择。
看起来像前缀树(每个节点末端都有元素)也适合这个场景。它快得要命,甚至比哈希映射还快,因为没有哈希值计算,得到一个值完全是O(n),其中n是键长度。这有点占用内存,但是在相同的节点路径中共享键的公共前缀。
编辑:我假设键是字符串,而不是简单的值,如整数
对于内置解决方案,我建议使用google::dense_hash_map。它们非常快,特别是对于数字键。您必须决定将保留为"empty_key"的特定键。此外,这里有一个非常好的不同哈希映射实现的比较。
节选Library Linux-intCPU (sec) Linux-strCPU (sec) Linux PeakMem (MB)
glib 3.490 4.720 24.968
ghthash 3.260 3.460 61.232
CC’s hashtable 3.040 4.050 129.020
TR1 1.750 3.300 28.648
STL hash_set 2.070 3.430 25.764
google-sparse 2.560 6.930 5.42/8.54
google-dense 0.550 2.820 24.7/49.3
khash (C++) 1.100 2.900 6.88/13.1
khash (C) 1.140 2.940 6.91/13.1
STL set (RB) 7.840 18.620 29.388
kbtree (C) 4.260 17.620 4.86/9.59
NP’s splaytree 11.180 27.610 19.024
但是,当设置"deleted_key"时,该映射也可以执行删除操作。因此,也许有可能创建一个更有效的定制解决方案。但是除了这一点之外,任何散列映射都应该完全满足您的需求(请注意,"map"是一个有序的树状映射,因此速度较慢)。
你需要的肯定听起来像一个哈希集,c++有这个作为std::tr1::unordered_set
或Boost.Unordered。
注:但是请注意,TR1还不是标准,您可能需要获得Boost来实现。
听起来std::unordered_set
符合要求,但是没有知道更多关于钥匙的事,很难说。我很好奇如何保证不会发生碰撞:这意味着一个小的(小于表的大小),有限的集合钥匙。如果是这种情况,将键映射到一个小的int,并使用std::vector
(与空槽的条目不是div)。
您正在寻找的是unordered_set
。您可以在Boost、TR1或c++ 0x中找到它。如果您希望将键与值相关联,那么unordered_map
就可以做到这一点-在Boost/TR1/c++ 0x中也是如此。