文字列をハッシュにしなければならないのですが

質問

C言語にさ
ファイルの中にある、3バイトunicodeの漢字文字列郡をハッシュテーブルに格納してハッシュを作りたいんですが、取っ掛かりすらつかない状況です。
とりあえず、配列から３バイトの１６進数にして、後はその文字列分の１６進数を足して、それを割ってキーをつくりテーブルにいれる、としようとしています。

配列から３バイトの１６進数にする
int joint(char a, char b, char c){
int join = 0;
join = a<<8;
join = (0x0000FF00 & join) + (0x000000FF & b);
join = join<<8;
join = (0x00FFFF00 & join) + (0x000000FF & c);
return join;

}

このように１６進数にするのですが、最初の取っ掛かりとしてのハッシュについては、どうやったらハッシュテーブルに格納でくるのかいまいちわからないのです。誰かわかりやすく教えてください。

回答No.2

chie65536（@chie65535） · ベストアンサー

＞後はその文字列分の１６進数を足して、それを割ってキーをつくりテーブルにいれる、としようとしています。

それは良いとは言えないね。

何故なら「あいう」と「ういあ」「いあう」「あうい」など、文字が入れ替わっただけの文字列が、すべて同じキーになってしまうから。

日本語のように「似たような文字が似たような配列で現われる言語」では、文字が入れ替わっただけの場合にもキーが変わるようにした方が良い。

あと、テーブルに格納する方法は、以下の通り。

・要素数２０４８個とかの配列を用意する。
・その配列の要素は「線形リスト」へのポインタ。初期状態では全部ヌルポインタ。
・線形リストは構造体で「文字列のポインタ」と「次のポインタ」を持つ。
・文字列からキー（０～２０４７）を作る。
・配列の「キー番目」を見に行く。
・配列の「キー番目」がヌルポインタなら、リストが１要素だけの線形リストを作り、配列に作ったポインタを格納する。線形リストの「文字列のポインタ」はキーを作った文字列へのポインタ。「次のポインタ」はヌル。
・配列の「キー番目」がヌルポインタではないなら、線形リストを最後まで辿り、同じ文字列が既にあるか調べる。同じ文字列があるなら線形リストはそのままにする。同じ文字列がないなら線形リストに追加する。

補足

ハッシュ関数は、こんな漢字のを使おうと思っています。

// ハッシュ関数
// ... 戻値 : ハッシュ値
// ... 引数 : key（キー）, mod（割る数）
unsigned int hash(char* key, int mod) {
　　　　unsigned int n = 0;
// 文字コードを順番に足していく
for( n = 0; *key != 0; key++)
n = (64 * n + *key)% mod;
return n;
}
しかし、ハッシュテーブルというものに関して未だよくわからないです。

回答No.6

toda hiro（@hiro_knigh）

>> しかし、16進数の文字コードを何で割って、ハッシュテーブルに格納していけばいいのでしょうか？
>> やはりFFFFFFなのでしょうか？

どう答えたら良いのだろう。。。。
#4様が的確に答えておられるのに。。。

基本的に上手く均等的になるようハッシュ値が求められれば良いのです。
それと、関数の外部から割るための値を貰おうとされているようですが間違いです。
ある一つのハッシュテーブルに格納するためのハッシュ値を求める算出式はユニークでなければなりません。
そうでなければ、ハッシュテーブルに格納したデータは意味の無いものになってしまいます。

回答No.5

toda hiro（@hiro_knigh）

ハッシュテーブルのMAXは、分類されるキーにより演算された値の取り得るMAXの値と思えば良いでしょう。

後は、自己参照構造体などで#3様が提供されている図を実現するようなプログラムを書けば良いだけです。

補足

私の場合は、漢字と日本語が混じった文字列を16進数として、下記の関数で計算したものが、ハッシュテーブルに入ると考えればいいのですね。
しかし、16進数の文字コードを何で割って、ハッシュテーブルに格納していけばいいのでしょうか？
やはりFFFFFFなのでしょうか？
// ハッシュ関数
// ... 戻値 : ハッシュ値
// ... 引数 : key（キー）, mod（割る数）
unsigned int hash(char* key, int mod) {
　　　　unsigned int n = 0;
// 文字コードを順番に足していく
for( n = 0; *key != 0; key++)
n = (64 * n + *key)% mod;
return n;
}

回答No.4

chie65536（@chie65535）

＞しかし、ハッシュテーブルというものに関して未だよくわからないです。

要は「辞書から文字列を探すときに、探す回数を減らそう」と言うのが、ハッシュテーブルを作る理由。

ANo.3の図を見て下さい。

辞書に「あいう」「かきく」「いろは」「あう」「させそ」「わおん」の６つが登録されている場合に「させそ」を探そうと思ったとします。

ハッシュテーブルを使わず、最初から全部の文字列を調べて行くと、５番目に「させそ」が出てくるまで、５回チェックしないとなりません。

これが「全部で５つ」ではなく「全部で４０万語」だったら？そして「させそ」が３９万８３１４番目にあったとしたら？単語を検索するたびにイライラさせられます。

しかし「『させそ』からハッシュキーの『２』を計算で求め、ハッシュテーブルの２番目を見に行くと『あう』の直後に、すぐに『させそ』が見付かる」のです。

また「かきくけ」を探そうとして、ハッシュキーを計算したら「１」になったとします。ハッシュテーブルの１番目を見るとNULLになっているので「『かきくけ』は未登録で、辞書にない」と言うのがすぐに判ります。

もし「端から全部を探しに行く」だと「未登録の単語を探す場合、全ての単語と比較しないと、未登録なのが判らない」ので、４０万語あれば４０万回の比較が行われます。

４０万語を「文字列により計算で求まる値を使って、均等に１０２４個に分類する」と、１分類あたり約３９０個になります。

つまり「全部で４０万語あっても、最大でも３９０～４００個くらい調べれば、辞書にあるかどうかが判る」のです。

このように「計算で求まる値で、幾つかに仕分けして分類してから、分類された筈の所だけを調べよう」と言うのが「ハッシュテーブルを作る理由」です。

その為「どのような文字列が来ても、偏らないで均等に分類できるようなキーが必要」なのです。

日本語の場合「良く使われる単語の文字数」や「ひらがななど、よく使う文字」に偏りがあるので、うまく均等になるような計算ルーチンが要ります。

補足

ハッシュテーブルのサイズってどのように定義すればいいんですか？
比べようとしてる文字列データが10万行以上あるのですが、配列の個数を10万個取ればいいのですか？

回答No.3

chie65536（@chie65535）

イメージ的には、こんな感じ。

「あいう」「かきく」「いろは」のハッシュキーは０。

「あう」「させそ」のハッシュキーは２。

「わおん」のハッシュキーは５。

０番をテーブルの先頭とした場合、１番、３番、４番は未使用。

図の「矢印」は「ポインタ」を表わしている。

回答No.1

Tacosan

なんとなく日本語が怪しい気もしますが, そもそも「ハッシュ」がなにか理解できていますか?

補足

ハッシュてのは、入力されたデータから乱数を取ってきてインデックスにするものじゃないんですか？