Zenn
来栖川電算Publicationへの投稿
🍟

Julia の `hash()` について

antimon2
2023/11/14に公開
3件
Julia
hash
tech

TL;DR

  • ==（または isequal()）を多重定義したら、hash() も多重定義しましょう！

for other language users

  • 他の（特にクラスを持つオブジェクト指向の）言語でがっつり開発している人には、ひょっとしたら当たり前の内容かも知れない。
  • 他言語で hash() 系の関数（メソッド）をオーバーライドしたことある方にも「Julia ならこうなる」という何かしらの参考になるかも。

初めに

この記事を書こうと思った発端は、私が管理人の1人である JuliaTokai の Discord でこんな投稿があったことです（以下抜粋）。

unique() 関数のバグを見つけたかもしれない。ユーザ定義型できちんと isequal(◯◯, △△) が動作するように定義しているのに unique にならないことがある。

julia> struct Foo
           vec::Vector{Int}
       end

julia> function Base.:(==)(a::Foo, b::Foo)  # `==` を多重定義すれば `isequal()` にも適用される
           a.vec == b.vec
       end

julia> a = Foo([1, 2])
Foo([1, 2])

julia> b = Foo([1, 2])
Foo([1, 2])

julia> isequal(a, b)
true

julia> unique([a, b])  # `[Foo([1, 2])]` だけになってほしい
2-element Vector{Foo}:
 Foo([1, 2])
 Foo([1, 2])

なお unique() 関数のヘルプはこうなってます：

help?> unique
search: unique unique! allunique

  `unique(itr)`

  Return an array containing only the unique elements of collection `itr`,
  as determined by `isequal`, in the order that the first of each set of
  equivalent elements originally appears. The element type of the input
  is preserved.

  See also: `unique!`, `allunique`, `allequal`.

  Examples
  ≡≡≡≡≡≡≡≡≡≡

  julia> unique([1, 2, 6, 2])
  3-element Vector{Int64}:
   1
   2
   6

  julia> unique(Real[1, 1.0, 2])
  2-element Vector{Real}:
   1
   2

# : 《以下略》

簡単にまとめると以下の通り：

  • unique() はコレクション（イテレータ）に対して unique な要素のみを集めた配列を返す関数。
  • 同値性（等価性）は isequal() で判定される。

なのでユーザ定義型でも isequal() を適切に定義すれば unique() によって unique な要素のみを集めた配列を得ることができるはず。なのにそれができない。という主張。

勘の良い方ならもうお分かりですね？
この場合、isequal() だけではなく hash() も適切に定義すれば見事解決します。
今回の場合は、例えば以下のようにすればOKです：

julia> # `Foo` や `isequal` は上記で定義済のものとする

julia> function Base.hash(a::Foo, h::UInt)  # 任意のユーザ定義型に対する `hash()` の定義例
           hash(:Foo, hash(a.vec, h))
       end

julia> a = Foo([1, 2])
Foo([1, 2])

julia> b = Foo([1, 2])
Foo([1, 2])

julia> isequal(a, b)
true

julia> hash(a) == hash(b)
true

julia> unique([a, b])  # `[Foo([1, 2])]` にちゃんとなる！
1-element Vector{Foo}:
 Foo([1, 2])

この hash() という関数は一体何なのか。なぜ isequal() だけでなく hash() もきちんと定義すべきなのか。
といった辺りを Julia ユーザ向けに解説していきます。

hash() とは

まずは hash のヘルプ（抜粋）を見てみましょう。

help?> hash
search: hash hasmethod haskey hasfield 《...以下略》

  hash(x[, h::UInt]) -> UInt

  Compute an integer hash code such that `isequal(x,y)` implies `hash(x)==hash(y)`.
  The optional second argument `h` is another hash code to be mixed with the result.

  New types should implement the 2-argument form, typically by calling the 2-argument
  `hash` method recursively in order to mix hashes of the contents with each other
  (and with `h`). Typically, any type that implements `hash` should also implement
  its own `==` (hence `isequal`) to guarantee the property mentioned above. 《以下略》

  julia> a = hash(10)
  0x95ea2955abd45275

  julia> hash(10, a) # only use the output of another hash function as the second argument
  0xd42bad54a8575b16

  See also: `objectid`, `Dict`, `Set`.

まとめると以下のような感じになります。

  • ハッシュコード を計算する関数である。
  • isequal(x, y) ⇒ hash(x) == hash(y) である（べきである（仕様））。
  • （ユーザ定義型で）hash(x, h) を実装するなら、== も実装するべきである。

