Erlang字典的时间复杂度

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)

来源：维基百科哈希表

- Magnus Kronqvist

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论文的链接）。

- RichardC

Answer 2

嗯，这有点超出我的能力范围。首先，它是一个哈希表，但我不确定执行时间。

查看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文件，你可以参考其技术实现方面的细节（另外，在源码中还有更多可能有用的注释）

希望这能为您提供一些帮助！

- marcelog