複数のHash値の合成

くまぎ @kumagi

複数のハッシュ値を合成するときって掛け算したら偶数に偏りそうだし引き算やxorしたら2つの物が一致したときに0になるパターンが多すぎて偏るし足し算が妥当なのかしら…。

tomo🐧@learning @cocoatomo

@kumagi java のオブジェクトだと, 各フィールドの hash 値を h_i (i=0, 1,...) と置いたときに Σ h_i*31^i を int にキャストしたものを採用してます. ref: Effective Java

tomo🐧@learning @cocoatomo

@kumagi 31ってマジックナンバーは素数が良いんだそうな. [要出典] 31 = 2^5 - 1 で shl と - で計算できるので計算機にも優しいから採用されてるそうです. 同じ理由で 127 を採用する流儀もあります.

tomo🐧@learning @cocoatomo

@kumagi OpenJDK の java.lang.String#hashCode の実装. L.1494 です. http://t.co/xgf7mwk

うんこ💩HIZA💩ペンギン @NetPenguin

参考までに。Eclipseで生成させると、31足してxorみたいなのだった気がする。RT @kumagi: 複数のハッシュ値を合成するときって掛け算したら偶数に偏りそうだし引き算やxorしたら2つの物が一致したときに0になるパターンが多すぎて偏るし足し算が妥当なのかしら…。

うんこ💩HIZA💩ペンギン @NetPenguin

@kumagi javaでめんどくさそうな部分は大体サポートしている気がします。フィールドからequalsメソッドとhashCodeメソッドを生成とか。

tomo🐧@learning @cocoatomo

@kumagi @netpenguin hashCode と equals の整合性を取らないといけないので, 同時に両方生成してくれます. ちなみにデフォルトは 31 掛けて足すの繰り返し, ですよ. http://t.co/1kVBGqY

うんこ💩HIZA💩ペンギン @NetPenguin

@cocoatomo @kumagi ハッシュ系のコレクションに突っ込む事を考えた場合に必須ですものね。31掛けてから足すでしたか。勘違いしてました(汗。指摘ありがとうございます！！