dictionary - erlang dict的时间复杂度

Question

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

平均情况

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-trees，未来版本可能会更改 dict 模块的默认实现。见http://erlang.org/pipermail/erlang-questions/2012-June/067311.html

如果您对这类事情感兴趣，您可能想阅读更多关于纯函数数据结构的信息。这似乎是一个很好的起点：http ://en.wikipedia.org/wiki/Purely_functional （特别是冈崎论文的链接）。

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 的链接，您可以参考这些链接以了解实现的技术细节（此外，源代码中有更多可能有用的注释）

希望它对它有所启发！