トップページ⇒tech
243コメント67KB

[[ハッシュ法統合スレッド]] vol.1

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
勉強してはいるんだが、よく分からん。
過去ログをあたっても、きちんとしたものがないから建てました。

語りあって勉強していこう。
0002sageNGNG
馬鹿死ね！
単発質問スレ立てるんじゃねえ。
0003デフォルトの名無しさんNGNG
せめて「アルゴリズム」とかにしてくれ
http://pc.2ch.net/test/read.cgi/tech/1004183881/l50
---------------終了----------------
0004デフォルトの名無しさんNGNG
Hashぐらいで勉強？
お前に才能は全然無い。
辞めろ。

ーーーーーーーーーーーーー終了ーーーーーーーーーーーーー
0005デフォルトの名無しさんNGNG
>>1
才能が無いかもしれん。頑張って勉強しる。

>>2-4
別に単発質問じゃねぇじゃん。よく日本語読めよ。
知ってるなら教えてあげれば？
君たちみたいな低レベル厨房には無理だと思うけど。
0006名無しさんNGNG
2chで語り合うより本読んだほうが100万倍速いと思われ。
0007デフォルトの名無しさんNGNG
5=1
単発質問は叩かれて当然。
しかも「教えてください」という謙虚な態度が見られず
「一緒に勉強しましょう」などとは笑わせる。
子供だろうな？
0008５NGNG
>>7
ごめん、５＝１じゃないんだけど・・・？？？
0009デフォルトの名無しさんNGNG
漏れも5=1だと思う
>>1は削除依頼出しとけな
0010デフォルトの名無しさんNGNG
ハッシュだけで語る事ってあるの？
なんか目のさめるような最新のアルゴリズムでもできたのか？
無いなら終了
0011デフォルトの名無しさんNGNG
vol.1とか書いてるし…
新打法がいいかもね
0012デフォルトの名無しさんNGNG
>>7
どちらにしても「自分のため」にスレを立てたことが見て透けるから叩かれる。

>>1
適当にキーワードを教えるから google で調べれ
衝突回避: 開番地（オープンアドレス）法 / チェインリスト（連鎖リスト）法
ハッシュ関数: 除算法 / 平方採中法 / 乗算法
用途: 一方向 / 最小完全 / 順序保存
ハッシュテーブル最適化: Java や Perl やファイルシステムの実装を参照
00131NGNG
>>2-11
ﾊｧ?かってに勘違いしないでくれる？

>>12
ありがとうございます。
0014デフォルトの名無しさんNGNG
良スレage
0015デフォルトの名無しさんNGNG
最近gperf置いてるところなくなってるけど、
特許かなんかに引っかかったのかな？
0016デフォルトの名無しさん NGNG
ここでモナーのAA使って説明してっ！！
0017デフォルトの名無しさんNGNG
Ruby以外は全て糞。
0018デフォルトの名無しさんNGNG
ﾊｯｼｭﾄﾞﾋﾞｰﾌが食べたいけど狂牛病怖いsage
0019デフォルトの名無しさんNGNG
18は既に狂牛病だから問題なし
0020デフォルトの名無しさんNGNG
マジで質問しますが、
オープンアドレス法と、リストチェイン法はどちらが有用ですか？
0021デフォルトの名無しさんNGNG
Ruby
0022デフォルトの名無しさんNGNG
要素数が少ないならオープンアドレス法
多いならその他
0023デフォルトの名無しさんNGNG
>>13
必要な情報手に入れたら終わりかよ？
「語り合って勉強」はどうなったんだ？

