我想知道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)
来源:维基百科哈希表
我想知道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)
来源:维基百科哈希表
因为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论文的链接)。
嗯,这有点超出我的能力范围。首先,它是一个哈希表,但我不确定执行时间。
查看dict模块的源代码(lib/stdlib/src/dict.erl),可以看到:
%% We use the dynamic hashing techniques by Per-�ke Larsson as
%% described in "The Design and Implementation of Dynamic Hashing for
%% Sets and Tables in Icon" by Griswold and Townsend. Much of the
%% terminology comes from that paper as well.
在谷歌上搜索该论文将会得到一些相关的链接,其中包括需要的PDF文件,你可以参考其技术实现方面的细节(另外,在源码中还有更多可能有用的注释)
希望这能为您提供一些帮助!