longのハッシュコード

programming C#

longのハッシュコードにヤられたー。

いやまあ、分かってみれば当たり前のことで単に僕が無知でしたってだけの話ではあるのだけれど、long値（64bit整数）の GetHashCode() が何を返すか僕は知らなかったわけで、そのせいで Dictionary の検索がめちゃくちゃ遅くなるという失敗をやらかしたのだ。

long lo = 123;  // 下位ビット
long hi = 456;  // 上位ビット
long key = lo | (hi << 32);  // lo と hi を合成して 64bit 整数を生成
System.Console.WriteLine( "key.GetHashCode() = {0}", key.GetHashCode() );
System.Console.WriteLine( "lo ^ hi = {0}", lo ^ hi );  // lo と hi の XOR

これを実行するとどちらの WriteLine も 435 を出力する。要するに、long のハッシュコードは下位32bitと上位32bitのXORなんですな。僕の失敗はこの特性を考慮しないでDictionaryのキーを設計してしまったこと。アホな設計のせいでハッシュコードが重複しまくりでさっぱりパフォーマンスが出なかったというわけだ。

僕がやりたかったのは、2つのint型（32bit整数）をペアにしたものをキーとするようなDictionaryを作ることだった。それなら2つのintを合成したlong値をキーにすりゃいいじゃん、というわけで次のような関数を作ってその戻り値をキーにしたのだ。

static long MakePair( long a, long b )
{
  return (a < b) ? (a << 32) | b : (b << 32) | a;
}

ところが、ペアにする「2つの32bit整数」というのが単にカウントアップされていくだけのインデックス値だったわけで、もちろんshortには収まりきらない値まで使用する可能性があったから32bit整数と言っているのだけれども、そうはいっても32bitをフルに使用するケースは少ないのだから上位ビットは単に0で埋められているだけという可能性が高い。これを踏まえた上で上記関数で生成されるlong値を考えてみると、そのハッシュコードはあまりにも効率が悪いことがわかる。
結局、MakePair()関数を次のように書き換えて問題は解決したのであった。

static long MakePair( long id1, long id2 )
{
  if ( id1 > id2 ) Swap( ref id1, ref id2 );
  long lo1 = id1 & 0x0000ffff;
  long hi1 = id1 & 0xffff0000;
  long lo2 = id2 & 0x0000ffff;
  long hi2 = id2 & 0xffff0000;
  return lo1 | (lo2 << 16) | (hi1 << 16) | (hi2 << 32);
}