ハッシュコード（日本語で「ハッシュ値」とか「要約値」とも言います）は、オブジェクト（値）を変換した固定長の値のことで、だいたい以下のような性質を求められるものです：

  1. 同値なオブジェクトに対するハッシュコードは同じ値になる。
  2. ほんの少しでも異なるオブジェクトに対してはできる限り見た目全然違うハッシュコードになる。

ハッシュコードを計算する関数を ハッシュ関数[1] と呼びます。Julia の hash() はハッシュ関数です。

先述の「ハッシュコードに求められる性質」のうち、2. の方は「値域に一様に（言ってみればランダムに）分布してほしい」ということですが、今回の本題ではないのでそれ以上は割愛します。
ポイントとなるのは性質 1. の方。これはヘルプにもあった『isequal(x, y) ⇒ hash(x) == hash(y) である（べきである）』のことをそのまま言っています。
なお isequal() のヘルプを見てみると（抜粋）↓

help?> isequal
search: isequal issetequal

  isequal(x, y)

  # :《中略》

  Implementation
  ≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡

  The default implementation of `isequal` calls `==`, so a type that does not involve
  floating-point values generally only needs to define `==`.

  `isequal` is the comparison function used by hash tables (`Dict`). `isequal(x,y)` must
  imply that `hash(x) == hash(y)`.

  This typically means that types for which a custom `==` or `isequal` method exists must
  implement a corresponding `hash` method (and vice versa). ...

  # :《以下略》

実装についての説明にこのようなことが書かれていますね。

  • isequal(x, y) のデフォルト実装は == を呼び出す。
  • isequal はハッシュテーブル（Dict）で使われる比較関数である。
  • isequal(x, y) ⇒ hash(x) == hash(y) である（べきである）（2回目）。
  • 従って == または isequal のどちらかのカスタムメソッドを定義した型は、hash のメソッドも定義すべきである。

同じことが、少し詳しく記述されていますね。
とにかく重要なのは、『==（または isequal()）を多重定義した型は、hash() も多重定義すべきである』ということです。

hash() の用途

isqequal() のヘルプに Dict（辞書）についての言及がありましたよね。
Dict は、キーと値のペアを保持するコレクション型です。
Julia の Dict はそこにも書かれているとおり、ハッシュテーブル[2] を利用して実装されています。ハッシュテーブルの「ハッシュ」とはハッシュコードのことです。

そうです。（Julia の）ハッシュ関数 hash() が返すハッシュコードは、Dict の内部のハッシュテーブルで利用されています[3]。少しだけ詳細を説明すると、登録したいエントリー（キーと値のペア）のキーに対してハッシュ関数を利用してハッシュコードを計算し、そのハッシュコードをハッシュテーブルのインデックスと照合することで高速な検索が可能となっています。

また Julia には Dict の他に Set（集合）も用意されています。
Set は、重複のない要素の組を格納するコレクション型です。
Julia の Set は実は Dict を利用して実装されています。ざっくり言うと、Set は Dict のキーだけを保持する仕組みになっています。

つまり、hash() の用途としては以下のようにまとめることができます。

  • hash() を実装した型の値は、Dict（辞書）のキーとして利用できる。
  • hash() を実装した型の値は、Set（集合）の要素として格納できる。

さて「重複がない」と言えば、元々の発端は unique() でしたね。
unique() が返すのは（要素の重複のない）配列であって集合ではありませんが、実は Set とも密接に関連しています。
答えを言ってしまうと、unique() は内部で Set を利用しています。具体的には、「既に出てきた値かどうかを管理する Set を用意しておいて、そこに登録されていなければ収集（と同時にその Set に登録）し、登録済なら読み飛ばす」という仕組みに（デフォルト実装は）なっています。

これで繋がりましたね。
ユーザ定義型で unique() 関数できちんと重複なく要素を集めたいなら、==（isequal()）だけでなく hash() を実装する必要がある、ということです。

（これ、だから unique() のヘルプに isequal() への言及だけじゃなくて「hash() も内部で利用している（からユーザ定義型で isequal と hash の定義よろしくね）」的なことまで書かれていないと不親切ですよね…「isequal を使うってことは当然 hash も使うこと前提だよそれくらい想定しろよ」ってそこまでユーザに求められてるんですかね…[4]）

hash() の実装例

では、具体的に Julia では hash() 関数をどのように定義（多重定義）すれば良いのかというと。
割と典型的な実装方法は、最初に示したようなものです（再掲）：

julia> struct Foo
           vec::Vector{Int}
       end

