lib/elixir/lib/hash_set.exです。

なにするやつか

iex(1)> set = HashSet.new
#HashSet<[]>
iex(2)> set = HashSet.put(set, :a)
#HashSet<[:a]>
iex(3)> set = HashSet.put(set, :b)
#HashSet<[:b, :a]>
iex(4)> set = HashSet.put(set, :c)
#HashSet<[:c, :b, :a]>
iex(5)> HashSet.member?(set, :b)
true
iex(6)> HashSet.member?(set, :d)
false
iex(7)> set2 = HashSet.new
#HashSet<[]>
iex(8)> set2 = HashSet.put(set2, :e)
#HashSet<[:e]>
iex(9)> HashSet.union(set, set2)
#HashSet<[:e, :c, :b, :a]>

こんな感じに集合を扱えます。HashSetはSetビヘイビアの実装なので、集合が扱えるのは当然なのです。大事なのは内部で何やってるかってことです。

構造体

冒頭に構造体の記述があります。

@node_size 8
@node_template :erlang.make_tuple(@node_size, [])

# 中略

defstruct size: 0, root: @node_template

:sizeと:rootの2つのキーがあるようです。:erlang.make_tuple(8, [])は、8個の空リストを持つタプルを返すので、それぞれ初期値は0と{[], [], [], [], [], [], [], []}です。

iex(1)> set = HashSet.new
#HashSet<[]>
iex(2)> inspect set, structs: false
"%{__struct__: HashSet, root: {[], [], [], [], [], [], [], []}, size: 0}"

`HashSet.put/2`

難しそうなのは置いといて、まずはput/2から。

def put(%HashSet{root: root, size: size}, term) do
  {root, counter} = do_put(root, term, key_hash(term))
  %HashSet{root: root, size: size + counter}
end

do_put/3にrootと追加する要素とそのハッシュ値を与えて、戻り値でrootとsizeを更新しています。

@node_bitmap 0b111
@node_shift 3

defp key_hash(key) do
  :erlang.phash2(key)
end

defp key_mask(hash) do
  hash &&& @node_bitmap
end

defp key_shift(hash) do
  hash >>> @node_shift
end

key_hash/1では、任意の値をハッシュ化できる組み込みのphash2を使っています。キー操作系には他にもkey_mask/1とkey_shift/1があり、それぞれハッシュの下位3bitと、ハッシュを3bit右シフトしたものを返します。次はdo_put/3を見てみます。

defp do_put(node, term, hash) do
  index = key_mask(hash)
  case elem(node, index) do
    [] ->
      {put_elem(node, index, [term]), 1}
    [^term|_] ->
      {node, 0}
    [t] ->
      n = put_elem(@node_template, key_mask(key_shift(hash)), [term])
      {put_elem(node, index, [t|n]), 1}
    [t|n] ->
      {n, counter} = do_put(n, term, key_shift(hash))
      {put_elem(node, index, [t|n]), counter}
  end
end

まずkey_mask/1でハッシュ値の下位3bit、すなわち0〜7の数値を取り出します。それをインデックスとして選ばれたリストの形によってどう処理するか決まります。case文から各リストは以下のいずれかに該当するようです。

[]
[term]
[term | node] (improper list)

termは集合を成す要素で、nodeは8つのリストを持つタプルです。要は8分木です。あと、なぜにimproper listなのかは知らんっす。パフォーマンス的な問題ですかね。

リストが空の場合

リストが空ならそこに要素を入れて、1(追加できた要素数。1か0)をタプルにして返します。

同じものが先頭にある場合

追加しようとしているものと同じものが既に存在している場合は、nodeに手を加えません。重複要素は持たないからです。{node, 0}を返します。

長さ1の場合

リストが要素を1つだけ持っている場合、子ノード8つをつくって、[term | node]に更新します。このとき新たな子ノードのどれかに要素を入れるわけですが、それを選ぶときはハッシュ値を3bit右シフトしてから下位3bitを見ています。ルートに追加するときは2, 1, 0bitを使っていましたが、1段深いところに入れるときは5, 4, 3bit目を使うってことです。

improper listの場合

すでに子ノードを持っているということなので、ハッシュのシフトとマスクを繰り返しながら子ノード達を辿っていき、追加できる場所を見つけます。再帰的ですね。

`delete/2`

def delete(%HashSet{root: root, size: size} = set, term) do
  case do_delete(root, term, key_hash(term)) do
    {:ok, root} -> %HashSet{root: root, size: size - 1}
    :error -> set
  end
end

集合から要素を削除するdelete/2は、削除が成功した場合は要素が1つ減ったHashSet構造体を返し、要素が見つからず削除できなかった場合はそのまま変更せず返します。

defp do_delete(node, term, hash) do
  index = key_mask(hash)
  case elem(node, index) do
    [] ->
      :error
    [^term] ->
      {:ok, put_elem(node, index, [])}
    [_] ->
      :error
    [^term|n] ->
      {:ok, put_elem(node, index, do_compact_node(n))}
    [t|n] ->
      case do_delete(n, term, key_shift(hash)) do
        {:ok, @node_template} ->
          {:ok, put_elem(node, index, [t])}
        {:ok, n} ->
          {:ok, put_elem(node, index, [t|n])}
        :error ->
          :error
      end
  end
end

do_delete/3はdo_put/3のように木構造を探索していき、termにマッチするものを見つけたらそれを消します。do_put/3と違うのは、[term | node]のtermを削除したときに子ノードに対してdo_compact_node/1を適用して木構造を保つことです。nodeの持つ8つのリストの何番目までが空かに応じた8つの関数が定義されています。

Enum.each 0..(@node_size - 1), fn index ->
  defp do_compact_node(node) when elem(node, unquote(index)) != [] do
    case elem(node, unquote(index)) do
      [t] ->
        case put_elem(node, unquote(index), []) do
          @node_template -> [t]
          n -> [t|n]
        end
      [t|n] ->
        [t|put_elem(node, unquote(index), do_compact_node(n))]
    end
  end
end

例えば[t1 | {[], [], [], [], [], [t2}, [], [t3]}]のt1を削除したとすると、有効な木構造を保てないのでt2を引っぱり出して[t2 | {[], [], [], [], [], [], [], [t3]}]にします。もし引っぱり出した結果、子ノードが全て空になってしまったら(@node_templateに等しくなったら)、その子ノード達を持っておく意味はないので[t2]を返します。

ひゃー疲れた

他も読んだは読んだのですが、一番大事なのはデータ構造の理解だなーという感想なのでもうゴールします。こういうデータ構造とか諸々のアルゴリズムとかは弱いので、本とかコードとか読んで手を動かさんとなー。

mmag

ハマったことメモなど

ElixirのHashSetを読んだ