乗算ハッシュ法の実装がなぜそのように実装されるのか理解できません

前提・実現したいこと

プログラミングの初心者で、データ構造について勉強しています。
「Open Data Structures」の、オープンソース版 PDF ファイルの疑似コード版を読み、Go で実装して翻訳者様のリポジトリで答え合わせをしています。

PDF で説明されている「乗算ハッシュ法」の実装時に、mod 2^w が省略されても良い理由が理解できませんので、その理由を教えていただきたいです。

該当のソースコード

PDF の 5.1.1 で、乗算ハッシュ法の計算方法が以下の通り説明されています。

hash(x) = ((z * x) mod 2^w) div 2^(w−d)

ここで、 z は奇数の集合 {1, 3, 5, . . . , 2^(w − 1)} からランダムに選択する。
整数のビット数を w とするとき、整数の演算の結果は 2^w を法として合同になることを思い出すと、このハッシュ関数の効率がとても良いことがわかる（図 5.2 参照）。
しかも、 2^(w−d) による整数の割り算は、二進法で右側の w − d ビットを落とせば計算できる（ビットを右に w − d 個だけシフトすればよいので、実装は上の式よりも単純になる）。

そして、乗算ハッシュ法の実装方法は疑似コード版では以下と記載されています。上記引用の通り、div 2^(w-d) がシフト演算で実装されています。

pseudocode
1hash(x)
2  return ((z * hash(x)) mod 2^w) >> (w − d)

ところが、C++ 版や、Java 版、翻訳者様の Go 版のリポジトリでは以下の通り、mod 2^w が省略されて実装されています。
冒頭でお尋ねした通り、なぜ mod 2^w を省略して実装して良いのか、理由を教えていただきたいです。

C++
1int hash(T x) {
2    return ((unsigned)(z * hashCode(x))) >> (w-d);

Java
1int hash(Object x) {
2    return (z * x.hashCode()) >>> (w-d);
3}

Go
1func (cht *ChainedHashTable) hash(x utils.V) uint64 {
2    return (cht.z * uint64(x)) >> (64 - cht.d)
3}

試したこと

teratail を「乗算ハッシュ法」で検索しましたが、関連のある質問は見つけられませんでした。

PDF の 5.1.1 の続きで、図 5.2 に w = 32, d = 8, z = 4102541685, x = 42 とした例があります。mod 2^w の有無で計算結果に違いがあるか、確認しました (The Go Playground)。あたりまえですが、mod 2^w の有無で計算結果は違いました。
計算結果に違いがあるということは、PDF で説明されている乗算ハッシュ法を正しく実装できていないと考えました。しかし、それは所詮素人の発想であって、何か mod 2^w が省略されても良い理由がちゃんとあるのではないか、と考えています。

行動規範の内容に同意します

回答3件

ベストアンサー

何か mod 2^w が省略されても良い理由がちゃんとあるのではないか

はい、C++の符号なし整数の演算やJavaの整数演算は、範囲をあふれた場合もとからmod 2^wとして計算するようになっています。

投稿2021/06/08 07:15

maisumakun

総合スコア145183

maisumakun

2021/06/08 07:17

引用文中の「整数の演算の結果は 2^w を法として合同になる」というのは、そういう意味です。

synydy

2021/06/08 13:41 編集

// コメントに Markdown 記法が利用できないようなので、Markdown 記法をやめたものに修正しました。 > C++の符号なし整数の演算やJavaの整数演算は、範囲をあふれた場合もとからmod 2^wとして計算するようになっています。「符号なし整数オーバーフロー剰余」で検索して、ラップアラウンドという概念を知りました。最終的に「符号なし整数ラップラウンド剰余」で検索して、IPA の PDF（https://www.ipa.go.jp/files/000045165.pdf#page=4）に行き当たりました。 > たとえば符号なし 8 ビットの変数で、演算結果が 257 になった場合、8 ビットの変数で表現できる最大値 255 に 1 を加えた 256 による剰余である 1 が演算結果となります。このような動作をラップアラウンドと言います。 Go で恐縮ですが「uint8 型の変数に 255 を入れて 2 回インクリメントした値」と「int 型の変数に 257 を入れて mod 2^8 した値」が同じになることで、Go でも符号なし整数のオーバーフローはラップアラウンドすること、mod 2^w で表現できることを確認しました（https://play.golang.org/p/46KLLWpTR4Z）。上記は「C++ や Java は符号なし整数の演算結果がオーバーフローを起こすと、ラップアラウンドが発生する」と同じ意味と理解しました。 > 引用文中の「整数の演算の結果は 2^w を法として合同になる」というのは、そういう意味です。ありがとうございます。理解できました。・テキストにある乗算ハッシュ法（hash(x) = ((z * x) mod 2^w) div 2^(w−d)）は、ラップアラウンドを考慮した記載になっていた。・そのことをテキストでは「整数の演算の結果は 2^w を法として合同になる」で説明していた。・C++、Java、あるいは、Go で実装する場合は、プログラミング言語側でラップアラウンドが行われるので、mod 2^w が消えた。ということですね。

行動規範の内容に同意します