ハッシュ配列マップトライ

ハッシュ配列マップトライ^[1]（HAMT ）は、ハッシュテーブルと配列マップトライ^[1]の特性を組み合わせた連想配列の実装です。これは、より一般的なハッシュツリーの概念を改良したものです。

手術

HAMT は配列マップされたトライであり、キーが最初にハッシュされて、キーが均等に分散され、キーの長さが一定であることが保証されます。

HAMT の配列マップトライの一般的な実装では、各ノードには固定数 N のスロットを持つテーブルが含まれ、各スロットには nil ポインタまたは別のノードへのポインタが含まれます。N は通常 32 です。各ノードに N 個のポインタ用のスペースを割り当てるのはコストがかかるため、代わりに各ノードには N ビット長のビットマップが含まれます。このビットマップの各ビットは nil 以外のポインタの存在を示します。この後には、ビットマップ内の 1 の数 (ハミング重み) と同じ長さのポインタ配列が続きます。

HAMTの利点

ハッシュ配列マップトライは、メモリをより経済的に使用しながら、ほぼハッシュテーブルのような速度を実現します。また、ハッシュテーブルは定期的にサイズ変更する必要があり、コストのかかる操作ですが、HAMTは動的に拡張されます。一般的に、HAMTのパフォーマンスは、Nスロットの倍数を持つルートテーブルを大きくすることで向上します。一部のHAMTバリアントでは、ルートを遅延拡張でき、パフォーマンスへの影響は無視できます^[1]。

実装の詳細

HAMT の実装には、数値の 2 進表現における 1 の数を数えるポピュレーションカウント関数の使用が含まれます。この操作は多くの命令セットアーキテクチャで使用できますが、一部の高級言語でのみ使用できます。ポピュレーションカウントは、一連のシフト命令と加算命令を使用してO(1)時間でソフトウェアで実装できますが、その場合、操作の実行速度が 1 桁遅くなる可能性があります。^[^要出典^]

実装

プログラミング言語Clojure ^[2] 、Scala [3] 、Frege ^[4]は、ネイティブのハッシュマップ型にハッシュ配列マップトリップの永続的な変種を使用しています。Haskell ライブラリ「unordered-containers」は、同じものを使用して永続的なマップとセットのデータ構造を実装しています。^[5]別のHaskellライブラリ「stm-containers」は、ソフトウェアトランザクションメモリのコンテキストで使用できるようにアルゴリズムを適応させています。^[6] Clojure 実装に基づくJavascript HAMT ライブラリ^[7]も利用可能です。Rubyの Rubinius ^[8]実装にはHAMT が含まれており、ほとんどが Ruby で書かれていますが、3 つの^[8]プリミティブがあります。Erlang の大きなマップは、リリース18.0 以降、内部で永続的なHAMT 表現を使用しています。 ^[9] Pony プログラミング言語は、永続コレクションパッケージのハッシュマップに HAMT を使用しています。^[10] Rust プログラミング言語に永続コレクション型を提供する im および im-rc クレートは、永続ハッシュテーブルとハッシュセットに HAMT を使用しています。 ^[11]

Ctrieと呼ばれるハッシュトライの並行ロックフリーバージョン^[12]は、進行を保証する可変スレッドセーフ実装です。データ構造は正しいことが証明されています^{[13] - Ctrie操作は、}原子性、線形化可能性、ロックフリーの特性を持つことが示されています。

参照

参考文献

^ abc フィル・バグウェル(2000)。理想的なハッシュツリー(PDF) (レポート)。ローザンヌ連邦エコール工科大学情報科学部。
^ “clojure/clojure”. GitHub . 2022年12月8日.
^ “フレーゲ/フレーゲ”. GitHub。 2022 年 12 月 7 日。
^ Johan Tibell、A. unordered-containers 0.2 の発表
^ Nikita Volkov、「stm-containers」ライブラリの発表、2014 年
^ “マットビアナー/ハムト”. GitHub。 2022年11月27日。
^ 「Rubinius の HAMT の Ruby ソースファイル」。GitHub。
^ https://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802 ^{[リンク切れ‍ ]}
^ 「Erlangプログラミング言語」。
^ 「horse: Pony は、オープンソース、アクターモデル、機能保護、高性能プログラミング言語です: Ponylang/ponyc」。GitHub。2018-11-26。
^ 「Rust im-rc クレート用の API ドキュメント」。
^ Prokopec, A. GitHub での並行ハッシュトライの実装
^ Prokopec, A. 他 (2011) キャッシュ対応ロックフリー同時ハッシュトライ。技術レポート、2011 年。

[bagwell-1] フィル・バグウェル(2000)。理想的なハッシュツリー(PDF) (レポート)。ローザンヌ連邦エコール工科大学情報科学部。

[2] “clojure/clojure”. GitHub . 2022年12月8日.

[3] “フレーゲ/フレーゲ”. GitHub。 2022 年 12 月 7 日。

[4] Johan Tibell、A. unordered-containers 0.2 の発表

[5] Nikita Volkov、「stm-containers」ライブラリの発表、2014 年

[6] “マットビアナー/ハムト”. GitHub。 2022年11月27日。

[7] 「Rubinius の HAMT の Ruby ソースファイル」。GitHub。

[8] ttps://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802 ^{[リンク切れ‍ ]}

[9] 「Erlangプログラミング言語」。

[10] 「horse: Pony は、オープンソース、アクターモデル、機能保護、高性能プログラミング言語です: Ponylang/ponyc」。GitHub。2018-11-26。

[11] 「Rust im-rc クレート用の API ドキュメント」。

[12] Prokopec, A. GitHub での並行ハッシュトライの実装

[13] Prokopec, A. 他 (2011) キャッシュ対応ロックフリー同時ハッシュトライ。技術レポート、2011 年。