ハッシュテーブル とは？

「田中」という名前を探すとき、普通の方法は全員のリストを先頭から確認する。ハッシュテーブルは「田中」という文字を計算して「この棚の番号」を一発で出し、その棚に直接取りに行く。だから1件でも100万件でも検索時間がほぼ変わらないんだ。

そうだよ。Pythonのdictはハッシュテーブルで実装されているから「dict['key']」で値を取り出すのがO(1)で速い。JavaScriptのオブジェクトやMapも同様。日常的に使っているデータ構造がハッシュテーブルだったりするんだ。

異なるキーを計算したら同じ棚番号になってしまうことを衝突（コリジョン）という。棚が一つしかないのに二つのものを入れようとする問題だよ。「チェイニング（リストで繋ぐ）」や「オープンアドレス法（別の空き棚を探す）」で解決する。衝突が多くなると速度が落ちるから、ハッシュ関数の設計が重要なんだ。

データの順序が保持されないこと。「最初に入れた要素」「最後に入れた要素」を取り出したいならハッシュテーブルでは難しい。Pythonのdictは3.7以降挿入順序を保持するようになったけど、これは実装の工夫であってハッシュテーブル本来の性質ではないんだ。順序が必要ならLinkedHashMap（Java）やOrderedDict（Python）を使うよ。

あるよ。ハッシュ衝突攻撃（Hash DoS）といって、意図的に同じハッシュ値になるキーを大量に送り込むと、衝突が連鎖してO(1)のはずがO(n)に劣化してサーバーが極端に遅くなる。2011年に多くのWebフレームワークで問題になって、以降はランダム化ハッシュ（起動ごとにハッシュ関数のシードを変える）が標準的な対策として導入されたんだ。