julia> function Base.:(==)(a::Foo, b::Foo)
           a.vec == b.vec
       end

julia> function Base.hash(a::Foo, h::UInt)  # 任意のユーザ定義型に対する `hash()` の定義例
           hash(:Foo, hash(a.vec, h))
       end

つまり。
定義したユーザ定義型（複合型）の、等価性を判定するために利用しているフィールドに対して hash() を再帰的に呼び出して、その結果を hash() の第2引数 h と混ぜ合わせて返す、という実装です。

なお上記の例では hash(:Foo, hash(a.vec, h)) のようにしていますが、最初の :Foo は、定義する対象の型が Foo という名前だからで、Bar ならば :Bar とかにすればOKです。
もしくはもっと効率を考えるなら、何か適当な UInt64 の値を（例えば Julia の REPL 上で rand(UInt64) でも実行して）生成してそれを利用して、hash(a.vec, h + 0x0123456789abcdef) のようにしても良いです。
ここでのポイントは以下の通り：

  • 必ず2引数のメソッドを追加すること（第1引数が対象となるユーザ定義型、第2引数は h::UInt）。
  • 基本的には実装例のように hash(～, h) をネストして呼ぶ感じでOK。
  • その場合、最後に呼び出す hash(～, h′) の h′ の値が明らかに 0 になっているような状況は避けること（偶然 0 になってしまう分には構わない）。

少しだけ詳しく解説します。

hash(hoge) は一部の例外を除き、内部で2引数の hash(hoge, zero(UInt)) を呼ぶようになっています。これがポイントの1番目と3番目の理由で、特別な理由がない限りは1引数の hash(a::Foo) を多重定義すべきではありません。
2引数の hash(a::Any, h::UInt) はデフォルト実装では然るべき高速なアルゴリズムで適度に分散された一様なハッシュコードを算出するようになっています。その際、h の値がほんの少しでも異なれば全く違う値が算出される工夫がされています。よって新しい型に hash(a::Foo, h::UInt) を適用させるには、内部で hash(a.◯◯, hash(a.△△, ～)) のようにネストするのが効果的、というわけです。

hash() の半自動的な実装例

フィールドの数が多くなると、その都度 hash(a.◯◯, hash(a.△△, hash(a.××, ...))) のようにネストしていくのは面倒になってきます。
私は以下のような半自動的な実装方法を使っています。

@generated function _equals_by_fields(a::T, b::T) where T
    _cmp_field(name) = :(getfield(a, $(QuoteNode(name))) == getfield(b, $(QuoteNode(name))))
    mapfoldr(_cmp_field, (x,y) -> :($x && $y), fieldnames(T), init=true)
end

@generated function _hash_by_fields(a::T, h::UInt) where T
    h_init = hash(T)
    _get_field(name) = :(getfield(a, $(QuoteNode(name))))
    mapfoldl(_get_field, (h, x) -> :(hash($x, $h)), fieldnames(T), init=:(h + $h_init))
end

@generated function ～ というのは 生成関数[5] というものの定義で、引数の型が確定したときに関数本体を動的に生成する関数です。Julia のメタプログラミングの機能の1つです。

例えば新しいユーザ定義型を以下のようなものだとしましょう：

struct Person
    name::String
    age::Int
end

_equals_by_fields() の方は、各フィールドに対して == を呼び出してその結果を && で繋げていくようなコードを生成します。つまり Person 型の場合、a.name == b.name && a.age == b.age というコード（より正確には a.name == b.name && (a.age == b.age && true)）を生成します。

_hash_by_fields() も同様、hash() 呼び出しをネストするコードを生成します。Person 型の場合、hash(a.age, hash(a.name, h + hash(Person))) というコードと同等になります。ただし hash(Person) は結果が恒等（常に同じ値を返すはず）なので事前に算出しておいてその値を埋め込むようにしています。つまり例えばその値が 0x123456789abcdef0 だった場合、実際に生成されるコードは hash(a.age, hash(a.name, h + 0x123456789abcdef0)) となります。

これを Person 型の == と hash() に適用するには、以下のようにすればOKです：

Base.:(==)(a::Person, b::Person) = _equals_by_fields(a, b)
Base.hash(a::Person, h::UInt) = _hash_by_fields(a, h)

このうように新しいユーザ定義型を定義した際、「全てのフィールドがそれぞれ等しいなら2つのインスタンスは等しい」という定義で良ければ、これを利用できます[6]。

以上、ぜひ参考にしてください。

2023.11.18 追記: AutoHashEquals.jl

