hashmap

目的もくてき

• HashMap<.K, .V> を提供ていきょうし、new / insert / get / contains / remove / len / free の bare 名で操作そうさできるようにします。
• key ごとの比較ひかくと hash 計算けいさんは HashKey trait に委譲いじょうし、specialized helper 名に依存いぞんしない collection にします。

実装じっそう

• open addressing + linear probing の固定長こていちょう hash table です。
• bucket 状態じょうたいは 0 = empty, 1 = full, 2 = tombstone で管理かんりし、削除さくじょで probe chain が壊こわれないようにします。

注意ちゅうい

• key 型 .K は HashKey の impl を持もつ必要ひつようがあります。
• 容量ようりょうは固定こていで、自動 rehash はまだ行おこないません。満杯まんぱいでは Diag::CapacityExceeded を返かえします。

計算量けいさんりょう

• 平均へいきん insert / get / contains / remove は O(1) です。
• 最悪さいあくは probe が全体ぜんたいを走査そうさして O(n) です。

HashMap

key/value を保持ほじする hash table の本体ほんたい

new

空からの HashMap<.K, .V> を作つくる

insert

key に value を挿入そうにゅうまたは更新こうしんする

get

key に対応たいおうする value を探さがす

contains

key の存在そんざいを確たしかめる

remove

key を削除さくじょする

len

要素数ようそすうを返かえす

free

内部ないぶメモリを解放かいほうする