- ベストアンサー
ハッシュ法について
nickn123の回答
ハッシュ(hash)とは、データ検索を高速化する方法です。 例えば、１万人の名簿から名前を使って検索する場合に、単純な検索だと、最大では１万回の名前の比較が必要になります。 そこで、１万人のデータをあらかじめ複数のグループに分割しておき、検索時に特定のグループだけを検索する事で比較回数を少なくしようと言う方法です。 この為には、名前を入力するとグループの番号に変換する関数が必要になります。この関数をハッシュ関数と呼び、求められる値（グループ番号）をハッシュ値と呼びます。 ＃単純な例だと、名前の先頭があ行だったら１、か行だったら２、さ行だったら３、、、わ行だったら１０、と言う関数にすれば、１０個のグループに分割できますよね。。 ハッシュ関数は、各ハッシュ値がなるべく均等に選択されるものが良いです。つまり、各グループ内の数が均等にした方が良い。
関連するQ&A
- アルゴリズムでわからない問題があります。（C言語）
問題１：探索アルゴリズムであるハッシュ法について正しいものを選べ。 (1)ハッシュ関数の出力によりデータを格納した配列の先頭から順番に調べる． (2) 入力データを，ハッシュ関数の出力により求めた格納場所に基づいて，あらかじめ木構造に格納しておく． (4) 入力データを格納した配列を繰り返し２つに分割し，それぞれを順番に調べていく． (3) 入力データから格納場所の位置に変換する関数（ハッシュ関数）の出力により，データの探索場所を決定する。 (5) 入力データを，ハッシュ関数の出力により求めた格納場所に基づいて，あらかじめヒープに格納しておく 問題２：探索アルゴリズムであるハッシュ法について正しくないものを選べ。 (1)入力データはハッシュ値で決められる場所に格納される． (2) ハッシュ関数には，異なる入力の値に対し異なる値を出力することが求められる． (3) ハッシュ関数の時間計算量は，入力データのサイズに比例する． (4) データの格納場所が大きい方が効率がよい． (5) 一般に２分探索法より高速に動作する． どなたかアルゴリズムに詳しい方回答お願いします
- 締切済み
- C・C++・C#
- ハッシュ（オープンアドレス法） C言語の課題
努力はしてみたのですが、C言語の課題ができません。教えていただけないでしょうか。 問：名前と年齢を入力し、名前をキーとしてハッシュ（オープンアドレス法）に登録する。'-'が入力されると登録を終了し、次に入力された名前をハッシュ法で検索し、あればその人のデータをハッシュから削除する、その後、ハッシュ表の内容を出力するプログラムを作成せよ。ただしハッシュ表の大きさは５とする。 例 koizumi 入力 1 入力 fukuda 入力 2 入力 aso 入力 3 入力 - 入力 koizumi 入力 fukuda(2) 出力 aso(3) 出力 ハッシュ関数は int hash(char *name) { int ret=0; while (*name)ret += *name++; return ret%5; } 再ハッシュ関数は int rehash(int h) { return (h+1)%5; } を使おうと考えています。 内容を理解できないと困るので簡単なプログラムをお願いします。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- ハッシュ法でのデータ管理について教えてください
ハッシュ法でのデータ管理をするプログラムを作りたいんですが長いことPASCALに触ってなかったせいか全く分かりません。 どなたか教えていただけないでしょうか？？問題の概要は以下のようなものです。 表に登録するデータについては、キーは英数字からなる長さ８までの文字列でデータ本体は整数（型名はintegerでよい）です。 ハッシュ表のサイズは１１とします。 ハッシュ関数は文字列xの各文字のASCIIコードの総和を１１で割った余りとします。 さらにメニュー表示として入力した文字により行う操作を決定します。 どの文字がどのような操作を行うのかは以下のとおりです。 's' の場合： ハッシュ表に登録されている全レコードを，ハッシュ関数値毎に(キーの値とデータの両方を)すべて表示します． 'r' の場合： さらに「キーの値」と「データ」を入力し，すでに同じキーをもつデータがあれば「二重登録」として検出し，そうでなければ，そのレコードをハッシュ表に登録します． 'e' の場合： さらに「キーの値」を入力し，そのキーをもつデータがハッシュ表に登録されているならば， そのデータを表示します．さらに削除するかどうかを入力させて，削除する選択をした場合にはそのレ コードを削除します．そのキーをもつデータがハッシュ表にない場合には「そのキーをもつレコードが ないこと」を出力しますが，ハッシュ表には操作を加えません． 'i' の場合： ハッシュ表に登録されている全レコードを，キーの値が小さい順に表示します．ここで「キー の値の順」とは，文字列の辞書順のことを意味します．Pascal では，文字列a,b に対して，a がb より 辞書的順序が先(小さい) ときには「a<b」で表現できます． 'd' の場合： 「'i' の場合」の逆で，キーの値が大きい順に表示します． 'q' の場合： プログラムを終了します．具体的には，実行文部の最後の「end.」の直前までジャンプし ます． 長くなってすいません。ちょっとしたヒントでもいいので教えていただければ幸いです。
- ベストアンサー
- その他（プログラミング・開発）
- ハッシュ法(オープンアドレス)線形探査法と再ハッシュ法
1から10000までの数字がランダム(重複なし)にはいっているファイルから任意に10個の数字を選びハッシュ法(オープンアドレス)の線形探査法と再ハッシュ法を使って探すプログラムを作りたいのですがまったく手がでません。さらに探査回数と実行時間も出力しなければなりませんが、こちらはなんとかできます。ハッシュ法というのが初めてで困っています。どなたか教えてください。お願いします。 ちなみにファイル名は次のようにmain関数中に絶対パスで記述します。 char infile[20] = "/integer.dat"; int in[10]={20,168739,701,52774,44476,185,994737,124623,645300,999901};
- 締切済み
- C・C++・C#
- phpのパスワードのハッシュ化について
phpで会員サイトの作成を学習しています。 PDOを使用してMysqlサーバーに接続しています。 開発環境はxamppでphp Version 5.5.15を使用しています。 入力フォームにユーザーの情報を入力してもらい、 データベースに格納する際、 基本的なセキュリティ要件として パスワードをハッシュ化する必要があるということを こちらのサイトで（http://php.net/manual/ja/faq.passwords.php） 知りました。 ハッシュ化については初耳で、いまいちハッシュアルゴリズムの種類による違い等はまだ理解しきれていないのですが、 PHP5.5.15を使用しているので、パスワードのハッシュアルゴリズムは 上記サイトに載っているようにpassword_hashを使用するのが今のところ最善なのでしょうか？ また、ハッシュ化されたパスワードの認証についてですが、 ログイン画面でパスワードを認証する際、 ユーザーが入力したパスワードをハッシュ化して 該当レコードのハッシュ化されて保存されたパスワードと 同じであれば認証が成功するという認識で正しいでしょうか？ ご回答、よろしくお願いします。
- ベストアンサー
- PHP
- ハッシュアルゴリズム
SSHAハッシュアルゴリズムはSHAと何が違うのでしょうか？ また、SSHAのアルゴリズムを説明しているようなサイトがあれば教えてください。
- ベストアンサー
- その他([技術者向] コンピューター)
- 相互的な検索のできるハッシュテーブル？
こんにちは。データ構造とアルゴリズムを学習しているJava入門者です。 「名前」と「電話番号」の二つのデータを格納するハッシュテーブルを実装したプログラムを考えています。名前をキーにして電話番号を呼び出すところまではいったのですが、 それと同時に電話番号と名前のどちらを入力しても、もう片方が検索できるようなプログラムを作れ、というのが今回の課題なのです。 基本的なハッシュテーブルの構造は学んでいるのですが、 どうしても「名前と番号、どちらのデータからも同じデータに辿り着く」ようなハッシュ関数が頭に浮かびません。 検索して色々調べてみたのですが、それらしい記事を見つけることが出来ませんでしたので、ここに投稿させていただきました。 どうぞよろしくお願いします。
- ベストアンサー
- Java
- ハッシュ法
ハッシュ法で作ったデータ構造をファイルに書き込む、またファイルからの読み込みを行うにはどうしたら良いのでしょうか？？ 連結リストの場合、ファイルを開いてから下のようにすれば書き込める事が分かったので、下の操作をハッシュテーブルの大きさ分だけ繰り返せば良いのかな、と思ったのですができません(> <) for(pos = g_syain_head; pos != NULL; pos = pos->next) { offset = sizeof(Syain) * i; fseek(fp, offset, 0); fwrite(pos, sizeof(Syain), 1, fp); i++; } 誰か分かる方お願いします！！
- ベストアンサー
- C・C++・C#
- 均一ハッシュ法と線形走査法
均一ハッシュ法と線形走査法それぞれについて 探索成功の場合、表を調べる回数を平均3回未満に おさえるためにはそれぞれの方法の場合、 データ数nに対して表の大きさをどれくらいにとる 必要があるのでしょうか？ よくわかりません。どうやって計算したら良いでしょうか？
- 締切済み
- 数学・算数
お礼
どうもありがとうございました。参考にさせていただきます。