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

C#
ERROR: The request could not be satisfied
atcoder.jp

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

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

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

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

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

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

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

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

ERROR: The request could not be satisfied
atcoder.jp

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

GetHashCode()が遅い

Reference Source
referencesource.microsoft.com

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