我有大型文本文件，需要对其执行各种操作，主要涉及逐行验证。数据通常具有销售/交易性质，因此往往包含大量跨行的冗余信息，例如客户姓名。迭代和处理这些数据已经成为一项常见的任务，以至于我正在用 C 语言编写一个库，希望将其作为 Python 模块提供。
在一次测试中，我发现在 130 万个列值中，只有大约 300,000 个是唯一的。内存开销是一个问题，因为我们基于 Python 的 Web 应用程序可能会同时处理对大型数据集的请求。
我的第一次尝试是读入文件并将每个列值插入到二叉搜索树中。如果以前从未见过该值，则分配内存来存储该字符串，否则返回指向该值的现有存储的指针。这适用于约 100,000 行的数据集。更大，一切都停止了，内存消耗猛增。我假设树中所有这些节点指针的开销没有帮助，并且使用 strcmp 进行二进制搜索变得非常痛苦。
这种不尽如人意的表现让我相信我应该投资于使用哈希表。然而，这提出了另一点——我事先不知道有多少记录。可能是 10 个，也可能是 1000 万个。如何在时间/空间上取得适当的平衡，以防止一次又一次地调整哈希表的大小？
在这种情况下，最好的数据结构候选者是什么？
感谢您的宝贵时间。
最佳答案
调整哈希表的大小不是一个问题，除非您要求每个插入到表中的操作都应该花费相同的时间。只要您始终按常数因子扩展散列表大小(例如，始终将大小增加 50%)，添加额外元素的计算成本就会分摊 O(1)。这意味着 n 插入操作(当 n 很大时)将花费与 n 成比例的时间 - 然而，实际时间每次插入可能会有很大差异(实际上，其中一个插入会非常慢，而其他插入会非常快，但所有操作的平均值很小)。这样做的原因是，当您插入一个额外的元素时，该元素会强制表格从例如1000000 到 1500000 个元素，插入将花费很多时间，但现在您已经为自己购买了 500000 个极快的 future 插入，然后才需要再次调整大小。简而言之，我肯定会选择哈希表。
关于python - BST 还是哈希表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5931151/