![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?8acaa2e)
C言語にさ
ファイルの中にある、3バイトunicodeの漢字文字列郡をハッシュテーブルに格納してハッシュを作りたいんですが、取っ掛かりすらつかない状況です。
とりあえず、配列から3バイトの16進数にして、後はその文字列分の16進数を足して、それを割ってキーをつくりテーブルにいれる、としようとしています。
配列から3バイトの16進数にする
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;
}
このように16進数にするのですが、最初の取っ掛かりとしてのハッシュについては、どうやったらハッシュテーブルに格納でくるのかいまいちわからないのです。誰かわかりやすく教えてください。
No.2ベストアンサー
- 回答日時:
>後はその文字列分の16進数を足して、それを割ってキーをつくりテーブルにいれる、としようとしています。
それは良いとは言えないね。
何故なら「あいう」と「ういあ」「いあう」「あうい」など、文字が入れ替わっただけの文字列が、すべて同じキーになってしまうから。
日本語のように「似たような文字が似たような配列で現われる言語」では、文字が入れ替わっただけの場合にもキーが変わるようにした方が良い。
あと、テーブルに格納する方法は、以下の通り。
・要素数2048個とかの配列を用意する。
・その配列の要素は「線形リスト」へのポインタ。初期状態では全部ヌルポインタ。
・線形リストは構造体で「文字列のポインタ」と「次のポインタ」を持つ。
・文字列からキー(0~2047)を作る。
・配列の「キー番目」を見に行く。
・配列の「キー番目」がヌルポインタなら、リストが1要素だけの線形リストを作り、配列に作ったポインタを格納する。線形リストの「文字列のポインタ」はキーを作った文字列へのポインタ。「次のポインタ」はヌル。
・配列の「キー番目」がヌルポインタではないなら、線形リストを最後まで辿り、同じ文字列が既にあるか調べる。同じ文字列があるなら線形リストはそのままにする。同じ文字列がないなら線形リストに追加する。
この回答への補足
ハッシュ関数は、こんな漢字のを使おうと思っています。
// ハッシュ関数
// ... 戻値 : ハッシュ値
// ... 引数 : 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
- 回答日時:
>> しかし、16進数の文字コードを何で割って、ハッシュテーブルに格納していけばいいのでしょうか?
>> やはりFFFFFFなのでしょうか?
どう答えたら良いのだろう。。。。
#4様が的確に答えておられるのに。。。
基本的に上手く均等的になるようハッシュ値が求められれば良いのです。
それと、関数の外部から割るための値を貰おうとされているようですが間違いです。
ある一つのハッシュテーブルに格納するためのハッシュ値を求める算出式はユニークでなければなりません。
そうでなければ、ハッシュテーブルに格納したデータは意味の無いものになってしまいます。
No.5
- 回答日時:
ハッシュテーブルの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
- 回答日時:
>しかし、ハッシュテーブルというものに関して未だよくわからないです。
要は「辞書から文字列を探すときに、探す回数を減らそう」と言うのが、ハッシュテーブルを作る理由。
ANo.3の図を見て下さい。
辞書に「あいう」「かきく」「いろは」「あう」「させそ」「わおん」の6つが登録されている場合に「させそ」を探そうと思ったとします。
ハッシュテーブルを使わず、最初から全部の文字列を調べて行くと、5番目に「させそ」が出てくるまで、5回チェックしないとなりません。
これが「全部で5つ」ではなく「全部で40万語」だったら?そして「させそ」が39万8314番目にあったとしたら?単語を検索するたびにイライラさせられます。
しかし「『させそ』からハッシュキーの『2』を計算で求め、ハッシュテーブルの2番目を見に行くと『あう』の直後に、すぐに『させそ』が見付かる」のです。
また「かきくけ」を探そうとして、ハッシュキーを計算したら「1」になったとします。ハッシュテーブルの1番目を見るとNULLになっているので「『かきくけ』は未登録で、辞書にない」と言うのがすぐに判ります。
もし「端から全部を探しに行く」だと「未登録の単語を探す場合、全ての単語と比較しないと、未登録なのが判らない」ので、40万語あれば40万回の比較が行われます。
40万語を「文字列により計算で求まる値を使って、均等に1024個に分類する」と、1分類あたり約390個になります。
つまり「全部で40万語あっても、最大でも390~400個くらい調べれば、辞書にあるかどうかが判る」のです。
このように「計算で求まる値で、幾つかに仕分けして分類してから、分類された筈の所だけを調べよう」と言うのが「ハッシュテーブルを作る理由」です。
その為「どのような文字列が来ても、偏らないで均等に分類できるようなキーが必要」なのです。
日本語の場合「良く使われる単語の文字数」や「ひらがななど、よく使う文字」に偏りがあるので、うまく均等になるような計算ルーチンが要ります。
この回答への補足
ハッシュテーブルのサイズってどのように定義すればいいんですか?
比べようとしてる文字列データが10万行以上あるのですが、配列の個数を10万個取ればいいのですか?
No.3
- 回答日時:
イメージ的には、こんな感じ。
「あいう」「かきく」「いろは」のハッシュキーは0。
「あう」「させそ」のハッシュキーは2。
「わおん」のハッシュキーは5。
0番をテーブルの先頭とした場合、1番、3番、4番は未使用。
図の「矢印」は「ポインタ」を表わしている。
![「文字列をハッシュにしなければならないので」の回答画像3](http://oshiete.xgoo.jp/_/bucket/oshietegoo/images/media/7/1221246_5497dfa086b89/M.jpg)
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- SQL Server [SQLServer] テーブル名からカラム名を取得する 1 2022/08/23 21:20
- JavaScript 二次元配列の全要素の全要素を区切り文字無しで連結する最も単純な書き方を教えてください 3 2023/06/09 12:51
- PostgreSQL SQLで検索結果の記事を表示したい 1 2022/04/28 21:03
- Oracle 下記のsqlで取得されるレコード以外を取得する方法ありますでしょうか。 SELECT B.番号, B 2 2022/04/20 23:21
- PostgreSQL 投稿記事と関連付けているテーブルがわからない 1 2022/04/27 20:29
- C言語・C++・C# c言語 プログラムのエラー 1 2023/02/11 20:31
- PostgreSQL 画像とカテゴリーを出力したいのですが、取得の条件を付ける方法がわかりません。 2 2022/05/01 18:03
- MySQL PhpMyAdminで作成して実行せよ。 東京23区を、皇居を中心とした4つのエリア(南東, 南西, 1 2023/06/11 11:58
- MySQL 複数DBテーブルからのデータ取得 3 2022/05/17 15:02
- C言語・C++・C# c言語配列の結合についてです。 なぜうまくいかないのでしょうか。 #include <stdio.h 4 2022/05/30 22:42
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
文字列を変数名として扱う方法
-
まったく同じファイルのハッシ...
-
重複ファイルを削除したいので...
-
ハッシュマーク以降のアドレス取得
-
mapのポインタ
-
ハッシュリストって単にハッシ...
-
文字列をハッシュにしなければ...
-
短いハッシュの作り方
-
JSを使ったタブの別ページから...
-
VBAにハッシュ関数はないのです...
-
PHPで変数を暗号化する方法
-
英語でのシャープとコメの呼び...
-
python の素朴な疑問
-
画面を強制的に再描画させる方法
-
VBA Dir関数でファイルをループ...
-
JQueryのスライドショーを停止...
-
vb.netからエクセル関数書き込み
-
DOSコマンドのループ内のTIMEコ...
-
VBのReturnの使い方
-
Escキーを押すと、中断する時と...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
ハッシュ検索はなぜ速い
-
文字列を変数名として扱う方法
-
チェックデジットについて
-
ハッシュのハッシュを実現したい。
-
まったく同じファイルのハッシ...
-
列挙型と連想配列の違いを教え...
-
重複ファイルを削除したいので...
-
*(アスタリスク)の意味
-
短いハッシュの作り方
-
英語でのシャープとコメの呼び...
-
ハッシュマーク以降のアドレス取得
-
Perlは戻り値で、ハッシュや配...
-
一意(ユニーク)かつ、ソート...
-
ハッシュリストって単にハッシ...
-
ActivePerl がハングアップ
-
mapのポインタ
-
多次元配列から重複を削除
-
Perlのサブルーチンの引数に配...
-
Perlのハッシュ変数のソートに...
-
文字数の短いユニークなID生成
おすすめ情報