二叉搜索树还是哈希表？

Question

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

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

我的第一次尝试是读取文件并将每个列值插入到二叉搜索树中。如果该值以前从未出现过，则分配内存来存储字符串，否则返回指向该值现有存储的指针。对于大约10万行的数据集，这种方法运行良好。对于更大的数据集，一切都变得非常缓慢，而且内存消耗急剧增加。我认为树中所有这些节点指针的开销没有起到帮助作用，并且使用strcmp进行二进制搜索变得非常痛苦。

这种不令人满意的性能让我相信我应该投资使用哈希表。然而，这引出了另一个问题 - 我事先不知道有多少记录。它可能是10条，也可能是一千万条。如何在时间/空间之间取得正确的平衡，以防止反复调整哈希表大小？

在这种情况下，哪些数据结构是最佳选择？

谢谢您的时间。

- zchtodd

---

为什么不把数据迁移到真正的数据库中呢？这听起来有点像你正在重新发明一个数据库。 - Winston Ewert

在某种程度上，我可以同意这一点，但考虑到应用程序的所有要求，非关系型数据库路线是有道理的，对我们来说仍然如此。 - zchtodd

Answer 1

哈希表的重新调整大小只有在您需要每次插入表中的元素所需的时间相同的要求时才需要考虑。只要您始终按固定因子（例如，始终将大小增加50％）扩展哈希表大小，添加额外元素的计算成本就会分摊为O（1）。这意味着n个插入操作（当n很大时）将花费与n成比例的时间 - 但是，每个插入的实际时间可能会变化很大（实际上，其中一个插入将非常缓慢，而其他插入将非常快，但所有操作的平均值很小）。原因是，当您插入一个额外的元素并强制表从1000000个元素扩展到1500000个元素时，该插入将花费很多时间，但现在您已经为未来的500000个极快速度的插入购买了自己，直到您需要再次调整大小。简而言之，我肯定会选择哈希表。

- Aasmund Eldhuset

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];
}

- BMitch

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)

当然，您在检查每一列后可能会发现有些列无法压缩，应该从“压缩”中排除。

- John Machin