如果我知道键的数量和确切的键是什么,有没有办法在Python中使字典(或哈希表)更有效率?我依稀记得,如果你知道键,可以设计一个聪明的哈希函数(完美哈希?)并预先分配空间。
Python不提供预调整大小选项以加速字典的“增长阶段”,也没有直接控制字典中的“放置”。
话虽如此,如果键始终事先已知,您可以将它们存储在
set中,并使用
dict.fromkeys()从集合构建字典。该classmethod已经
优化为根据集合大小预调整字典的大小,并且可以在不调用__hash __()的情况下填充字典:
>>> keys = {'red', 'green', 'blue', 'yellow', 'orange', 'pink', 'black'}
>>> d = dict.fromkeys(keys) # dict is pre-sized to 32 empty slots
如果减少冲突是您的目标,您可以在字典中运行插入顺序实验以最小化堆积。(请参考Knuth的TAOCP中
Brent算法D的变体,了解如何执行此操作)。
通过为字典(例如
这个)提供纯Python模型进行检测,可以计算替代插入顺序的加权平均探查次数。例如,插入
dict.fromkeys([11100, 22200, 44400, 33300])
每次查找的平均探查次数为1.75。这比
dict.fromkeys([33300, 22200, 11100, 44400])
的平均2.25次要好。
另一个“技巧”是通过欺骗完全填充的词典,增加其稀疏性,使其增加大小而不添加新键:
d = dict.fromkeys(['red', 'green', 'blue', 'yellow', 'orange'])
d.update(dict(d))
最后,你可以为你的键引入自定义的 __hash__(),旨在消除所有冲突(可能使用完美哈希生成器,如
gperf)。