Time complexity of erlang dict

Question

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?

Average Case

Search: O(1 + n/k)
Insert: O(1)
Delete: O(1 + n/k)

Worst Case

Search: O(n)
Insert: O(1)
Delete: O(n)

Source: Wikipedia Hash Table

Answer 1

Well, a little out of my league here. First of all, it is a hashtable, but I'm not sure about the execution time.

Looking at the source for the dict module (lib/stdlib/src/dict.erl), shows:

%% 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.

Googling about that paper shows a number of links with the PDF in question, that you can refer to for the technical details of the implementation (also, there are more comments in the source code that might be useful)

Hope it sheds some light on it!

Answer 2

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.

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

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).