hashset
HashKey trait に
目的
HashSet<.T>を提供 し、new/insert/contains/remove/len/freeの bare 名で操作 できるようにします。- key ごとの
比較 と hash計算 はHashKeytrait に委譲 し、型名埋め込み API をなくします。
実装
- open addressing + linear probing を
用 いる固定長 hash table です。 - bucket
状態 は0 = empty,1 = full,2 = tombstoneで管理 します。
注意
- key 型
.TはHashKeyの impl を持 つ必要 があります。 容量 は固定 で、自動 rehash はまだ行 いません。
計算量
平均 insert/contains/removeは O(1)、最悪 は O(n) です。
HashSet
hash table
new
HashSet<.T> を