ばーーーーーか。
0024デフォルトの名無しさんNGNG
いいから、もう終了。
0025デフォルトの名無しさんNGNG
オープンハッシュ仕事で使ったことないんだけど、役に立つ？
使い勝手が悪い気がする。
0026デフォルトの名無しさんNGNG
まずつかわねーよな
0027デフォルトの名無しさんNGNG
>>25
JavaのHashtableってオープンハッシュじゃない？
使っててびっくりした事があるような。
0028デフォルトの名無しさんNGNG
age
00291NGNG
>>23-24
「終了」なんだろ？だったら煽るな低脳。
0030デフォルトの名無しさんNGNG
　　　　　　　　　　　 ㌧㌦　,,　∧＿∧
㌧㌦ (＼／)　　　　　　 ノ|ヽ (　´∀｀)八
／|＼( ´∀｀)／|＼　／ ｜ 　　　'''''´ ｜ ヽ
⌒⌒⊂　:　つ⌒⌒ （ 〃⌒γ　　　　γ⌒ヽ　）
　　　 ∪∪　　　　　　　 　 ∪ ⌒ ∪
0031煽られて喜ぶな！NGNG
>>1よ・・・
http://www.geocities.co.jp/Milano-Killer/6419/1.swf
00321 ◆I5fAb/7M NGNG
あのー・・・
最初の書き込み以外は全部偽物なんですけど・・・

>>13とか俺のイメージが悪くなるようなこと言うなよ！
仕事から帰ってきてみればﾋﾞｸｰﾘしたよ！畜生！
00331 ◆I5fAb/7M NGNG
で、取り敢えず、半角小文字アルファベットだけの文字列を
２７進数の整数ととらえ、１０進整数に変換するところまで
考えました。
でも、配列のサイズが異様に大きくなっちゃうんだよなぁ・・・

＃いっとくけど、一方的に教えてもらうつもりはないよ
＃自分でもいろいろ考えてるし、センスがないのも分かってる
＃ただ、色んな人と情報を共有したかっただけだよ
0034デフォルトの名無しさんNGNG
ハッシュは自作する機会が余りないけど、
かなり基本的なデータ構造だからねえ。

>>33
その配列ってハッシュテーブルのこと？
0035デフォルトの名無しさんNGNG
>>33
その話聞いてると、プログラミング向いてないのが判る。
他の事しなさい。
0036デフォルトの名無しさんNGNG
で、ネタ切れ?
0037新手のＣ＋＋使いゴゴゴNGNG
>>33

性能のよいハッシュ「関数」の作成を目指しているのかにゃ？
汎用性を考えると、対象の文字列を限定するのは
どうかと思われ。。。

単に ASCII コードをそのまま使うのではだめかにゃ？
それにハッシュ値は普通、mod(割り算の余り)を
とるから、配列のサイズがでかくなって困るはずは
ないですよ。
0038デフォルトの名無しさんNGNG
>>37
どう見てそんな大層なもんじゃないよ。

特定の集合について衝突しないハッシュ表が欲しい
とかならgperf使って完全ハッシュ関数を求めれば
良いだけだが、1はそれよりはるか以前のレベル。
0039デフォルトの名無しさんNGNG
>>38
それ思った。

＞で、取り敢えず、半角小文字アルファベットだけの文字列を
＞２７進数の整数ととらえ、１０進整数に変換するところまで
＞考えました。
＞でも、配列のサイズが異様に大きくなっちゃうんだよなぁ・・・

これじゃハッシュどころじゃないわな。
0040デフォルトの名無しさんNGNG
もしやハッシュ関数でハッシュ値を求めるのに大きな配列使ってるのか。
12 でキーワード挙げたのに、挙げたのに……
004137NGNG
>>38

おぉ、そう言われると、なんか、そんな気が...(笑)

とりあえず、「Cプログラマのためのアルゴリズムと
データ構造」 (ソフトバンク/近藤嘉雪著/\2,200-)を
おすすめしときます。わたしゃ、これで理解した
ような気分にひたれました。
00421 ◆I5fAb/7M NGNG
modの値をとればいいのかぁ・・・
ありがとう。

配列のサイズというのは、ハッシュテーブルのことです。
余りを利用するからかちあいが生じるのね。
やっと概要を理解してきました。事件の点と点がつながる感じです。
00431 ◆I5fAb/7M NGNG
それで、かちあいが生じたときには
次の番号に移すか、リスト構造のチェーンにすればいい、と。
なんとなくですが、あっていますか？

ちなみにPerlの連想配列はどうしているのでしょう？
00441 ◆I5fAb/7M NGNG
>>41
さっそくamazonで見てみますね。
情報ありがとう。
004537NGNG
>>43

前者はオープンハッシュ、
後者ガチェーンハッシュだったかしらん。
多分、あっているような気が。

Perl はどうなんでしょうね。
ちなみに、連想配列＝ハッシュではないので、注意。
二分木で実現している連想配列もありますんで。
004637NGNG
>>44

すみゃあせん。C言語プログラマ向けなので、
他言語の人はちょっと×でしょう。
C言語を知っていたら、オススメということで。
00471 ◆I5fAb/7M NGNG
上の方では何か勝手に煽られてますけど ^^;
プログラム板の人たちはみんないい人ですね。嬉しいです。
私も勉強して、情報をどんどん書き込むつもりでしたが
なかなか追いつけません。ごめんね。
本当に感謝しています。

>>46
使用言語はＣ＋＋です。
たぶん大丈夫だと思います。わざわざありがとう。
00481 ◆I5fAb/7M NGNG
>>45
あ、そうなんですか。
２分木だと、探索時間がやっぱりO(logn)になるんですかね。
ハッシュはかちあいがなければ基本的にはO(１)ですよね。

２分木っていうのは実装は分かるんですが、
連想配列にするメリットはあるのですか？
考えましたが、いまいち分かりませんでした。
004937NGNG
>>48

ハッシュ法の欠点としては、メモリを潤沢に使ってしまうという
ことと、ハッシュ関数がタコだったとき、O(n) になってしまうこと。

二分木だと、比較的メモリ仕様量は少ない。あと、バランス木
(B木・AVG?木だったかな)であれば、どんな内容を放りこまれて
も、無茶苦茶性能が落ちるということがありません。

C++ の Standard Template Library だと、どんな内容が
来てもそれなりの性能のハッシュ関数...というのが提供
できないからだとか何とかで、ハッシュテーブルの規格化
が見送られたという経緯があります。
# ↑嘘かも。でも、ハッシュがないのはホント

というわけで、C++ with STL では、自分でハッシュテーブル
クラスを構築しない限りは、連想配列として、map <string,class T>
を使わざるを得ません。

長くてスマソ
0050デフォルトの名無しさんNGNG
>>48
C Magazine の今月号のアルゴリズムページで、
そのものズバリな解説をしているので、見るがよろし。
18 日に来月号がでちゃうので、見るならお早めに。
0051デフォルトの名無しさんNGNG
オープンハッシュの削除ってどうやればいい？
005237NGNG
＞ハッシュ関数がタコだったとき、O(n) になってしまうこと。

えーと、嘘を書いたかも(汗)。
でも、タコ関数だと、性能が落ちるのは確か。
詳しいことは、ちゃんとした文献で勉強してくださいまし。
00531 ◆I5fAb/7M NGNG
>>49 >>50
ありがとう。
C Magazine読んでみます。
でも、あれ難しいんだよなぁ。
理解できるか心配。
00541 ◆I5fAb/7M NGNG
ＳＴＬの話は聞いたことがあります。
っていうか、まだ完全なハッシュ関数って開発されてないんだ・・・

ということは、研究する価値もあるのかな？
005537NGNG
>>51

空のマークではなく、削除マークを入れるしかないのかな？
でも、これではハッシュテーブルの性能は回復しないしなー。

こうして考えると、チェーンハッシュの方が何かと自由がきくなぁ。
005637NGNG
>>54

いや、完璧なハッシュ関数はありえないです。
というのも、テーブルに放りこまれるデータとの
相性問題みたいなもんだからです。

>>38 さんの示された gperf とかいうツールを
使えば、データにあったハッシュ関数を生成
できるような気がしますね。

私自身は gperf は知らないんですけど、
きっと、そういうツールに違いない(笑)
0057デフォルトの名無しさんNGNG
>>51
削除して、rehashするしか無いんじゃない？
005837NGNG
>>57

ですよね～。削除が必要な要件であれば、
オープンハッシュは使わないのが無難ですねぇ。

とすると、Perl はどうしてるんだろ。
0059デフォルトの名無しさんNGNG
lisp/schemeスレの過去ログにオープンハッシュの
コードあったけど、>>57の方法だった。
006037NGNG
>>59

検索お疲れ様です。やっぱそうっすか。

まじで削除できる仕組みを作ろうとすると、
なんか、ハッシュテーブルの各要素に
ハッシュ値自身を入れるとか、
いろいろと複雑な仕組みを用意しなくては
いけないでしょーが、そうすると、
オープンハッシュの「仕組みがシンプル」という
メリットが消えてしまいますな。

# あ、勝手にメリットと思ってるだけで、
# 本当にそうかは知らない。ゴメソ。
0061デフォルトの名無しさんNGNG
オープンハッシュの削除は削除マーク入れるんだよ。
挿入の時に削除マークがあったら、そこに上書きする。

Fortranの時代ならともかく、CやPascalだとオープン
ハッシュの方がちょっと複雑なコードになるよ。
最初から仕様で上限が決まっているならオープンハッ
シュが良いかも。

「完全ハッシュ関数」とは、決められたキーの集合に
ついて衝突のないハッシュ関数のこと。gperfはキー
集合を与えると完全ハッシュ関数のCソースを生成して
くれる。

さらに「最小完全ハッシュ関数」とは、N個のキーに対
して0..N-1のハッシュ値を生成する完全ハッシュ関数。

（これくらい教科書やウエブ読めば載ってるんだからさあ、
いちいちスレ立てるのやめようよ。）
0062デフォルトの名無しさんNGNG
良く使うのって
チェイン法＋木
あたりかなあ。
0063デフォルトの名無しさんNGNG
なんだ、結局自分でハッシュ関数を考えていないじゃん。
0064デフォルトの名無しさんNGNG
gperfが吐いたコードって、GPLに従わなくてもいいの？
ソース非公開の商用でも可？
0065 NGNG
良スレに移行の予感
0066デフォルトの名無しさんNGNG
つか回答出尽くしただろ...移行以前に終了だよ
>>64
Unix板でも逝け。ちなみにGPLに従う必要はない。GCCと同じだ
0067デフォルトの名無しさんNGNG
こういう問題をBASICでやろうとすると
「ああ、マシン語はいいよな」とか思うんだよね。
マシン語だったらオーバーフローが出ようが
フラグが立つだけだからそれに対処するコードを書かないだけの話で
無視してがんがんレジスタに値を加え上げていけばいいだけだから。
BASICだと数値が大きくなるとオーバーフローで止まってしまう。
ダサいなぁとか思いつつmodを入れたりするのだ。
（欲しい所を切り出す必要もあるし）

あ、ダンプリストのチェックサムの話だったかも。
ま、どっちでもいっしょか。
0068デフォルトの名無しさんNGNG
bash
0069ななしさそNGNG
初心者にとってはめちゃくちゃ優良スレッドだよ。ここ。
勉強になった。
0070デフォルトの名無しさんNGNG
tsh
0071デフォルトの名無しさんNGNG
６９＝１ですか？そうですよね？絶対にそうにきまってる！
キミに一言言いたいことがある。
クソスレあ・げ・る・な
0072デフォルトの名無しさんNGNG
>>71
１は上の方でトリップつけて出てきてたじゃん。
変な憶測はやめろよ
0073デフォルトの名無しさんNGNG
なんでハッシュは荒れるの？
ソートじゃ、こうは荒れないよ。
0074デフォルトの名無しさんNGNG
クソスレ決定。多数決で。
とりあえずvol. 1なんてついてるがハッシュでvolいくつまで続けるつもり
だったのかが気になるぞ。
0075デフォルトの名無しさんNGNG
71=74だろ。
0076デフォルトの名無しさんNGNG
>>73
71=74みたいなバカが理解できないから。
ソートはだれでも分かるからだろ。
低レベルな荒らしは無視しる。
007737NGNG
とはいえ、誰かがＱを出さんと、
Ａ出す人はいないわけで。。。。
(と、知ったかぶりしたい 37 でも思うわけで)

誰も質問か、問題提起してくれないようなら
そろそろ、終わりかな？
0078デフォルトの名無しさんNGNG
ハッシュに乱数を使うやり方を聞いたことがあるんだが
一体何に使うの？
乱数にしちゃったらキーと番号の対応関係が１対１じゃ
無くなるんじゃないの？
0079デフォルトの名無しさんNGNG
↑
ゴメン、ageだ
0080デフォルトの名無しさんNGNG
あと、ハッシュのメリット、応用例はなに？
例えば、２分探索にすれば探索時間はO(logn)だから
そんなに時間がかからないんじゃ？
0081デフォルトの名無しさんNGNG
>>80
医院の保険証番号による患者のデータベースとか。
0082デフォルトの名無しさんNGNG
車のナンバーとか。
0083デフォルトの名無しさんNGNG
ラーメンのゆであがり時間の予測とか
0084デフォルトの名無しさんNGNG
>>83
センスゼロ。

力道山　＞　それはチョップ。
0085デフォルトの名無しさんNGNG
>>78
もうすこし勉強してこい
0086デフォルトの名無しさんNGNG
>>78
完全ハッシュが作れないからじゃないかなぁ
0087デフォルトの名無しさんNGNG
どこかでハッシュのライブラリを提供してないですか？
ＳＴＬみたいな仕様のものがあると嬉しいです。
0088デフォルトの名無しさんNGNG
Ｃ＃とかＪａｖａでハッシュはあるの？
0089デフォルトの名無しさんNGNG
Javaにはある。入門書の真中あたり。
0090デフォルトの名無しさんNGNG
配列の次に習うのね。
0091デフォルトの名無しさんNGNG
>>87
STLPortじゃ駄目なのか?
0092デフォルトの名無しさんNGNG
gperfちょっと使ってみたけど、アプリの実行中に
ハッシュ表の再作成が出来ないと、利用局面があまり多くない気がするんだけど、
どうなの？
0093デフォルトの名無しさんNGNG
>>92
使い道まちがってる。
gperfが役に立つのは予約語みたいにキー集合が固定の時。
同じコンパイラでも変数表には使う意味なし。
あたりまえだろ？
009492NGNG
>93
そうなんだ。
……と、rubyのソースを見てみたら、確かに予約語にしか使ってないね。
gccもたぶんそうかな。
0095デフォルトの名無しさんNGNG
ハッシュドビーフ
0096デフォルトの名無しさんNGNG
まず、用語を共通にしようよ

ハッシュ関数 【hash function】 とは元の文や値に一意に対応する固定長の疑似乱数を作る関数
　通信では（パリティやチェックサムと並んで）データの保全性を確保する為に使われる

ハッシュ法とは、このハッシュ関数から得られたハッシュ値を配列添字に使う事で高速検索を
実現しようというもの。

　衝突がなければ非常に高速。　　だから動的に表が変化しない場合やその頻度が探索頻度より
非常に小さい場合に有利

　・・・・てな感じでいい？
0097デフォルトの名無しさんNGNG
>>96
さんくす
0098デフォルトの名無しさんNGNG
>>96-97
いやもう終わってるんだが…
0099デフォルトの名無しさんNGNG
ハッシュテーブルの数は素数がベストで、2 や 10 の累乗だと
衝突が発生しやすいのでダメらしいけど、その理屈がよく分らない。
素数で割ると、なんで余りの数値が散らばりやすくなるの？

誰かうまく解説してちょ。
0100デフォルトの名無しさんNGNG
>>99
たとえ素数がベストでも、実行速度がベストとは限らんからねぇ。
今の時代、
and 0.5clock
mod 39clock
とかザラだし。
0101デフォルトの名無しさんNGNG
キーに使う値が、たまたま割り切れる数ばかりというのは、よくあることです。
その場合、同じく割り切れやすい値をテーブルサイズにすると、値が集中してしまう。
どんな数でも割れない素数なら比較的安全。
・・・ということではないかと。考えてみました。
0102デフォルトの名無しさんNGNG
しょうがない、ちゃんとやるか（←何様だ）。

ハッシュ法(hashing)：
　キーをハッシュ関数(後述)によってN通りに分類し、キーkと値vを
　大きさNの配列(ハッシュ表)に格納する事によって高速に検索を行う手法。

ハッシュコード： キーから非負の整数への関数
ハッシュ関数： キーからハッシュ表の添字(Cだと0～N-1)への関数。
　　　　　　　ハッシュコードをNで割った剰余を取るのが普通だが、
　　　　　　　ハッシュコードを使わないで直接ハッシュ関数を得る
　　　　　　　こともある。
バケット： ハッシュ表の要素。
プローブ： ハッシュ関数の値(ハッシュ値) i = h(k)を添字に使ってi番目の
　　　　　バケットを引き、使用済みか、もしそうならキーがkと等しいかを
　　　　　調べる操作。未使用ならば検索失敗。使用中なら、キーをkと比較
　　　　　し、等しければ検索成功。
衝突： 複数のキーが同じバケットに割り当てられること。この場合に、後か
　　　らの値をどう格納するかで、大きく分けて2つの方法がある。
　　　　　1. オープンアドレス法(closed hash table)
　　　　　　h(k)から始まって、0～N-1の数字が1回ずつ現れるような数列を
　　　　　　使い、未使用の場所が出てくるか、すべての場所を試し終わるま
　　でハッシュ表の異なる場所を次々とプローブする方法。
　　未使用の場所を見つければ、そこに衝突した値を格納する。
　　数列として良く使われるのはh(k) + j (mod　N)。特に、j=1が
　　最も良く使われる。
　2. チェイニング法(open hash table)
　　キーと値のペアをバケットとは異なる領域(あふれ領域)に格納し、
　　衝突が起きたら同じバケットに属するペアを線形リストでつない
　　でおく方法。現在では、最初からリスト構造にしておくことが多
　　い。
rehash： ２つの意味で使われる。
　1. オープンアドレス法で、別の番地に対してプローブをやり直す
　　こと。
　2. ハッシュ表の占有率(使用中のバケットの割合)が高くなったと
　　き、より大きなハッシュ表に内容をすべて移し変えること。これ
　　により、占有率を常に一定の値以下に保つことができる。

ハッシュ関数の性質：
キーが「等しい」ならば、ハッシュ関数が同一の値を返さなければならない。
ハッシュ関数は、0～N-1の範囲でなるべく一様に分布していることが望ましい。
また、オープンアドレス法の場合は特に、いろいろなキーの値に対してなるべ
く広く散らばった値を返すことが望ましい。(近い値を返すと、プローブの回
数が多くなってしまう。)

なぜNが素数だと良いか:
ハッシュコード自身がなるべくランダムな値を取ることが望ましいが、たまた
ま偏りがあった場合(例えば、あるキーの集合に対してたまたま4の倍数が多く
なってしまうなど)でも、素数で割った余りを取ることで偏りをなくす事がで
きる。

ハッシュ法の効率：
占有率が50%以下ならば、キーの比較回数が平均的にO(1)で済むことが知られ
ている。

rehash(2の意味)の際、どのくらい表を大きくするか：
ある定数g(g > 1.0)倍の大きさにしていくようにすれば、M個のペアを挿入
する際のrehash回数はlog(M)で済み、全コストが平均的にO(M)でおさまる。
0103デフォルトの名無しさんNGNG
何も考えないで作るならChain-Hash+BTree
01041 ◆I5fAb/7M NGNG
わぁ、結構レスがついてますね。
今日は忙しくてレスできそうにないのですが。

>>99
あ、そうなんですか。
それは初めて知りました。
原理が理解できるかどうか分かりませんが、
時間があるときに調べたいと思います。
（まだ、そんなレベルじゃ無いんですけどね・・・）

>>102
ご丁寧にありがとうございます。
0105デフォルトの名無しさんNGNG
1. オープンアドレス法(closed hash table)
2. チェイニング法(open hash table)

これ良く間違えるんだよな。
オープンハッシュというとどちらの事を言ってるのか...
0106デフォルトの名無しさんNGNG
ハッシュポテト
0107デフォルトの名無しさんNGNG
早くも1は飽きた模様。
やはり自己中教えて君だったか(ﾜﾗ
01081 ◆I5fAb/7M NGNG
>>107
済みませんねぇ。私はあなたのような引きこもりと違って
仕事もあるし忙しいのです。
アルゴリズムの勉強も仕事とは関係なく、趣味の領域です。
勉強のペースをあなたごときに左右されたくありません。
0109デフォルトの名無しさんNGNG
>>108
相手によって態度変えすぎ。
スレをゴミにしたくなければ言葉に気を付けてくれ。
仕事をしているならそのくらいはできるよな？
0110デフォルトの名無しさんNGNG
>>108
己の趣味の勉強のために単一質問スレ立てたんでしょ？
そういうのって自己中質問君なんじゃないの？
0111デフォルトの名無しさんNGNG
いくらなんでももう終りでいいんじゃないの、このスレ。
あとは教科書ヨメ。
0112ということだと思われNGNG
趣味の勉強如きに金払って教科書買うなんて嫌だね。
検索して解説ページ探すのも時間と手間がかかるから嫌だね。
0113デフォルトの名無しさんNGNG
それではあなたの知っているハッシュ関数をage!ていきましょっい。
elfhash
0114デフォルトの名無しさんNGNG
糞スレ化の予感。
つーか、もうまともな人間にとっては書くこと無い。
01151 ◆I5fAb/7M NGNG
あらら・・・
ちょっと毒づいてみたら叩かれてしまうとは・・・ ^ ^;

気を悪くされたのならごめんなさい。
一人で勉強するよりも大人数でやった方が効率も良ければ
間違いも発見しやすくなると思ったのです。
それにハッシュは応用も多彩で、単一の話題には
とどまることがないと思ったのですが。

例えば、コンパイラなどは変数の識別に
ハッシュテーブルを用いたりしていますよね？
基礎研究と応用研究は種類の異なるものだと思います。
（そうでないと工学の存在価値が・・・・）

まだまだハッシュというデータ構造には
利用すべき範疇があると思っていた私は見当違いでしょうか。
叱咤・激励・ご意見があればお願いします。
0116デフォルトの名無しさんNGNG
http://burtleburtle.net/bob/hash/doobs.html
0117デフォルトの名無しさんNGNG
>>115
もちろんハッシュに利用価値はあるよ。フツーの技術、プログラマの
ジョーシキとして使われてる。例えて言えば「配列」とか「リスト構造」
の次くらいに来る基本的なデータ構造だ。

「配列について」とか言うスレ立てたらどういう反応が来ると思う？
0118デフォルトの名無しさんNGNG
>>117
データ構造としてのハッシュは確かに陳腐なテーマだが、
ハッシュ演算自体には他にも応用があるだろう。
MD5やCRCみたいなデータ同一性の確認方法とか、
全文検索のインデックスに利用するとかな。
0119デフォルトの名無しさんNGNG
それって応用なんて言う程のもんか？
ドキュな漏れでも普通にやってるぞ（藁
0120デフォルトの名無しさんNGNG
1は目的を達したんで来なくなったのかな?
0121デフォルトの名無しさんNGNG
age
0122デフォルトの名無しさんNGNG
SHA-512とかRIPEMD-320とかあるんだね。
漏れの中では、SHA-1, RIPEMD-160で止まってた。
0123デフォルトの名無しさんNGNG
123
0124デフォルトの名無しさんNGNG
なんていうか、CMapはカスだよな。
0125デフォルトの名無しさんNGNG
終焉
0126デフォルトの名無しさんNGNG
>>1
＞あらら・・・
＞ちょっと毒づいてみたら叩かれてしまうとは・・・ ^ ^;

終わったな。弔い晒しage。どっちだ。
01271.1NGNG
ところで文字列のハッシュ値ってどうやって作るの?
h = (s[i] * 11) ^ h;//ﾅﾝﾁｬｯﾃ
で偏るんだけど。
0128デフォルトの名無しさんNGNG
除算法 / 平方採中法 / 乗算法
0129デフォルトの名無しさんNGNG
LFSR法
0130デフォルトの名無しさんNGNG
>>127 じゃあ

h = (s[i] * 101) ^ h;//
にしたら？
0131デフォルトの名無しさんNGNG
age
0132デフォルトの名無しさんNGNG
sage
0133デフォルトの名無しさんNGNG
ハッシュ法なんてプログラマとして覚えてて当然だと思っていたが、
ゲームプログラマで知っている人に出会ったことが無い（これマジで)
だから、不特定データの出現頻度チェックとか糞汚いプログラム書いてんだねー
0134デフォルトの名無しさんNGNG
>文字列のハッシュ値
http://java.sun.com/j2se/1.3/ja/docs/ja/api/java/lang/String.html#hashCode()

に、javaがどうやってるか載っている。
#それにしてもurlにカッコなんてありなのか?

この31という数字は経験的(ぉ)に良好な結果を出す数値として
知られているそうだね。「プログラミング作法」とかいう本でも
同じ数字が紹介されていた。

ところで
http://java.sun.com/j2se/1.3/ja/docs/ja/api/java/lang/String.html#intern()
って面白いねえ。
同値の文字列を同一の文字列に変換してくれるという、
かんがえようによっては凄くうれしいメソッド。
うまく使えばcompareの手間を極限まで減らすことが可能。
0135デフォルトの名無しさんNGNG
RubyとかPerlとかPythonとかのハッシュ値の出し方
知ってる人がいたら、紹介キボン。
0136お約束NGNG
そーす読め、そーす。
0137もう一つのお約束NGNG
>136
面倒くさいからここで聞いてるに決まってるじゃん。
0138デフォルトの名無しさんNGNG
>>135
Rubyなら大抵のクラスで
hoge.hash


と。
0139デフォルトの名無しさんNGNG
>138
そんなことは聞いてねぇー（藁
0140デフォルトの名無しさんNGNG
とりあえずRubyのハッシュ関数と思われる部分を貼り付けてみるぞ～
ちなみに gperf ってなんだ? 俺は知らん｡

/* C code produced by gperf version 2.7.1 (19981006 egcs) */
/* Command-line: gperf -p -j1 -i 1 -g -o -t -N rb_reserved_word -k1,3,$ ./keywords　*/
struct kwtable {char *name; int id[2]; enum lex_state state;};

#define TOTAL_KEYWORDS 40
#define MIN_WORD_LENGTH 2
#define MAX_WORD_LENGTH 8
#define MIN_HASH_VALUE 6
#define MAX_HASH_VALUE 55
/* maximum key range = 50, duplicates = 0 */

#ifdef __GNUC__
__inline
#endif
static unsigned int
hash (str, len)
　　 register const char *str;
　　 register unsigned int len;
{
　static unsigned char asso_values[] =
　　{
　　　56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
　　　56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
　　 ～ ここらへん長いので省略 ～
　　　56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
　　　56, 56, 56, 56, 56, 56
　　};
　register int hval = len;

　switch (hval)
　　{
　　　default:
　　　case 3:
　　　　hval += asso_values[(unsigned char)str[2]];
　　　case 2:
　　　case 1:
　　　　hval += asso_values[(unsigned char)str[0]];
　　　　break;
　　}
　return hval + asso_values[(unsigned char)str[len - 1]];
}
0141デフォルトの名無しさんNGNG
gperfは完全ハッシュ関数を求めるツール。
ふつうは言語のキーワードとかのコンパイル時に静的に決定されるキーへの
ハッシュ関数を作るときに使うんだが。
0142デフォルトの名無しさんNGNG
例によって手を抜けるところは手を抜いているわけだな＞Ruby
0143デフォルトの名無しさんNGNG
>>141
へー、ちゃんとそういうツールがあるんだねぇ

>>142
手を抜いているってどこらへんのこと?
0144デフォルトの名無しさんNGNG
ハッシュに gperf を使ったり、
正規表現に regex.c 使っているところ。
regex.c は LGPL なんで将来書き直したいと言ってるけどね。
0145デフォルトの名無しさんNGNG
>>140で引用されてるのは、予約語のみを探すのに使う部分で、
hoge.hashので呼び出されるハッシュ関数は何処か別のところに有る筈。
何処に有るかは知らん。
0146デフォルトの名無しさんNGNG
文字列用のハッシュ関数見つけた。
なんか他にも色々あったけどオブジェクトそれぞれに
専用のハッシュ関数を持っているみたい。

int rb_str_hash(VALUE str)
{
　　register long len = RSTRING(str)->len;
　　register char *p = RSTRING(str)->ptr;
　　register int key = 0;

#ifdef HASH_ELFHASH
　　register unsigned int g;

　　while (len--) {
key = (key << 4) + *p++;
if (g = key & 0xF0000000)
　　key ^= g >> 24;
key &= ~g;
　　}
#elif HASH_PERL
　　if (ruby_ignorecase) {
while (len--) {
　　key = key*33 + toupper(*p);
　　p++;
}
　　}
　　else {
while (len--) {
　　key = key*33 + *p++;
}
　　}
　　key = key + (key>>5);
#else
　　if (ruby_ignorecase) {
while (len--) {
　　key = key*65599 + toupper(*p);
　　p++;
}
　　}
　　else {
while (len--) {
　　key = key*65599 + *p;
　　p++;
}
　　}
　　key = key + (key>>5);
#endif
　　return key;
}
0147ｦﾔｸｿｸNGNG
Use the Source , Luke
0148デフォルトの名無しさんNGNG
ウセ、ザ、ソゥアケ、ルケ
0149デフォルトの名無しさんNGNG
ageんなよ。
gperfの話なんてとっくに終わってるだろ。
0150デフォルトの名無しさんNGNG
>>149
んなこたぁない。
0151デフォルトの名無しさんNGNG
俺は、バイナリツリーとハッシュを知ったときは感動したなぁ。
うれしくって、すぐにプログラムを書いたっけ。

正直、みんなに知ってもらいたいと思う。

最近はフリーソフトを公開してるレベルでも
基礎的なアルゴリズムを知らないから困る・・・
0152デフォルトの名無しさんNGNG
授業で聞いた時は「え、どうやって使うの」という疑問が先に湧いた。
（ぶつかった時の事。チェックサムを求めるみたいな話までしかしてくれなかったから。）
で授業の後で聞きにいっても「そこがまた難しいところで」とかなんとか誤魔化されてしまった。
（一般教養的？な授業だった）
ま、今は使えるけどね。
0153デフォルトの名無しさんNGNG
>>150
んなこたあない。
とっくに終わってる。
スレ読み直せ。
0154デフォルトの名無しさんNGNG
>>153
これから新たに質問のあるやつがいるかもしれないだろ。
自分に必要ないからって終わっていると決めつけるのは愚の骨頂。
0155デフォルトの名無しさんNGNG
>>154
そういってあげんな、おめーは必要としてないだろ
0156デフォルトの名無しさんNGNG
>>151
スレ違いな質問になっちゃうけど、
バイナリツリーで感動出来るプログラムってどんなプログラムがあるの?
ハフマン符号化は確かに感動したけど、それ以外に活用出来る用途を知らない。
0157デフォルトの名無しさんNGNG
>>156
クイックソートとかはどうよ？
0158デフォルトの名無しさんNGNG
void *bsearch(const void * key, const void * base,
　　　　　　　　　　size_t nmemb, size_t size,
　　　　　　　　　　int (* compar)(const void *, const void *));
0159デフォルトの名無しさんNGNG
>>158
それってツリーか?
0160デフォルトの名無しさんNGNG
はさみを使って感動的な切り絵や折り紙を作ったとして、
決してはさみに感動するわけではないと思うが。
（最初に良い道具に出会ったときの感動は抜きにして）
0161デフォルトの名無しさんNGNG
プログラムの話は別として
いい道具には感動するよ。
切れ味のいい切出し小刀とか。
必要もないのにいくつも鉛筆削りたくなったりとか。
0162158NGNG
スマソ、バイナリサーチだった。
鬱氏
0163161NGNG
木工はマスタベに陥りやすいので要注意。
（本来の目的を見失いがち。木を削る事自体が快感になるので）
0164デフォルトの名無しさんNGNG
>161
そうそう！
必要もないのに人間を斬りつけたくなったりするよね。
犬猫で我慢するけど（藁
0165デフォルトの名無しさんNGNG
俺は大抵Ｋ＆Ｒに載ってるハッシュ関数
ほとんどそのまま使ってるけどダメ？
0166デフォルトの名無しさんNGNG
>>165
原理が分かっていれば、それでいいと思う。
学習者は自分で書くべし。
0167デフォルトの名無しさんNGNG
Ｂ木とかAVL木のスレ立てて良い？
0168デフォルトの名無しさんNGNG
ﾜﾗﾀ＞[[ハッシュ法統合スレッド]] vol.1
0169デフォルトの名無しさんNGNG
「アルゴリズム全般」とか、そゆ名前にしてくれよな。
0170デフォルトの名無しさんNGNG
全然分からない人は逝ってよしなの？
0171デフォルトの名無しさんNGNG
何に使うワケでもないんだけど、
赤黒木作ってみてね、なんでか50000個に１つ位
ノードが行方不明になるんですよ。
で、紙に赤い腺、黒い線、いっぱい描いて。
仕事してないんだけど、ソース打ってるから。ばれない。

こういう日って幸せだなあ、って。そんな１日でした。
0172デフォルトの名無しさんNGNG
>>171
赤黒木の実装ってわけわかんなくなるよね（ｗ
自作で作るならB木が単純で良い気がする。
0173167NGNG
で、立てて良いの？
0174デフォルトの名無しさんNGNG
>>173
アルゴリズムに関する総合スレならいいんでない？
ただ、過去に合った
【アルゴリズム・データ構造】相談室
http://piza.2ch.net/tech/kako/982/982651804.html
スレ見ても分かるように、需要は少ない。

[アルゴリズム関連スレ]
優秀なアルゴリズムの本
http://pc.2ch.net/test/read.cgi/tech/1006933077/
[[ハッシュ法統合スレッド]] vol.1
http://pc.2ch.net/test/read.cgi/tech/1005461137/
動的計画法を用いるアルゴリズムの開発
http://pc.2ch.net/test/read.cgi/tech/1001491798/
プログラミングの為の数学と算数
http://pc.2ch.net/test/read.cgi/tech/997150743/
フーリエ変換について教えてください
http://piza2.2ch.net/tech/kako/996/996929748.html
交差判定アルゴリズム
http://piza2.2ch.net/tech/kako/996/996157997.html
ＦＦＴの解析ソフト
http://piza2.2ch.net/tech/kako/993/993693311.html
人工知能のアルゴリズムを教えて下さい
http://pc.2ch.net/test/read.cgi/tech/982118979/
【アルゴリズム・データ構造】相談室
http://piza.2ch.net/tech/kako/982/982651804.html
迷路生成アルゴリズムのソース
http://piza.2ch.net/tech/kako/967/967900403.html
0175デフォルトの名無しさんNGNG
補前亜毛
0176デフォルトの名無しさんNGNG
詳しく書いてあるページを教えて！
0177%hash?NGNG
ハッシュって連想配列とか
一時方向変数だっけ？
0178デフォルトの名無しさんNGNG
>>176
ttp://www.ietf.org/rfc/rfc1321.txt
ttp://csrc.nist.gov/publications/fips/fips180-1/fip180-1.txt
0179デフォルトの名無しさんNGNG
米語はいやん
0180デフォルトの名無しさんNGNG
ファイルの内容の比較にハッシュ値を使うのって良い考えと思います？計算量とかどうなのかな、と思いまして。
タイムスタンプとかで比較すると新旧がわかってよいですが、中身がね。
0181デフォルトの名無しさんNGNG
>>180
CRC みたいなもの？
0182デフォルトの名無しさんNGNG
>>180
ふつーMD5
0183デフォルトの名無しさんNGNG
>>180
ファイルサイズ比較->違うなら変更されてる
ハッシュ値を比較->違うなら変更されてる
(タイムスタンプを比較->違うなら変更されている)
ファイルは変更されてない

というのはよく使われるね。ハッシュには衝突の少ないアルゴリズム(MD5など)
を使用する。ファイルがどっちもローカルにあるならMD5の計算をするよりファ
イルの中身を直接比較した方が速いだろうけど、ネットワーク経由ならハッシュ
を使った方がいいことが多いのでは?
0184デフォルトの名無しさんNGNG
1対1で比較ならファイルを直接で良いだろうけど、1対多の場合を考えるとハッシュの方が良いだろうねえ。
0185デフォルトの名無しさんNGNG
>>183
サンキュー
ネットワーク経由でファイルを同期させるってものを考えてます。〈よくあるしくみですが〉
さきにMD5とかで衝突の判定しといたらよさげかなぁとか思いましてね。

他の人もどうも。
バージョン管理が絡んでいますが、1:多とは言えなくてほぼ1：1なのです。
で、みんなはどうしてるのかなぁとか思った、と。
0186デフォルトの名無しさんNGNG
>>185
rsyncとかcvsupのソースでも見たら?
0187デフォルトの名無しさんNGNG
オープンアドレス法とリストチェイン法の違いを教えれ。
0188デフォルトの名無しさんNGNG
>>187
ぶっちゃけて言えばタダの配列対リストの配列
0189デフォルトの名無しさんNGNG
ぶっちゃけすぎ
0190デフォルトの名無しさんNGNG
ぶっかけすぎ
0191デフォルトの名無しさんNGNG
はっちゃけすぎ
0192デフォルトの名無しさんNGNG
　口腔内に射精された精液を気管に詰まらせて窒息寸前になり、１１９番
通報する事故が急増している。オーラルセックスが普及したことで、いわ
ゆる「口内射精」をする人が増えたことが原因。
　１１９番通報してくるのは１８歳未満の若者が圧倒的に多い。オーラル
セックスに不慣れなために、フェラチオ中に思わす射精してしまったり、
逆に、わざと突然射精して女性の反応を楽しもうとして事故に繋がってい
る。
　特に最近増えているのが中学校からの通報。休み時間に校内でセックス
をしたり、セックスには至らないまでもフェラチオをしたりする生徒が増
えたため、通報件数が急上昇している。「高校からの通報件数に追いつく
のは時間の問題」と関係者は語る。
　精液は粘性の高い液体であるため、場合によっては窒息死に至る場合が
ある。救急科の医師は「口内射精をする場合には、必ず相手に意思表示を
してから射精するようにして欲しい。そうすれば事故はかなり防ぐことが
出来る」と話している。
0193デフォルトの名無しさんNGNG
コンパイラにどのようにハッシュが活用されているのか
教えてください。
0194デフォルトの名無しさんNGNG
変数名とかの識別子の高速検索とか。
0195デフォルトの名無しさんNGNG
それぐらいしかハッシュのメリットってないものなの？
0196デフォルトの名無しさんNGNG
>>195
なんだ？
もっとインテリジェントなものを期待してるのか？（ｗ
0197デフォルトの名無しさんNGNG
>>196
サーチをO(1)でこなすのなら、
ハッシュを使ってソートを
更にスピードアップできるのではないか、
と思ったのです。
0198デフォルトの名無しさんNGNG
>>197
なるほど。
確かにソートをO(nlogn)より速くしたいな。
0199デフォルトの名無しさんNGNG
>>199
それができたら何かの賞が取れるだろうな。
できないことを証明されてるかは俺は知らんし。
0200デフォルトの名無しさんNGNG
↑
>>197の間違い。
鬱だ、回線切って素振りしてきます。
0201デフォルトの名無しさんNGNG
夜中にそんなことしてると、職務質問されるぞ。
0202デフォルトの名無しさんNGNG
>>99
そこでさっとテストプログラムを書いてテストしてみないから
99は落ちこぼれなわけです。
0203デフォルトの名無しさんNGNG
初心者への GNU perf のススメ
http://sharl.haun.org/gperf.html
0204デフォルトの名無しさんNGNG
条件が限定されるが、分布かぞえソートがO(nlogn)より速いわけO(n+W)で、
たとえば、ハッシュで16bit以下の世界にマップすれば、それなりに
お望みのものになるかと思われ。
0205デフォルトの名無しさんNGNG
http://pc.2ch.net/test/read.cgi/tech/1005053427/l50
こいつが言ってることはハッシュですか？
0206デフォルトの名無しさんNGNG
>>205
そこのどのレスよ？
0207デフォルトの名無しさんNGNG
>>206
ここのスレよ。
0208デフォルトの名無しさんNGNG
>>207
(ﾟДﾟ)ﾊｧ?
0209デフォルトの名無しさんNGNG
ハッシュ法＝ハヤシライス調理法
0210デフォルトの名無しさんNGNG
なんでSTLにはハッシュがないの？
あれば便利じゃん・・・
0211デフォルトの名無しさんNGNG
ハッシュ関数のあたりが面倒だからだろ。
0212デフォルトの名無しさんNGNG
ハッシュの超基礎的なことが学べる
サイトorメルマガはありませんか？
0213デフォルトの名無しさんNGNG
ハッシュドビーフ
0214デフォルトの名無しさんNGNG
>>212
メルマガでなら最近見たような。
0215デフォルトの名無しさんNGNG
>>212
たくさんあるよ。
どこだかは忘れた。済まん。
0216デフォルトの名無しさんNGNG
>>197
限りなく遅レスだが、ビンソートは一種のそういうものだと思う。
0217デフォルトの名無しさんNGNG
>>216
便ソートってどういうの？
0218デフォルトの名無しさんNGNG
>>217
検索かけてみなされ。
0219デフォルトの名無しさんNGNG
>>218
瓶ソート、だめじゃん・・・
0220デフォルトの名無しさんNGNG
$a{"b"} = "c";
0221デフォルトの名無しさんNGNG
a= { 'b' => 'c'}
0222デフォルトの名無しさんNGNG
>>220
それってPerl？
C++で使うにはどーするのよ？
0223デフォルトの名無しさんNGNG
>>222
map<string,string> a;
a["b"]="c";
0224デフォルトの名無しさんNGNG
>>223
mapはlog(n)の検索時間がかかるんだっけ？
0225デフォルトの名無しさんNGNG
>>222
http://mukun_mmg.tripod.co.jp/mmg/cpp.html
ここのページの１３章ってところで
ハッシュも含めていろんなデータ構造を紹介してるよ。
初心者向けだから分かりやすいのでは？

俺が読んでるメールマガジンだが。
0226222NGNG
>>225
サンクス！早速登録します。
0227デフォルトの名無しさんNGNG
>>225
斜め読みしたけど、そこの作者って丁寧な人だね。
初心者のとっかかりには分かりやすそう。
メルマガだから図がAAなのは見づらいが。
0228デフォルトの名無しさんNGNG
>>227
同意。メルマガにしては良い方だと思う。
0229デフォルトの名無しさんNGNG
ハッシュ最強
0230デフォルトの名無しさんNGNG
kd-tree 最高
0231デフォルトの名無しさんNGNG
結局最強のハッシュは何よ？
0232デフォルトの名無しさんNGNG
>>225
そのメルマガはだめだろ。
スタイル的に。
発行が最近の日付なに書き方も古すぎ。
作者は勉強して無いと思われ。
0233デフォルトの名無しさんNGNG
ハッシュ　ブラウンズ　朝食には最強！
0234デフォルトの名無しさんNGNG
>>232
２月１日に発行されたよ。
バックナンバーを出すのはいつも遅いけど。
0235デフォルトの名無しさんNGNG
定期age
0236デフォルトの名無しさんNGNG
定期age
0237デフォルトの名無しさんNGNG
ハッシュを使った応用プログラムって何か無い？
今度発表しなきゃならなくて困ってるんだけど・・・
0238デフォルトの名無しさんNGNG
過去ログくらい検索すれ！
http://piza.2ch.net/log/food/kako/958/958184629.html
0239デフォルトの名無しさんNGNG
ハッシュを扱うインターフェイスを設計しているのですが、
Listenする人ならリスナー(Listener)ですよね
ハッシュを扱う人ならハッシャー(Hasher)なんでしょうか？
なんか例外とかいろいろ射出しそうでこわいです
0240デフォルトの名無しさんNGNG
>239
ハッシュを作るのは、シェフ(chef)ですよ。
0241デフォルトの名無しさんNGNG
ちなみに、ハシシュを与えられるのはアサシン(assassin)です。
参考: http://www.google.com/search?hl=ja&q=%90%FC%8C%60%83n%83V%83V%83%85

0242デフォルトの名無しさんNGNG
hashの定義ってﾅﾝﾃﾞすか？
0243デフォルトの名無しさんNGNG
ｈａｓｈあげ
■ このスレッドは過去ログ倉庫に格納されています