如果我知道键的数量以及这些键的确切含义,python中有什么方法可以使字典(或哈希表)更有效地工作?我隐约记得,如果您知道键,则可以巧妙地设计哈希函数(完美的哈希值?)并预先分配空间。
Python没有公开预定义大小的选项来加快字典的“成长阶段”,也没有提供对字典中“放置”的任何直接控制。
也就是说,如果始终事先知道键,则可以将它们存储在集合中, 并使用dict.fromkeys() 从该集合构建字典。该类方法已优化为根据设置的大小对字典进行预大小设置,并且可以填充字典而无需任何新的__hash __()调用:
>>> keys = {'red', 'green', 'blue', 'yellow', 'orange', 'pink', 'black'}
>>> d = dict.fromkeys(keys) # dict is pre-sized to 32 empty slots
如果要减少冲突是您的目标,则可以对字典中的插入顺序进行实验以最大程度地减少堆积。(看看Knuth的TAOCP中布伦特对算法D的变化,以了解如何完成此操作)。
通过为字典(例如this)使用纯Python模型,可以计算替代插入顺序的探针的加权平均数。例如,dict.fromkeys([11100, 22200,44400, 33300])
每次查询平均插入1.75个探针。超过了每次查找的2.25次平均探查dict.fromkeys([33300, 22200,11100, 44400])
。
另一个“窍门”是通过愚弄它以增加其大小而不增加新的键s,从而增加完全填充的字典中的空缺:
d = dict.fromkeys(['red', 'green', 'blue', 'yellow', 'orange'])
d.update(dict(d)) # This makes room for additional keys
# and makes the set collision-free.
最后,您可以为密钥引入自己的自定义__hash __(),以消除所有冲突(可能使用完美的哈希生成器,例如gperf )。