<分区>
我必须在内存 (RAM) 中存储 500M 两位数 unicode 字符。
我使用的数据结构应该有:
Worst Case Space Complexity: O(n)
Worst Case Time Complexity: O(1) <-- insertion, read, update, deletion
我正在考虑选择 dict，它是 python 中哈希的实现，但问题是它只在平均情况下而不是在最坏情况下确保所需操作的时间复杂度为 O(1)。
我听说如果条目数已知，在最坏的情况下可以达到 O(1) 的时间复杂度。
怎么做？
万一这在 python 中是不可能的，我可以直接在我的 python 代码中访问内存地址和数据吗？如果是，那么如何？
最佳答案
大多数情况下，性能损失(通常发生在碰撞时)会在所有调用中分摊。因此，对于最实际的使用，您不会每次调用都得到 O(n)。事实上，每次调用都会导致 O(n) 命中的唯一情况是在每个键的哈希值与现有键的哈希值冲突的病态情况下(即最坏的可能(或最不幸的是)哈希表的使用)。
例如，如果您事先知道您的 key 集，并且您知道它们不会发生散列冲突(即它们的所有散列都是唯一的)，那么您就不会遇到冲突情况。另一个主要的 O(n) 操作是调整哈希表的大小，但是这个操作的频率取决于实现(扩展因子/哈希函数/冲突解决方案等)并且它也会随着运行而变化- 根据输入集运行。
在任何一种情况下，如果您可以使用所有键预填充字典，就可以避免运行时突然变慢。这些值可以设置为无，稍后用它们的真实值填充。当最初使用键“启动”dict 时，这应该会导致唯一明显的性能下降，并且 future 的值插入应该是常数时间。
一个完全不同的问题是您打算如何读取/查询结构？您是否需要附加单独的值并通过 key 访问它们？应该订购吗？也许 set 可能比 dict 更合适，因为您实际上并不需要 key:value 映射。
更新:
根据您在评论中的描述，这听起来更像是数据库要做的工作，即使您使用的是临时集。您可以使用内存中的关系数据库(例如使用 SQLite)。此外，您可以使用像 SQLAlchemy 这样的 ORM 以更 python 方式与数据库交互，而无需编写 SQL。
这甚至听起来您可能是从数据库中读取数据开始的，所以也许您可以进一步利用它？
存储/查询/更新大量具有唯一键控的类型化记录正是 RDBMS 经过数十年的开发和研究而专门从事的工作。使用预先存在的关系数据库(例如 SQLite 的)的内存版本可能是一个更务实和可持续的选择。
尝试使用 python 的内置 sqlite3模块并通过提供 ":memory:" 作为构建时的 db 文件路径来尝试内存版本:
con = sqlite3.connect(":memory:")
关于python - 将 python 字典的最坏情况时间复杂度优化为 O(1)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15191918/