时间复杂的erlang dict [英] Time complexity of erlang dict

问题描述

我想知道Erlang OTP dict是否作为哈希表实现，在这种情况下是否会提供这样的性能？

I am wondering if the Erlang OTP dict module is implemented as a hash table and in that case does it give the performance of such?

平均案例

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，时间复杂度永远不会优于对数（实现必须使用某种的树），但细节可能随着实施而变化。

Because the dict module is implemented in Erlang itself using the built-in data types (tuples and lists), and is nondestructive, that is, every "update" actually creates a slightly rewritten new version of the previous dict, the time complexity can never be better than logarithmic (the implementation must use some kind of tree), but the details can vary with the implementation.

目前的实施（已经存在了很多年）并没有实际扩大，条目变大。作者（Robert Virding）最近一直在尝试使用其他树实现，例如2-3个树，并且可能会在将来的版本中改变dict模块的默认实现。请参阅 http://erlang.org/pipermail/erlang-questions/2012-June/067311.html

The current implementation (which has been around for many years) doesn't actually scale well when the number of entries gets large. The author (Robert Virding) has recently been experimenting with other tree implementations such as 2-3-trees, and it is possible that the default implementation of the dict module will be changed in a future release. See http://erlang.org/pipermail/erlang-questions/2012-June/067311.html

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

If you're interested in this sort of thing, you might want to read up more about pure functional data structures. This seems like a good starting point: http://en.wikipedia.org/wiki/Purely_functional (in particular the link to Okasaki's thesis).

这篇关于时间复杂的erlang dict的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！