我想知道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)
资料来源:Wikipedia Hash Table
最佳答案
由于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论文的链接)。
关于dictionary - Erlang dict的时间复杂度,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/11055391/