BST 还是哈希表？

Question

我有大型文本文件，需要对其执行各种操作，主要涉及逐行验证。这些数据通常具有销售/交易性质，因此往往包含大量跨行的冗余信息，例如客户姓名。迭代和操作这些数据已成为一项常见任务，因此我正在用 C 编写一个库，希望将其作为 Python 模块提供。

在一项测试中，我发现在 130 万个列值中，只有约 300,000 个是唯一的。内存开销是一个问题，因为我们基于 Python 的 Web 应用程序可能会同时处理大型数据集的请求。

我的第一次尝试是读入文件并将每个列值插入到二叉搜索树中。如果以前从未见过该值，则分配内存来存储该字符串，否则返回指向该值的现有存储的指针。这对于大约 100,000 行的数据集非常有效。更大了，一切都会停止，内存消耗猛增。我认为树中所有这些节点指针的开销没有帮助，并且使用 strcmp 进行二分搜索变得非常痛苦。

这种令人不满意的性能使我相信我应该投资使用哈希表。然而，这提出了另一点——我事先不知道有多少记录。可能是十个，也可能是一千万。如何实现时间/空间的正确平衡，以防止一次又一次地调整哈希表的大小？

在这种情况下，最好的数据结构是什么？

感谢您抽出时间。

Answer 1

哈希表大小调整不是一个问题，除非您要求每次插入到表中的时间应该相同。只要您始终将哈希表大小扩展为常数因子（例如始终将大小增加 50%），添加额外元素的计算成本就会摊销O(1)。这意味着 n 次插入操作（当 n 很大时）将花费与 n 成比例的时间 - 然而，实际时间每次插入可能会有很大差异（实际上，其中一个插入会非常慢，而其他插入会非常快，但所有操作的平均值很小）。这样做的原因是，当您插入一个额外的元素，迫使表从 1000000 个元素扩展到 1500000 个元素时，该插入将花费大量时间，但现在您已经为自己购买了 500000 个极快的未来插入，然后您才需要再次调整大小。简而言之，我肯定会选择哈希表。

Answer 2

您需要使用哈希表的增量调整大小。在我当前的项目中，我跟踪每个存储桶中使用的哈希键大小，如果该大小低于表的当前键大小，那么我会在插入或查找时重新哈希该存储桶。在调整哈希表大小时，键大小加倍（向键添加额外的位），并且在所有新存储桶中，我只需添加一个指向现有表中适当存储桶的指针。因此，如果n是哈希桶的数量，则哈希扩展代码如下所示：

n=n*2;
bucket=realloc(bucket, sizeof(bucket)*n);
for (i=0,j=n/2; j<n; i++,j++) {
  bucket[j]=bucket[i];
}

Answer 3

我希望制作的C语言库
可作为 Python 模块使用

Python 已经内置了非常高效的微调哈希表。我强烈建议您首先让您的库/模块在 Python 中运行。然后检查速度。如果这还不够快，请对其进行分析并删除您发现的任何减速带，也许可以使用 Cython。

设置代码：

shared_table = {}
string_sharer = shared_table.setdefault

整理每个输入行：

for i, field in enumerate(fields):
    fields[i] = string_sharer(field, field)

在检查每一列后，您当然可能会发现某些列压缩得不好，应该从“整理”中排除。