将Python字典的最坏情况时间复杂度优化为O(1)

Question

我需要在内存（RAM）中存储5亿个两位数的unicode字符。

我使用的数据结构应该具备：

Worst Case Space Complexity: O(n)
Worst Case Time Complexity: O(1) <-- insertion, read, update, deletion

我在考虑使用字典，因为它是Python中哈希表的实现，但问题是，它在平均情况下能保证操作的时间复杂度是O(1)，但在最坏情况下就不一定了。

我听说如果已知条目的数量，最坏情况下也能实现O(1)的时间复杂度。

那该怎么做呢？

如果在Python中做不到，我能否直接在我的Python代码中访问内存地址和其中的数据？如果可以的话，怎么做呢？

Answer 1

字典在最糟糕的情况下性能是O(n)，不过这种情况发生的可能性很小，通常你不会遇到这种情况。我建议你先使用字典，如果它不能满足你的需求，再考虑换其他的实现方式。

这里有个关于这个话题的有用讨论

Answer 2

你为什么更关心最坏情况下的性能，而不是平均性能呢？任何合理的哈希表在平均情况下都会给你 O(N) 的性能。

如果你真的想要最坏情况下的 O(1) 性能，这里有两种可能的方法：

1. 创建一个包含 max(charCode)-min(charCode) 个条目的向量，然后直接根据 Unicode 字符编码查找你想要的值。如果你的键的范围足够紧凑，可以放进内存里，这种方法效果很好。

2. 用暴力的方法选择哈希函数或字典大小（使用一个自定义的字典实现，让你可以控制这些），不断尝试新的函数和/或大小，直到找到一个没有冲突的。预计这会花费很长时间。我不推荐这种方法。

编辑：

假设你知道最小的字符编码是 1234，最大的字符编码是 98765。再假设你有足够的内存来存放 98765-1234 个元素。我还假设你愿意使用 numpy 库或其他高效的数组实现。在这种情况下，你可以像这样在向量中存储值：

# configuration info
max_value = 98765 # replace with your number
min_value = 1234  # replace with your number
spread = (max_value - min_value)
dtype = object # replace with a primitive type if you want to store something simpler

# create the big vector
my_data = numpy.empty((spread,), dtype=dtype)

# insert elements
my_char_code              = ...
my_value_for_my_char_code = ...

assert min_value <= my_char_code < max_value
my_data[my_char_code - min_value] = my_value_for_my_char_code

# extract elements
my_char_code              = ...
assert min_value <= my_char_code < max_value
my_value_for_my_char_code = my_data[my_char_code - min_value]

这是 O(1) 的，因为查找是通过指针运算实现的，不依赖于数组中存储的元素数量。

如果你实际想存储的元素数量远小于 spread，这种方法可能会非常浪费内存。例如，如果 spread 是 40 亿（即整个 UTF32），那么仅 my_data 就会消耗至少 40 亿 * 8 字节/指针 = 32 GB 的内存（可能还会更多；我不知道 Python 的引用有多大）。另一方面，如果 min_value 是 30 亿，而 max_value = min_value + 100，那么内存使用量就会非常小。

Answer 3

通常情况下，性能下降（通常发生在碰撞时）会在所有调用中平均分摊。所以在大多数实际使用中，你不会每次调用都遇到 O(n) 的情况。实际上，只有在每个键的哈希值都和已有键的哈希值发生碰撞的极端情况下（也就是使用哈希表的最糟糕情况），你才会在每次调用时都遭遇 O(n) 的性能损失。

举个例子，如果你事先知道你的键集合，并且知道它们不会发生哈希碰撞（也就是说，它们的哈希值都是唯一的），那么你就不会遇到碰撞的问题。另一个主要的 O(n) 操作是哈希表的调整大小，但这发生的频率取决于具体的实现（扩展因子/哈希函数/碰撞解决方案等），而且根据输入集合的不同，运行时的表现也会有所不同。

无论如何，如果你能提前用所有的键填充字典，就可以避免突然的运行时变慢。值可以先设置为 None，之后再用真实的值填充。这样在最开始“准备”字典时，性能的下降是唯一明显的，而之后插入值应该是恒定时间的。

一个完全不同的问题是，你打算如何读取或查询这个结构？你需要附加独立的值，并通过键访问它们吗？它需要有序吗？也许使用 set 比 dict 更合适，因为你并不真正需要 key:value 的映射。

更新：

根据你在评论中的描述，这听起来更像是数据库的工作，即使你正在处理一个临时集合。你可以使用内存中的关系数据库（例如，SQLite）。此外，你还可以使用像 SQLAlchemy 这样的 ORM，以更符合 Python 的方式与数据库交互，而不需要编写 SQL。

听起来你可能一开始就是从数据库读取数据，那么也许你可以进一步利用这一点？

存储/查询/更新大量唯一键入的记录，正是关系数据库管理系统（RDBMS）经过几十年的发展和研究所专注的内容。使用现有关系数据库的内存版本（比如 SQLite）可能是一个更务实和可持续的选择。

试试使用 Python 内置的 sqlite3 模块，并通过在构造时提供 ":memory:" 作为数据库文件路径来尝试内存版本：

con = sqlite3.connect(":memory:")