data-structures - 效率 : What data structure to use. ..？

Question

我正在处理一个非常大的数据集。本质上，我将处理数百万条记录并将值存储到数据集中。

每次我存储一个值时，我必须首先检查以确保该值不在数据结构中。如果值在数据结构中，我必须更新(或删除/添加)记录以更新计数。

数据集中有重复，我不想使用糟糕的数据结构并获得 O(n) 的速度，因为我希望能够在一夜之间运行它并在早上完成它!

有什么建议吗？

Answer 1

正如其他人所说，哈希表是 可能 正确答案，但是 哈希表的空间效率并不高，所以如果您到了可能耗尽内存的地步，您应该考虑一个排序的键数组和一个并行排序的值数组。基本上，如果您可以预先访问整个键列表，请创建一个数组并对其进行排序。然后创建一个并行的值数组。每次需要存储东西时，只需进行二分查找(O(log N))即可找到键数组中的索引，然后更新值数组中的对应索引。这将比哈希表的速度效率低，但可以保证几乎没有空间开销。