ハッシュ法の仕組み

データ検索って、魔法みたいに早くできるんです。その仕組み、見ていきましょう。 まずは簡単なクイズから。ホテルのクローク、荷物を一番早く返す方法って何でしょう？ そう、番号札ですよね。実はこの考え方が、すごいアルゴリズムの基本なんです。 この番号札システムこそ、今日お話しするハッシュ法。一体どうなってるんでしょうか。 例えば田中さんというデータを、ある魔法の箱に通してみます。 この魔法の箱が、ハッシュ関数。データからある一つの数字を作り出すんです。 ポンと出てきた「5」という数字。これがハッシュ値。まあいわば、棚番号ですね。 だから田中さんのデータは、即座に5番の棚へ。もう探す必要がないんです。 これがハッシュ法。データ自体から、しまう場所をズバッと計算しちゃうわけです。 じゃあ、一体どれくらい早いのか気になりますよね。 計算量で言うとなんとOの1、O1ですね。これすごいことなんです。 データが10個でも、1億個でも、かかる時間は同じ。文字通り一瞬です。 これって探索アルゴリズムの中ではもう最速、究極のスピードなんです。 でも待ってください。もし佐藤さんも5番になったらどうなるでしょう。 5番の棚はもう田中さんで埋まってる。これは困りましたね。 これを専門用語で「衝突」、つまりコリジョンと呼びます。置き場が被っちゃったんですね。 でも大丈夫。同じ棚にリストで繋げるとか、賢い解決策があるんです。 今日のポイントです。ハッシュ法は超高速だけど衝突が弱点。でも解決策もあるということですね。 この魔法の箱、実はすごく身近な技術なんです。どこで使われているか想像つきますか？