gallu’s blog

エンジニアでゲーマーで講師で占い師なおいちゃんのブログです。

ハッシュへの考察:検索手法としてのハッシュ

なにもない一番初めからいきましょう。
まだすべてが混沌だったころに神様が矛を持たれてその混沌を混ぜると………ってまて。前すぎ。


コンピュータが出てきてからまぁ「人間じゃシャレにならん大量のデータを扱うのに便利」って発想は割合に早くからありまして。
大量のデータで一つ重要な要素は「検索」です。図書館ですと、司書の方とかが魔法のような手さばきでありえない速度の検索をやっている、あんな感じです。
基本は「頭からデータ嘗め回して見つけたら"君だ〜"とか叫ぶ」感じなのですが。こういうのを「線形検索」とか呼称します。


問題がありまして。単純に「力技なので時間が掛かる」です。データ量が少なけりゃよいのですが、多いと大変な目にあいます*1
大変なときには何か考える。必要は発明の母と申します。
一つには「Bツリー(Balanced tree)」ってのがあるのですがおいといて*2


大雑把に考えて。データを「全部嘗め回す」から時間がかかるのです。んじゃぁ「データをいくつかのグループに分ければ」問題は解決すると思いませんか?
これがハッシュ(「ハッシュ法(hashing)」って言い回しが多いですねぇ)の根幹たる発想です。
例えば。データを10のグループにわければ、理論上は「全体を嘗め回す1/10の労力」でいけます。100のグループなら1/100。すばらしい。
問題は「データとグループとを結びつける必要」があるのですが。これにテーブルを用意したんじゃ意味ありません。当たり前ですね。「グループを探すためにデータ全部に対して線形検索が必要」になっちゃいますから。


幸い。コンピュータは「計算機」です。んじゃ計算でなんか出てくりゃ按配よかんべ、ってのがここから連なる発想になります。
ここで、ちょっと格好よく専門用語を出してみると。
ハッシュ関数っていう「計算してくれるhogehoge」を用意しまして。こいつにデータを食わせると「ハッシュ値(又はハッシュキー)」と呼称される「グループ名」が出てきます、って感じの流れを作っちゃうんですね。


ハッシュ値ハッシュ関数(でぇた);


こんなイメージ。
これが「ハッシュ」と呼ばれるものの大元になります。
この辺を踏まえて、あちこちのハッシュ関数の定義を少し見てみましょう。

あるデータが与えられた場合にそのデータを代表する数値を得る操作、又は、その様な数値を得るための関数(ハッシュ関数)のこと。またハッシュ関数から得られた数値そのもの(ハッシュ値)のことをハッシュということもある。

ドキュメントや数字などの文字列の羅列から一定長のデータに要約するための関数・手順のことをハッシュ関数という。関数を通して出力される値は、「ハッシュ値」、または単に「ハッシュ」と呼ぶ。

データベース処理などで、ハッシュ法による検索処理を実現する際に、レコードの検索を高速に行なえるようなキー(ハッシュキー)を作成するのに使用する処理。ハッシュ関数で得られたキーからハッシュテーブルを参照して、検索対象を高速に得ることができる。

与えられた原文から固定長の疑似乱数を生成する演算手法。生成した値は「ハッシュ値」と呼ばれる。

データ(キー値)をある関数で変換し、格納する場所を直接決め、そこにデータを格納する。この関数のことをハッシュ関数とよぶ。

ハッシュ関数(はっしゅかんすう、hash function)とは、もとのデータからある一定範囲の数値を生成する関数である。理想的には、異なったデータからは常に異なったハッシュ値が得られることが望ましいが(完全ハッシュ関数)、多くの場合それは困難である。

概ね腑に落ちるのではないでしょうか?
ハッシュとは「検索を高速に行うために必要な色々」である、というのがここまでの定義になります。


さてはて。鍵は出来ましたが。ではどんな風に実際のデータを格納していくのでしょう?

*1:ちなみに某サイトには「データ量が1000を越えたら,線形表よりも効率のよい方法を考えたほうがよい」とありました。検証はしていないのですが参考として記述しておきます。

*2:とあるサイトによると「各種のツリー構造とは異なり、静的な配列だけで簡単に実装でき、効率も極めて高い。このため、非常に実用的な手法として重宝である。」だそうです。