簡単なハッシュ関数
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/02 09:30 UTC 版)
ハッシュ対象のデータが十分に小さいなら、入力データそのものをハッシュ値として使うこともできる(何らかのバイナリを整数として再解釈する)。このような自明なハッシュ関数(恒等関数)の計算コストは事実上ゼロである。 「十分に小さい」の意味は、ハッシュテーブルに割り当てられるメモリ量に依存する。2008年現在、典型的なPCでは1GB程度のメモリが利用可能で、30ビット程度のハッシュ値なら扱える。ただし、多くの場合そこまで大きなハッシュテーブルは必要としない。例えば、英文の文字列の大文字/小文字の変換をするとき、各文字をバイナリ符号化したものを使い、その文字符号を整数のインデックスとしてテーブルを参照すると対応する変換後の文字符号が得られるようにするという方法が考えられる(例えば、'A' には 'a'、'8' には '8' を返すなど)。それぞれの文字が8ビットで表されていれば(ASCIIまたはISO Latin 1)、テーブルのエントリ数は 28 = 256 個だけとなるし、Unicodeの場合でも 17×216 = 1114112 エントリである。 同じ技法は 'us' とか 'ja' のような2文字国名コードを実際の国名にマッピングする場合(262=676 エントリ)、アメリカの5桁の郵便番号を地名にマッピングする場合(10万エントリ)などに利用できる。不正なデータ値(例えば国名コードなら 'xx'、ZIPコードなら 00000)に対応するエントリは未定義とされたり、何らかの 'null' 値にマッピングすることになるだろう。
※この「簡単なハッシュ関数」の解説は、「ハッシュ関数」の解説の一部です。
「簡単なハッシュ関数」を含む「ハッシュ関数」の記事については、「ハッシュ関数」の概要を参照ください。
- 簡単なハッシュ関数のページへのリンク