二叉搜索树还是哈希表？

Question

我有一些很大的文本文件，需要对这些文件进行各种操作，主要是逐行验证。这些数据通常与销售或交易有关，因此在行与行之间往往会有很多重复的信息，比如客户名字。处理和操作这些数据已经成为一项常见的任务，所以我正在用C语言编写一个库，希望能把它做成一个Python模块。

在一次测试中，我发现130万个列值中，只有大约30万个是独一无二的。内存使用量是一个问题，因为我们的Python网页应用可能会同时处理多个大数据集的请求。

我第一次尝试是读取文件，把每个列值插入到一个二叉搜索树里。如果这个值之前没有出现过，就会分配内存来存储这个字符串；如果已经存在，就返回指向那个值的现有存储的指针。对于大约10万行的数据集，这个方法效果不错。但如果数据集更大，处理速度就会变得很慢，内存消耗也会飙升。我猜树中那些节点指针的开销并没有帮助，而且用strcmp进行二叉搜索也变得非常麻烦。

这种不理想的表现让我觉得应该考虑使用哈希表。不过，这又带来了另一个问题——我事先根本不知道会有多少记录。可能是10条，也可能是1000万条。我该如何在时间和空间之间找到一个合适的平衡，以避免哈希表一次又一次地调整大小呢？

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

感谢你的时间。

Answer 1

我希望能把一个用C语言写的库做成Python模块。

Python里面已经有非常高效、调校得很好的哈希表了。我强烈建议你先把你的库或模块在Python中做好。然后再检查一下速度。如果速度不够快，就分析一下性能，找出那些拖慢速度的地方，可能可以用Cython来解决。

设置代码：

shared_table = {}
string_sharer = shared_table.setdefault

压缩每一行输入数据：

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

当然，你在检查每一列的时候，可能会发现有些列压缩效果不好，应该排除在“压缩”之外。

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

哈希表的大小调整其实不是个大问题，除非你有要求希望每次插入的时间都一样。只要你每次扩展哈希表的大小是按固定比例增加，比如说每次增加50%，那么添加一个新元素的时间平均下来就是 O(1)。这意味着当你进行 n 次插入操作时（当 n 很大的时候），所花的时间和 n 是成正比的。不过，实际每次插入所需的时间可能会有很大差别（在实际操作中，有一次插入可能会非常慢，而其他的则会很快，但所有操作的平均时间还是很小的）。原因是，当你插入一个新元素，导致哈希表的大小从比如说1000000扩展到1500000时，这次插入会花费很多时间，但这之后你就可以进行500000次非常快速的插入，而不需要再调整大小。总之，我绝对推荐使用哈希表。