erlang dict的时间复杂性

Question

我想知道Erlang OTP dict模块是否实现为哈希表,在这种情况下它是否提供了这样的性能？

平均情况

Search: O(1 + n/k)
Insert: O(1)
Delete: O(1 + n/k)

最糟糕的情况

Search: O(n)
Insert: O(1)
Delete: O(n)

来源:维基百科哈希表

Answer 1

因为dict模块是使用内置数据类型(元组和列表)在Erlang中实现的,并且是非破坏性的,也就是说,每个"更新"实际上都会创建一个稍微重写的前一个dict的新版本,时间复杂度永远不会优于对数(实现必须使用某种树),但细节可能随实现而变化.

当条目数量变大时,当前的实现(已经存在多年)实际上并不能很好地扩展.作者(Robert Virding)最近一直在试验其他树实现,例如2-3树,并且有可能在将来的版本中更改dict模块的默认实现.请参见http://erlang.org/pipermail/erlang-questions/2012-June/067311.html

如果您对此类事情感兴趣,可能需要阅读有关纯功能数据结构的更多信息.这似乎是一个很好的起点:http://en.wikipedia.org/wiki/Purely_functional(特别是与Okasaki论文的链接).