2026-09-28
Buckets.hs
import Data.Bits (countTrailingZeros)
registers :: Int -> [Int] -> [Int]
registers m hs =
[ maximum (0 : [rank (h `div` m) | h <- hs, h `rem` m == i])
| i <- [0 .. m - 1]
]
where
rank w = countTrailingZeros w + 1
ハッシュ値の並び hs を m 個のバケットに振り分け、バケットごとに rank の最大値を記録する registers です。ハッシュ値は負になることもあります。print (registers 4 [6, -7, 5]) はいま [0,1,1,0] を出力しますが、本来は [0,2,1,0] です。どこを直せばよいでしょうか?
Answer
h `rem` m == i を h `mod` m == i に変えます。
rem の結果は割られる数と同じ符号になるので、(-7) `rem` 4 は -3 です。i は 0 から 3 までしか動かないので、-7 はどのバケットの内包表記にも拾われず、エラーも出ないまま消えます。mod の結果は割る数と同じ符号になり、(-7) `mod` 4 は 1 です。
rank に渡す商には div を使っているので、組にすべきなのも mod です。div は負の無限大の方向に丸めるので (-7) `div` 4 は -2 になり、-2 * 4 + 1 で元の -7 に戻ります。rem と組になるのは0の方向に丸める quot で、div と rem を混ぜると h の分け方として辻褄が合いません。
直すと -7 はバケット1に入ります。商の -2 は2の補数で表すと末尾に 0 が1個並ぶので rank は 2 です。バケット1にはもう1つ 5 から rank 1 が来ていて、最大値の 2 が残ります。