dictionary - erlangdictの時間計算量

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ツリーなどの他のツリー実装を実験しており、将来のリリースで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とのリンクがいくつか表示され、実装の技術的な詳細を参照できます（また、ソースコードには役立つ可能性のあるコメントがあります）

それがそれに光を当てることを願っています！