erlang dictの時間複雑度

Question

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) 

出典：Wikipedia Hash Table

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

さて、ここで私のリーグのうち少し。まず第一に、ハッシュテーブルですが、実行時間についてはわかりません。 （LIB/STDLIB/SRC/dict.erl）dictのモジュールのソースを見ると

、示しています。その論文についてグーグルで

%% 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とのリンクの数を示します実装の技術的な詳細を参照することができます（また、有用かもしれないより多くのコメントがソースコードにあります）

それはそれにいくつかの光を発することを願っています！