コラム
2025/05/28
プログラミングについて 第１１0回目
『ハッシュ法 その１』
プログラムのアルゴリズムの本などを見ていると、ときどきハッシュ法という変な名前のアルゴリズムが出てきます。その変なアルゴリズムの説明を読んでもなんだか意味のない関数とかが書かれていて、それとどういう関係があるのかなどと考えているうちに『ハッシュ法なんて分からなくてもいいや！』とあきらめる方も多いと思います。
実は私もそうでした。
ハッシュ法とはＨａｓｈという単語から連想しても想像がつく様に、細切れにするとか、ごちゃ混ぜにするというところから命名されたアルゴリズムなのだと思います。もともとこのハッシュ法はデータの検索を高速に行なうことを目的として考え出されたアルゴリズムです。
データを高速に検索するには、これまでにお話しした方法では、２分木構造や、ソートしておいて検索する方法など、どちらかと言えば規則的に並べてから行なうものが殆どでした。
ハッシュ法はある規則に従ってデータを配置させるのですが、その規則というのは昇順とか降順とかという規則ではなく、もっと規則的にグチャグチャに並べることで検索を高速にしようとするものです。
このように説明すると、いい加減なアルゴリズムの様ですが、なかなか考えさせられるものがあります。
例えば次の様な文字列があったとします。
a
ab
abc
abcd
abcde
abcdef
abcdefg
もしこの文字列を単純に２分木構造で表現すると、
a
└┐
ab
└┐
abc
└┐
abcd
└┐
abcde
└┐
abcdef
└┐
abcdefg
となって２分木としては最悪の形状になってしまい、abcdefg を検索するには通常のリストを検索するのと変わらなくなってしまいます。この様な一様な規則では整列させず、別の規則で整列（整列とは言えませんが）させようというのがハッシュ法です。
下のプログラム例を見て下さい。
#include <stdio.h>
#define MAX_TABLE 21
char *table[MAX_TABLE]; /* ハッシュテーブル */
main()
{
char *name[]={
"a",
"ab",
"abc",
"abcd",
"abcde",
"abcdef",
"abcdefg",NULL};
int i;
for(i=0;i<MAX_TABLE;i++)table[i]=NULL; /* ハッシュテーブルの初期化 */
for(i=0;name[i];i++)add(name[i]); /* ハッシュテーブルへの文字列の
登録 */
/* ハッシュテーブルの内容の表示 */
for(i=0;i<MAX_TABLE;i++){
if(table[i])printf("%3d %s\n",i,table[i]);
}
}
add(name)
char *name;
{
char *s;
int v;
/* 文字列を１バイトの符号なし整数
と考え、各文字の数の合計を得る */
v=0;
s=name;
while(*s){
v+=(unsigned char)*s;
s++;
}
v%=MAX_TABLE; /* 得られた合計をテーブルの要素数
で割った剰余を得る */
table[v]=name; /* 得られた結果をテーブルの要素イン
デックス番号と考え、文字列を登録
する */
}
非常に簡単なハッシュ法の例です。このプログラムの内容そのものは難しいものではありませんが、肝心なところは関数 add の内容です。先に結果を見てみると、
0 abc
6 ab
7 abcdefg
9 abcdef
12 abcde
13 a
16 abcd
となり、各文字列がバラバラにテーブルに登録されているのが分かると思います。
そもそもハッシュ法はデータを何らかの方法で出来る限り一様に分散する整数値を算出し、それを配列の要素インデックスとする方法なのです。上の関数 add では文字列の各文字の値を合計して、テーブルの要素数の剰余を得る事でそれを実現しています。
ですので、上の方法では文字列 abc は必ず０番目、abcdef は９番目の要素になるので、検索を行なうときにはテーブルに登録した方法と同様の計算を行い、要素番号を取得すればいいことになりますので、検索が高速になることが理解できると思います。
このような一様に分散する整数値を生成する関数（この例の場合は関数 add 内の文字列の値の合計と剰余を得る部分）をハッシュ関数と呼びます。ハッシュ関数は今回の例では単純に文字列の値の合計をテーブルの要素数の剰余を求めましたが、値が一意に決定でき、テーブルの要素数以内の一様に分散するようなものであればどのようなものでも構いません。
ここまでは理想の話しです。実は上のプログラムには欠点があるのです。テーブルに登録した文字列が、たまたま運良くテーブルに登録されているだけなのです。上の計算方法は単純な加算ですので文字列の値の合計は、
abc
cba
cab
acb
のいずれも同じ値になってしまうのです。ですので、上のプログラムではテーブルの内容が上書きされてしまい、正常なテーブルが生成されません。これを回避するには、１つは文字列の値の合計を算出する方法を変えるか、既にテーブルに登録されていたときには次の登録場所を計算する別のハッシュ関数を用意することです。
後者の方法で試してみましょう。テーブルに登録する文字列は、
char *name[]={
"abc",
"acb",
"bac",
"bca",
"cab",
"cba",NULL};
にし、関数 add を、
add(name)
char *name;
{
char *s;
int v;
v=0;
s=name;
while(*s){
v+=(unsigned char)*s;
s++;
}
while(1){
v%=MAX_TABLE;
if(!table[v]){
table[v]=name ;
break;
}
else{
printf("%d\n",v);
v=v+(v/2+1)*11;
}
}
}
として実行してみると結果は次の様になりました。
0 abc
2 cab
3 cba
11 acb
14 bac
18 bca
上の例での第２、第３のテーブルの要素インデックスを得るのは、
v=v+(v/2+1)*11;
（実際には、v=(v+(v/2+1)*11)%MAX_TABLE; です。）
という単純な式です。どうしてこのような式を作ったかと言われても正確なことは説明することができないのですが、一様にでたらめな数値を算出する式にしてみただけのことなのです。実は、11 を 9 や 8 にすると同じ数値が循環してしまい無限ループになってしまい、たまたま 11 でうまくいっただけのことなのです。
このような第２、第３...のハッシュ関数の値はテーブルの空き要素が少なくなってくると、数値が循環したり、空きを発見するために多くの計算をしなければならなくなってしまいます。ですので、ハッシュ法を使用するときにはハッシュテーブルの要素数は十分大きくしなければなりません。
実際のプログラムではハッシュ法だけで効率良く検索を行なおうとすると、上述で説明した様に大きなハッシュテーブルを用意しなければならず、メモリーの無駄が生じてしまいます。ですので、通常はハッシュ法のみではなく、他の方法と組み合わせてプログラムを作るのが一般的です。例えば、ハッシュ法でおおざっぱに分類しておき、同一のハッシュ値になるデータを２分木構造で表現するといった作り方をします。この場合、
ハッシュテーブル ０ １ ２ ３ ４ ５ ６ ７ ８ ９
│ │
２分木 abc opq
┌┴┐ ┌┴┐
ab def qewr zser
┌┴┐ ┌┴┐
という感じの構造になります。
次回はこのハッシュ法と２分木を組み合わせた例を紹介する予定です。
第110回 プログラミングについて『ハッシュ法 その1』
プログラミングについて 第１１0回目
『ハッシュ法 その１』
プログラムのアルゴリズムの本などを見ていると、ときどきハッシュ法という変な名前のアルゴリズムが出てきます。その変なアルゴリズムの説明を読んでもなんだか意味のない関数とかが書かれていて、それとどういう関係があるのかなどと考えているうちに『ハッシュ法なんて分からなくてもいいや！』とあきらめる方も多いと思います。
実は私もそうでした。
ハッシュ法とはＨａｓｈという単語から連想しても想像がつく様に、細切れにするとか、ごちゃ混ぜにするというところから命名されたアルゴリズムなのだと思います。もともとこのハッシュ法はデータの検索を高速に行なうことを目的として考え出されたアルゴリズムです。
データを高速に検索するには、これまでにお話しした方法では、２分木構造や、ソートしておいて検索する方法など、どちらかと言えば規則的に並べてから行なうものが殆どでした。
ハッシュ法はある規則に従ってデータを配置させるのですが、その規則というのは昇順とか降順とかという規則ではなく、もっと規則的にグチャグチャに並べることで検索を高速にしようとするものです。
このように説明すると、いい加減なアルゴリズムの様ですが、なかなか考えさせられるものがあります。
例えば次の様な文字列があったとします。
a
ab
abc
abcd
abcde
abcdef
abcdefg
もしこの文字列を単純に２分木構造で表現すると、
a
└┐
ab
└┐
abc
└┐
abcd
└┐
abcde
└┐
abcdef
└┐
abcdefg
となって２分木としては最悪の形状になってしまい、abcdefg を検索するには通常のリストを検索するのと変わらなくなってしまいます。この様な一様な規則では整列させず、別の規則で整列（整列とは言えませんが）させようというのがハッシュ法です。
下のプログラム例を見て下さい。
#include <stdio.h>
#define MAX_TABLE 21
char *table[MAX_TABLE]; /* ハッシュテーブル */
main()
{
char *name[]={
"a",
"ab",
"abc",
"abcd",
"abcde",
"abcdef",
"abcdefg",NULL};
int i;
for(i=0;i<MAX_TABLE;i++)table[i]=NULL; /* ハッシュテーブルの初期化 */
for(i=0;name[i];i++)add(name[i]); /* ハッシュテーブルへの文字列の
登録 */
/* ハッシュテーブルの内容の表示 */
for(i=0;i<MAX_TABLE;i++){
if(table[i])printf("%3d %s\n",i,table[i]);
}
}
add(name)
char *name;
{
char *s;
int v;
/* 文字列を１バイトの符号なし整数
と考え、各文字の数の合計を得る */
v=0;
s=name;
while(*s){
v+=(unsigned char)*s;
s++;
}
v%=MAX_TABLE; /* 得られた合計をテーブルの要素数
で割った剰余を得る */
table[v]=name; /* 得られた結果をテーブルの要素イン
デックス番号と考え、文字列を登録
する */
}
非常に簡単なハッシュ法の例です。このプログラムの内容そのものは難しいものではありませんが、肝心なところは関数 add の内容です。先に結果を見てみると、
0 abc
6 ab
7 abcdefg
9 abcdef
12 abcde
13 a
16 abcd
となり、各文字列がバラバラにテーブルに登録されているのが分かると思います。
そもそもハッシュ法はデータを何らかの方法で出来る限り一様に分散する整数値を算出し、それを配列の要素インデックスとする方法なのです。上の関数 add では文字列の各文字の値を合計して、テーブルの要素数の剰余を得る事でそれを実現しています。
ですので、上の方法では文字列 abc は必ず０番目、abcdef は９番目の要素になるので、検索を行なうときにはテーブルに登録した方法と同様の計算を行い、要素番号を取得すればいいことになりますので、検索が高速になることが理解できると思います。
このような一様に分散する整数値を生成する関数（この例の場合は関数 add 内の文字列の値の合計と剰余を得る部分）をハッシュ関数と呼びます。ハッシュ関数は今回の例では単純に文字列の値の合計をテーブルの要素数の剰余を求めましたが、値が一意に決定でき、テーブルの要素数以内の一様に分散するようなものであればどのようなものでも構いません。
ここまでは理想の話しです。実は上のプログラムには欠点があるのです。テーブルに登録した文字列が、たまたま運良くテーブルに登録されているだけなのです。上の計算方法は単純な加算ですので文字列の値の合計は、
abc
cba
cab
acb
のいずれも同じ値になってしまうのです。ですので、上のプログラムではテーブルの内容が上書きされてしまい、正常なテーブルが生成されません。これを回避するには、１つは文字列の値の合計を算出する方法を変えるか、既にテーブルに登録されていたときには次の登録場所を計算する別のハッシュ関数を用意することです。
後者の方法で試してみましょう。テーブルに登録する文字列は、
char *name[]={
"abc",
"acb",
"bac",
"bca",
"cab",
"cba",NULL};
にし、関数 add を、
add(name)
char *name;
{
char *s;
int v;
v=0;
s=name;
while(*s){
v+=(unsigned char)*s;
s++;
}
while(1){
v%=MAX_TABLE;
if(!table[v]){
table[v]=name ;
break;
}
else{
printf("%d\n",v);
v=v+(v/2+1)*11;
}
}
}
として実行してみると結果は次の様になりました。
0 abc
2 cab
3 cba
11 acb
14 bac
18 bca
上の例での第２、第３のテーブルの要素インデックスを得るのは、
v=v+(v/2+1)*11;
（実際には、v=(v+(v/2+1)*11)%MAX_TABLE; です。）
という単純な式です。どうしてこのような式を作ったかと言われても正確なことは説明することができないのですが、一様にでたらめな数値を算出する式にしてみただけのことなのです。実は、11 を 9 や 8 にすると同じ数値が循環してしまい無限ループになってしまい、たまたま 11 でうまくいっただけのことなのです。
このような第２、第３...のハッシュ関数の値はテーブルの空き要素が少なくなってくると、数値が循環したり、空きを発見するために多くの計算をしなければならなくなってしまいます。ですので、ハッシュ法を使用するときにはハッシュテーブルの要素数は十分大きくしなければなりません。
実際のプログラムではハッシュ法だけで効率良く検索を行なおうとすると、上述で説明した様に大きなハッシュテーブルを用意しなければならず、メモリーの無駄が生じてしまいます。ですので、通常はハッシュ法のみではなく、他の方法と組み合わせてプログラムを作るのが一般的です。例えば、ハッシュ法でおおざっぱに分類しておき、同一のハッシュ値になるデータを２分木構造で表現するといった作り方をします。この場合、
ハッシュテーブル ０ １ ２ ３ ４ ５ ６ ７ ８ ９
│ │
２分木 abc opq
┌┴┐ ┌┴┐
ab def qewr zser
┌┴┐ ┌┴┐
という感じの構造になります。
次回はこのハッシュ法と２分木を組み合わせた例を紹介する予定です。