コメントで AutoHashEquals.jl というパッケージを教えていただきました（知らなかった）。
これは、上記のような ==（および isequal()）と hash() の実装を自動生成してくれるパッケージです。

例えば先の例の拡張例として以下のようになります：

using AutoHashEquals

@auto_hash_equals struct Person
    name::String
    age::Int
    weight::Float64
end

alice1 = Person("Alice", 14, 48.0)
alice2 = Person("Alice", 14, 48.0)

@assert alice1 == alice2
@assert isequal(alice1, alice2)
@assert hash(alice1) == hash(alice2) == hash(alice1.weight, hash(alice1.age, hash(alice1.name, hash(:Person, zero(UInt)))))

このパッケージを使えばこの記事で書いたことも実現できますし、それ以上にめんどくさくてこの記事では対応し切れていない以下のような特徴も備えています。

  • 一部のフィールドだけを指定して等価性判定およびハッシュコード算出できる。
  • == と isequal の仕様の違い（主に浮動小数点数周り）にもきちんと対応して的確なコードを生成してくれる。

後者については、例えば 0.0 == -0.0 ですが isequal(0.0, -0.0) === false であり、一方で NaN != NaN ですが isequal(NaN, NaN) === true です。
詳細はそれだけで記事1つ分のネタになりそうなので割愛しますが、この辺りの仕様にもきちんと対応しているなど、十分実用的ですね。

参考

脚注

  1. 参照：Wikipedia(ja): ハッシュ関数 ↩︎

  2. 参照：Wikipedia(ja): ハッシュテーブル ↩︎

  3. Julia に限らず、多くのハッシュテーブル（を利用した辞書やハッシュマップなど）を標準装備している多くの言語でそれに利用するためのハッシュ関数（メソッド）が用意されています。 ↩︎

  4. クラスベースのオブジェクト指向言語だと、全てのクラスの基底クラス（Java なら Object クラス）のメソッドとして isEqual() 系のメソッド（Java なら .equals()）と hash() 系のメソッド（Java なら .hashCode()）が用意されていて、クラスの説明として「継承したクラスで .equals() をオーバーライドしたら .hashCode() も適切にオーバーライドすること！」という説明できれいにコンパクトにまとめられる（のでまだ分かりやすい）のかも。 ↩︎

  5. 拙著 実践Julia入門 第8章「メタプログラミング」内、「8-6. 生成関数」、公式ドキュメントの Generated-functions | Metaprogramming · The Julia Language などを参照。 ↩︎

  6. フィールドの一部が異なっていても等しいと判断してほしい場合（例えば状態（status）を表すフィールドを持っている mutable struct でその状態を等価性の判定材料にしたくない場合）や、逆にフィールドが全部等しくてもそれだけでは等価と判定してほしくない場合などは、この方法が使えないのでご注意。 ↩︎

来栖川電算
来栖川電算Publication

名古屋のAI企業「来栖川電算」の公式publicationです。AI・ML を用いた認識技術・制御技術の研究開発を主軸に事業を展開しています。 公式HP→ kurusugawa.jp/ , 採用情報→ kurusugawa.jp/jobs/

Discussion

HyrodiumHyrodium

これ、だから unique() のヘルプに isequal() への言及だけじゃなくて「hash() も内部で利用している（からユーザ定義型で isequal と hash の定義よろしくね）」的なことまで書かれていないと不親切ですよね…

ドキュメント改善のPR作成しました！

https://github.com/JuliaLang/julia/pull/52159

フィールドの数が多くなると、その都度 hash(a.◯◯, hash(a.△△, hash(a.××, ...))) のようにネストしていくのは面倒になってきます。
私は以下のような半自動的な実装方法を使っています。

AutoHashEquals.jlというパッケージもありますね。

using AutoHashEquals
@auto_hash_equals struct Box{T}
    x::T
end

が

struct Box{T}
    x::T
end
Base.hash(x::Box, h::UInt) = hash(x.x, hash(:Box, h))
Base.(:(==))(a::Box, b::Box) = a.x == b.x
Base.isequal(a::Box, b::Box) = isequal(a.x, b.x)

と等価になるようです。

antimon2antimon2

PRお疲れさまです！
あと情報ありがとうございます！

AutoHashEquals.jlというパッケージもありますね。

知りませんでした。github 見てみましたが「フィールドのコレとコレだけ対象」とか、この記事ではめんどくさいので割愛した == と isequal() の違いとかもケアしたコードを生成したりとか、思いのほか多機能で良いですね。