ハッシュテーブル(hash table)と言う有名なアルゴリズムがあって、社内のJava研修で実装してもらっています。
ハッシュと言う言葉は今ではどなたでもご存知だと思います。あのハッシュタグのハッシュと同じ語源です。
このアルゴリズムは検索性能において最速なので、システムの高速化にとってすごく重要です。
仕組みは割と簡単で、
■検索対象の値を格納する時
- 検索対象の値(例えば文字列)を切り刻ん(hash)で数値化する。
- その数値を配列(テーブルと言います)の添え字(インデックス)として使って格納する。
■検索する時
- 検索対象の値(例えば文字列)を切り刻んで数値化する。
- 配列内のその数値を添え字とする箱から取り出す。
なぜ高速なのかと言うと、切り刻んだ値を計算するだけで配列内の場所を特定する事が出来、箱の中を1つ1つ探す必要が無いからです。
文字列を値として格納する場合、例えば「ABC」という文字列を切り刻んでそれぞれの文字を数値化します。
A→68、B→69、C→70 (全ての文字にはあらかじめ数値が割り当てられています)
そしてこれらを足します。68+69+70= 207
最後に配列上の207番目にABCという文字を入れます。★1
面白いのはここからなんですが、「CBA」も同じ207になってしまいますよね?
同じ箱の中に2つの文字列は入れられないので困ってしまいます。これを競合と言います。
この競合回避策として「素数」を使います。★2
数値を計算する過程で素数を掛けてあげます。
そうするとABCの数値とCBAの数値が別のものになって別の箱に入れることができます。
値が重なりにくくなるという素数の性質はインターネットのセキュリティにも利用されているので興味のある人は調べてみて下さい。
★1 実際には、207を配列の要素数で割った余りを添え字にします。
★2 正確に言うと競合の回避策ではなく「軽減策」ですが、回避策が気になる人は調べてみてください。
※ちなみにハッシュドビーフ(hashed beef)も同じ語源です。