我有 x（百万）个正整数，它们的值可以尽可能大（+2,147,483,647）。假设它们是独一无二的，那么为查找密集型程序存储它们的最佳方式是什么。
到目前为止，我想到了使用二叉 AVL 树或哈希表，其中整数是映射数据的键（名称）。但是我不确定我是否可以使用哈希表实现如此大的键和如此大的数量（除了容易发生冲突之外，这不会产生> 0.8的负载因子吗？）
我可以就哪种数据结构可能适合我的情况获得一些建议吗
问问题
20379 次
5 回答
7
结构的选择很大程度上取决于您有多少可用内存。我假设基于您需要查找但不循环它们、查找最近或其他类似操作的描述。
最好的可能是一个分桶哈希表。通过将哈希冲突放入存储桶并在存储桶中为键和值保留单独的数组，您既可以适当地减小表的大小，又可以在搜索存储桶时利用 CPU 缓存加速。桶内的线性搜索甚至可能比二分搜索更快！
AVL 树非常适合读取密集型但不是只读的数据集，并且需要有序枚举、查找最近和相似的操作，但要正确实现它们是一项烦人的工作。但是，由于 CPU 缓存行为，您可能会使用 B-tree 获得更好的性能，尤其是缓存忽略 B-tree 算法。
于 2010-11-24T01:55:46.127 回答
2
你研究过B树吗？效率介于 8 到 10 之间log_m(n)，log_(m/2)(n)因此如果您选择m在 8-10 左右，您应该能够将搜索深度保持在 10 以下。
于 2010-11-24T01:55:02.710 回答
2
位向量，如果数字存在，则设置索引。您可以对其进行调整以获取每个数字的出现次数。Bentley 的 Programming Pearls 中有一个关于位向量的不错的专栏。
于 2013-01-05T16:00:43.530 回答
1
如果内存不是问题，地图可能是您最好的选择。地图是 O(1)，这意味着当您扩大要查找的项目数量时，查找值所需的时间是相同的。
一个映射，其中键是 int，值是名称。
于 2010-11-24T01:55:13.940 回答
0
请先尝试哈希表。有一些变体可以容忍非常密集而不会显着放缓（如布伦特变体）。
如果您只需要存储 32 位整数而不需要任何关联的记录，请使用 aset而不是 a map，就像hash_set在大多数 C++ 库中一样。它将只使用 4 字节的记录加上一些恒定的开销和一点松弛以避免 100%。在最坏的情况下，要处理“数百万”个数字，您需要几十兆字节。大，但没有什么不可管理的。
如果您需要更紧凑，只需将它们排序存储在一个普通数组中并使用二进制搜索来获取它们。这将是 O(log n) 而不是 O(1)，但是对于“数百万”条记录，获取其中任何一条记录仍然只需要 20 多步。在 C 中，你有bsearch()，这是尽可能快的。
编辑：刚刚在您的问题中看到您谈到了一些“映射数据（名称）”。这些名字是独一无二的吗？他们也必须在记忆中吗？如果是，它们肯定会主导内存需求。即便如此，如果名称是典型的英文单词，大多数会是 10 字节或更少，总大小保持在“数十兆字节”；也许高达一百兆，仍然非常易于管理。
于 2010-11-24T02:37:33.970 回答