高速にデータを挿入、検索、削除、更新を行う手段に使われるのがハッシュ法である。 大抵のプログラムには備わっているので、通常はそれを使えばよい。
地図システムのように、データはシンプルであるがデータ量が膨大な場合には 汎用的なクラスライブラリでは対応できないことがある。
ハッシュ法ではハッシュ値のぶつかりを避ける方法として、チェインを作る方法と オープンアドレス法が知られている[1]。
前者の方がやや高度で、削除ではチェインの繋ぎ変えも必要となり、管理用のメモリもいる。
後者もなるべくぶつかりを避けようとすると、プログラムが複雑になる。
しかし、ぶつかりを覚悟すれば実装はシンプルである。 シンプルであるがゆえに、少々ぶつかりがあっても、パフォーマンスがよいことを経験している。
ハッシュ値としては、空きと削除の二つ分の数値は使えない。
自分がよく使うハッシュ関数を下に示す。 実際には、ハッシュサイズ(HASHSIZE) はもっと大きな値を使うが、 ここでは説明のために小さな値としている。
下のプログラムでは、"abs", "atof" など12個の関数名について、 ハッシュ値（ハッシュ関数で得られた値）を求めている。
#include <stdio.h>
#define HASHSIZE 19
// 素数 ... , 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61
char *func[] = {
"abs", "atof", "atoi", "atol", "close", "feof",
"fgetc", "fgets", "fopen", "fputc", "fputs", "free"
};
int hash(char *key) {
int n, h = 0;
for (n = 0; key[n] != '\0'; n++) {
h = (h * 137 + key[n]) % HASHSIZE;
}
return h;
}
int main() {
int n;
printf("HASHSIZE = %d\n", HASHSIZE);
for (n = 0; n < sizeof(func)/sizeof(char*); n++) {
printf("%-6s", func[n]);
}
printf("\n");
for (n = 0; n < sizeof(func)/sizeof(char*); n++) {
printf(" %2d ", hash(func[n]));
}
}
実行結果を下に示す。
HASHSIZE = 19 abs atof atoi atol close feof fgetc fgets fopen fputc fputs free 7 3 6 9 13 7 18 15 11 14 11 3
ハッシュ法による文字列管理では、ハッシュサイズに等しい要素数を持つ配列が用いられる。 例えば "abs" のハッシュ値は7であるから、下図に示すように、 第7番目（先頭が第0番目）の配列要素にそのアドレスが格納される。 "atof"、"atoi" と順に割り当てていく。 "feof" の番になると、第7番目の要素は既に割り当て済みなので、配列の添え字を進めて、 未割り当て要素を探す。 この例では、直ぐ隣が空きであったため、"feof"には第8番目の要素が割り当てられる。 同様に、"fputs"、"free" も本来のハッシュ値とは違う場所が割り当てられる。
ある文字列例えば "feof" が登録されているかどうかを調べるには、 "feof"のハッシュ値が 7 であるから、もし、第7要素が空きであれば、登録されていないことになる。 何らかの文字列が登録されていたら、この文字列と "feof" を比較する。 もし、一致すれば登録されていたことになる。一致しなかった場合、配列の添え字を先に進めて、 ここが空きなら、"feof" は登録されていないことが確定する。 何らかの文字列が登録されていた場合は前と同じ処理を繰り返す。 なお、添え字が配列の末尾まで達したら、 配列の先頭に戻って同じことを行う。
衝突により、本来の場所と異なる位置に登録されることがあるため、 文字列の比較は２回以上になるケースもあるが、衝突がなければ、文字列の比較は精々１回で済む。
以上のように、ハッシュ法は登録処理も検索処理も非常に高速に行われるため、 広く使われる技術である。 ハッシュ表に格納するのは、文字列とは限らず、数値とか構造体データなど、どのようなデータでもよい。
なるべく衝突を減らすためには、ハッシュ表のサイズは、 登録する文字列の個数に比べて、十分に余裕を持たせることが必要である。 また、HASHSIZEはきりのいい数字にせず、素数にした方がよい。 このハッシュ関数では 137 という中途半端な数値が使われているが、 これもなるべく衝突が起こらないようにするためである。
以上述べたことをプログラム化したものを下に示す。
#include <stdio.h>
#define HASHSIZE 19
char *hashTable[HASHSIZE];
// 素数 ... , 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61
char *func[] = { // 登録する単語
"abs", "atof", "atoi", "atol", "close", "feof",
"fgetc", "fgets", "fopen", "fputc", "fputs", "free"
};
char *check[] = { // チェックする単語
"strcmp", "atof", "printf", "free"
};
int hash(char *key) {
int n, h = 0;
for (n = 0; key[n] != '\0'; n++) {
h = (h * 137 + key[n]) % HASHSIZE;
}
return h;
}
int put(char *str) {
int n, h = hash(str);
for (n = 0; n < HASHSIZE; n++) {
int ix = (h + n) % HASHSIZE;
if (hashTable[ix] == NULL) {
hashTable[ix] = str;
return ix; // 新規登録
} else if (strcmp(hashTable[ix], str) == 0) {
return ix; // 登録済み
}
}
printf("Error: Hash Table Full");
return -1;
}
int contain(char *str) {
int n, h = hash(str);
for (n = 0; n < HASHSIZE; n++) {
int ix = (h + n) % HASHSIZE;
if (hashTable[ix] == NULL) {
return -1; // 登録なし
} else if (strcmp(hashTable[ix], str) == 0) {
return ix; // 登録済み
}
}
return -1;
}
int main() {
int n;
printf("HASHSIZE = %d\n", HASHSIZE);
for (n = 0; n < sizeof(func)/sizeof(char*); n++) {
put(func[n]);
}
for (n = 0; n < sizeof(check)/sizeof(char*); n++) {
printf("\"%s\"は登録されて%s\n",
check[n], contain(check[n]) >= 0 ? "います" : "いません");
}
}
実行結果を以下に示す。
HASHSIZE = 19 "strcmp"は登録されていません "atof"は登録されています "printf"は登録されていません "free"は登録されています
文字列に日本語を含む場合には、
地図システムではノード(折れ線データの頂点)数は膨大である。 7,000万程度のノードの id(8バイト) と整数化した経度(4バイト)と緯度(4バイト)の管理を HashMap で行うにはノートパソコンでは主メモリが足りない。そこで、次のようにした。
簡単なオープンアドレス方式とした。メモリ使用量削減から、ノード情報は class 定義はせず、 long[] nodes（ノードid）、int[] lons、int[] lats の三つの配列で管理する。
パフォーマンス上は全く問題がなかった。MAXSIZE は 100000000 でもいいであろうが、 メモリに余裕があるため、130000000 とした[2023.1.28]。
ハッシュ表に当たるのが long[] nodes である。int[] lons、lats には無駄があるが、 class を導入するよりはメモリ使用量は少なくて済む。
static int MAXSIZE = 130000000;
static long[] nodes = new long[MAXSIZE]; // node id
static int[] lons = new int[MAXSIZE];
static int[] lats = new int[MAXSIZE];
static int hash(long id) {
return (int)(Math.abs(id * 137) % MAXSIZE);
}
static int put(long id, int lon, int lat) {
int n, h = hash(id);
for (n = 0; n < MAXSIZE; n++) {
int ix = (h + n) % MAXSIZE;
if (nodes[ix] == 0) {
nodes[ix] = id;
lons[ix] = lon;
lats[ix] = lat;
num_nodes++;
if (num_nodes % 1000000 == 0) {
System.out.printf("%d万\r", num_nodes / 10000);
}
return ix; // 新規登録
} else if (nodes[ix] == id) {
return ix; // 登録済み
}
}
System.out.println("Error: Hash Table Full");
return -1;
}
static int get(long id) {
int n, h = hash(id);
for (n = 0; n < MAXSIZE; n++) {
int ix = (h + n) % MAXSIZE;
if (nodes[ix] == 0) {
return -1; // 登録なし
} else if (nodes[ix] == id) {
return ix; // 登録済み
}
}
return -1; // 存在しない
}