x << 32 + yをハッシュキーにして速度が悪化した話

C#
Submission #4543737 - AtCoder Beginner Contest 045
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

AtCoderの過去問をやっていて、なぜかO(1)で計算量的には問題がないはずなのにDictionaryでTLEになるケースがありました。

Dictionaryで速度が問題になる原因は二種類あります

  • ハッシュキーが衝突している
  • GetHashCode()が遅い

ハッシュキーが衝突している

[C#] (long)x
結論 (long)x
yuinore.net

今回のケースはこの記事の通りです。テストケースによっては衝突しやすいハッシュキーが作られてしまいパフォーマンスが悪化します。今回は最大で10倍程度遅くなりました。

ハッシュテーブル - Wikipedia
ja.wikipedia.org

ハッシュキーが衝突するとパフォーマンスが悪化する理由はこちら。ざっくり言うと、衝突したら衝突しなくなるまで番地を探し続けるためです。

Submission #4544120 - AtCoder Beginner Contest 045
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

そのためハッシュキーを衝突しないように工夫するとパフォーマンスが改善されます。

GetHashCode()が遅い

Reference Source
referencesource.microsoft.com

普通の関数ですので実装次第では決して速くはないです。string.GethashCode()は文字列の長さに依りますね。（とはいえ現実のソフトウェア開発でここがボトルネックになることは、ほぼないです。