如果二郎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:
因为字典模块在二郎山本身使用内置的数据类型（元组和列表）来实现，而且是破坏性的，那就是，每一个“更新”实际上创建以前快译通的稍微改写新版本，时间复杂度绝不能比对数好（实现必须使用某种树的），但在细节上可以与实施而变化。
当前的实现（这已经许多年）实际上并没有很好地扩展，当条目数变大。 笔者（罗伯特Virding）最近一直在尝试其他树的实现，如2-3树，它是可能的字典模块的默认实现会在将来的版本中改变。 见http://erlang.org/pipermail/erlang-questions/2012-June/067311.html
如果你有兴趣在这样的事情，你可能想阅读更多的关于纯功能性数据结构。 这似乎是一个很好的起点： http://en.wikipedia.org/wiki/Purely_functional （特别是链接Okasaki的论文）。
Answer 2:
嗯，一点点从我的联赛在这里。 首先，它是一个哈希表，但我不能确定执行时间。
查看源的字典模块（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链接，你可以参考的执行的技术细节（也有在源代码中更多的评论可能有用）
希望它揭示一些关于它的光芒！
文章来源: Time complexity of erlang dict
