通常情况下,效果指标(通常是在碰撞时发生)会在所有通话中进行摊销。因此,对于大多数实际使用而言,您不会O(n)
每次通话都得到帮助。实际上,唯一会导致O(n)
每次呼叫命中的情况是在病理情况下,其中每个键的哈希值与现有键的哈希值相冲突(即,哈希表的最坏(或最不幸)用法)。
例如,如果您事先知道一组键,并且知道它们不会发生哈希冲突(即,它们的所有哈希都是唯一的),那么您就不会遇到冲突情况。另一个主要O(n)
操作是哈希表大小调整,但是它的频率取决于实现方式(扩展因子/哈希函数/冲突解决方案等),并且还取决于输入集的运行时间。
无论哪种情况,如果都可以用所有键预填充字典,则可以避免运行时突然变慢。可以将这些值设置为“无”,然后再使用其实际值进行填充。最初用键“启动”字典时,这应该会导致唯一明显的性能下降,并且将来的值插入应为恒定时间。
一个完全不同的问题是您打算如何读取/查询结构?您是否需要附加单独的值并可以通过密钥访问它们?应该订购吗?也许aset
可能比a更合适dict
,因为您实际上并不需要key:value
映射。
根据您在注释中的描述,这听起来似乎更像是数据库要做的工作,即使您正在使用临时集也是如此。您可以使用内存中的关系数据库(例如,使用sqlite)。此外,您可以使用像sqlAlchemy这样的ORM来更Python地与数据库交互,而不必编写sql。
甚至听起来您可能正在从数据库中读取数据,所以也许您可以进一步利用它?
存储/查询/更新大量唯一键入的类型化记录正是RDBMS经过数十年的开发和研究而专门针对的内容。使用内存中的现有关系数据库版本(例如sqlite)可能是一个更加实用和可持续的选择。
尝试使用python的内置sqlite3
模块,并通过":memory:"
在构建时提供db文件路径来尝试使用内存中的版本:
con = sqlite3.connect(":memory:")