Мне интересно, реализован ли модуль 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)
Источник: Таблица хеширования Википедии
Поскольку модуль dict реализован в самом Erlang, используя встроенные типы данных (кортежи и списки), и является неразрушающим, то есть каждое "обновление" фактически создает слегка переписанную новую версию предыдущего dict, время сложность никогда не может быть лучше логарифмической (реализация должна использовать какое-то дерево), но детали могут варьироваться в зависимости от реализации.
Текущая реализация (которая существует уже много лет) на самом деле не очень хорошо масштабируется, когда количество записей становится большим. Автор (Роберт Вирддинг) недавно экспериментировал с другими реализациями дерева, такими как 2-3 дерева, и вполне возможно, что реализация dict-модуля по умолчанию будет изменена в будущей версии. См. http://erlang.org/pipermail/erlang-questions/2012-June/067311.html
Если вы заинтересованы в подобных вещах, вам может потребоваться больше узнать о чистых функциональных структурах данных. Это кажется хорошей отправной точкой: http://en.wikipedia.org/wiki/Purely_functional (в частности, ссылка на тезис Окасаки).
Хорошо, немного из моей лиги здесь. Прежде всего, это хеш-таблица, но я не уверен в времени выполнения.
Глядя на источник для модуля 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 файлом, на которые вы можете ссылаться на технические подробности реализации (также есть больше комментариев в исходном коде, которые могут быть полезны)
Надеюсь, что он проливает свет на него!