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

勉強してはいるんだが、よく分からん。
過去ログをあたっても、きちんとしたものがないから建てました。

語りあって勉強していこう。

馬鹿死ね！
単発質問スレ立てるんじゃねえ。

せめて「アルゴリズム」とかにしてくれ
http://pc.2ch.net/test/read.cgi/tech/1004183881/l50
---------------終了----------------

Hashぐらいで勉強？
お前に才能は全然無い。
辞めろ。

ーーーーーーーーーーーーー終了ーーーーーーーーーーーーー

>>1
才能が無いかもしれん。頑張って勉強しる。

>>2-4
別に単発質問じゃねぇじゃん。よく日本語読めよ。
知ってるなら教えてあげれば？
君たちみたいな低レベル厨房には無理だと思うけど。

2chで語り合うより本読んだほうが100万倍速いと思われ。

5=1
単発質問は叩かれて当然。
しかも「教えてください」という謙虚な態度が見られず
「一緒に勉強しましょう」などとは笑わせる。
子供だろうな？

>>7
ごめん、５＝１じゃないんだけど・・・？？？

漏れも5=1だと思う
>>1は削除依頼出しとけな

ハッシュだけで語る事ってあるの？
なんか目のさめるような最新のアルゴリズムでもできたのか？
無いなら終了

vol.1とか書いてるし…
新打法がいいかもね

>>7
どちらにしても「自分のため」にスレを立てたことが見て透けるから叩かれる。

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

>>2-11
ﾊｧ?かってに勘違いしないでくれる？

>>12
ありがとうございます。

良スレage

最近gperf置いてるところなくなってるけど、
特許かなんかに引っかかったのかな？

ここでモナーのAA使って説明してっ！！

Ruby以外は全て糞。

ﾊｯｼｭﾄﾞﾋﾞｰﾌが食べたいけど狂牛病怖いsage

18は既に狂牛病だから問題なし

マジで質問しますが、
オープンアドレス法と、リストチェイン法はどちらが有用ですか？

Ruby

要素数が少ないならオープンアドレス法
多いならその他

>>13
必要な情報手に入れたら終わりかよ？
「語り合って勉強」はどうなったんだ？

ばーーーーーか。

いいから、もう終了。

オープンハッシュ仕事で使ったことないんだけど、役に立つ？
使い勝手が悪い気がする。

まずつかわねーよな

>>25
JavaのHashtableってオープンハッシュじゃない？
使っててびっくりした事があるような。

age

>>23-24
「終了」なんだろ？だったら煽るな低脳。

　　　　　　　　　　　 �d�j　,,　∧＿∧
�d�j (＼／)　　　　　　 ノ|ヽ (　´∀｀)八
／|＼( ´∀｀)／|＼　／ ｜ 　　　'''''´ ｜ ヽ
⌒⌒⊂　:　つ⌒⌒ （ 〃⌒γ　　　　γ⌒ヽ　）
　　　 ∪∪　　　　　　　 　 ∪ ⌒ ∪

>>1よ・・・
http://www.geocities.co.jp/Milano-Killer/6419/1.swf

あのー・・・
最初の書き込み以外は全部偽物なんですけど・・・

>>13とか俺のイメージが悪くなるようなこと言うなよ！
仕事から帰ってきてみればﾋﾞｸｰﾘしたよ！畜生！

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

＃いっとくけど、一方的に教えてもらうつもりはないよ
＃自分でもいろいろ考えてるし、センスがないのも分かってる
＃ただ、色んな人と情報を共有したかっただけだよ

ハッシュは自作する機会が余りないけど、
かなり基本的なデータ構造だからねえ。

>>33
その配列ってハッシュテーブルのこと？

>>33
その話聞いてると、プログラミング向いてないのが判る。
他の事しなさい。

で、ネタ切れ?

>>33

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

単に ASCII コードをそのまま使うのではだめかにゃ？
それにハッシュ値は普通、mod(割り算の余り)を
とるから、配列のサイズがでかくなって困るはずは
ないですよ。

>>37
どう見てそんな大層なもんじゃないよ。

特定の集合について衝突しないハッシュ表が欲しい
とかならgperf使って完全ハッシュ関数を求めれば
良いだけだが、1はそれよりはるか以前のレベル。

>>38
それ思った。

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

これじゃハッシュどころじゃないわな。

もしやハッシュ関数でハッシュ値を求めるのに大きな配列使ってるのか。
12 でキーワード挙げたのに、挙げたのに……

>>38

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

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

modの値をとればいいのかぁ・・・
ありがとう。

配列のサイズというのは、ハッシュテーブルのことです。
余りを利用するからかちあいが生じるのね。
やっと概要を理解してきました。事件の点と点がつながる感じです。

それで、かちあいが生じたときには
次の番号に移すか、リスト構造のチェーンにすればいい、と。
なんとなくですが、あっていますか？

ちなみにPerlの連想配列はどうしているのでしょう？

>>41
さっそくamazonで見てみますね。
情報ありがとう。

>>43

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

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

>>44

すみゃあせん。C言語プログラマ向けなので、
他言語の人はちょっと×でしょう。
C言語を知っていたら、オススメということで。

上の方では何か勝手に煽られてますけど ^^;
プログラム板の人たちはみんないい人ですね。嬉しいです。
私も勉強して、情報をどんどん書き込むつもりでしたが
なかなか追いつけません。ごめんね。
本当に感謝しています。

>>46
使用言語はＣ＋＋です。
たぶん大丈夫だと思います。わざわざありがとう。

>>45
あ、そうなんですか。
２分木だと、探索時間がやっぱりO(logn)になるんですかね。
ハッシュはかちあいがなければ基本的にはO(１)ですよね。

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

>>48

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

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

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

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

長くてスマソ

>>48
C Magazine の今月号のアルゴリズムページで、
そのものズバリな解説をしているので、見るがよろし。
18 日に来月号がでちゃうので、見るならお早めに。

オープンハッシュの削除ってどうやればいい？

＞ハッシュ関数がタコだったとき、O(n) になってしまうこと。

えーと、嘘を書いたかも(汗)。
でも、タコ関数だと、性能が落ちるのは確か。
詳しいことは、ちゃんとした文献で勉強してくださいまし。

>>49 >>50
ありがとう。
C Magazine読んでみます。
でも、あれ難しいんだよなぁ。
理解できるか心配。

ＳＴＬの話は聞いたことがあります。
っていうか、まだ完全なハッシュ関数って開発されてないんだ・・・

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

>>51

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

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

>>54

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

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

私自身は gperf は知らないんですけど、
きっと、そういうツールに違いない(笑)

>>51
削除して、rehashするしか無いんじゃない？

>>57

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

とすると、Perl はどうしてるんだろ。

lisp/schemeスレの過去ログにオープンハッシュの
コードあったけど、>>57の方法だった。

>>59

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

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

# あ、勝手にメリットと思ってるだけで、
# 本当にそうかは知らない。ゴメソ。

オープンハッシュの削除は削除マーク入れるんだよ。
挿入の時に削除マークがあったら、そこに上書きする。

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

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

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

（これくらい教科書やウエブ読めば載ってるんだからさあ、
いちいちスレ立てるのやめようよ。）

良く使うのって
チェイン法＋木
あたりかなあ。

なんだ、結局自分でハッシュ関数を考えていないじゃん。

gperfが吐いたコードって、GPLに従わなくてもいいの？
ソース非公開の商用でも可？

良スレに移行の予感

つか回答出尽くしただろ...移行以前に終了だよ
>>64
Unix板でも逝け。ちなみにGPLに従う必要はない。GCCと同じだ

こういう問題をBASICでやろうとすると
「ああ、マシン語はいいよな」とか思うんだよね。
マシン語だったらオーバーフローが出ようが
フラグが立つだけだからそれに対処するコードを書かないだけの話で
無視してがんがんレジスタに値を加え上げていけばいいだけだから。
BASICだと数値が大きくなるとオーバーフローで止まってしまう。
ダサいなぁとか思いつつmodを入れたりするのだ。
（欲しい所を切り出す必要もあるし）

あ、ダンプリストのチェックサムの話だったかも。
ま、どっちでもいっしょか。

bash

初心者にとってはめちゃくちゃ優良スレッドだよ。ここ。
勉強になった。

tsh

６９＝１ですか？そうですよね？絶対にそうにきまってる！
キミに一言言いたいことがある。
クソスレあ・げ・る・な

>>71
１は上の方でトリップつけて出てきてたじゃん。
変な憶測はやめろよ

なんでハッシュは荒れるの？
ソートじゃ、こうは荒れないよ。

クソスレ決定。多数決で。
とりあえずvol. 1なんてついてるがハッシュでvolいくつまで続けるつもり
だったのかが気になるぞ。

71=74だろ。

>>73
71=74みたいなバカが理解できないから。
ソートはだれでも分かるからだろ。
低レベルな荒らしは無視しる。

とはいえ、誰かがＱを出さんと、
Ａ出す人はいないわけで。。。。
(と、知ったかぶりしたい 37 でも思うわけで)

誰も質問か、問題提起してくれないようなら
そろそろ、終わりかな？

ハッシュに乱数を使うやり方を聞いたことがあるんだが
一体何に使うの？
乱数にしちゃったらキーと番号の対応関係が１対１じゃ
無くなるんじゃないの？

↑
ゴメン、ageだ

あと、ハッシュのメリット、応用例はなに？
例えば、２分探索にすれば探索時間はO(logn)だから
そんなに時間がかからないんじゃ？

>>80
医院の保険証番号による患者のデータベースとか。

車のナンバーとか。

ラーメンのゆであがり時間の予測とか

>>83
センスゼロ。

力道山　＞　それはチョップ。

>>78
もうすこし勉強してこい

>>78
完全ハッシュが作れないからじゃないかなぁ

どこかでハッシュのライブラリを提供してないですか？
ＳＴＬみたいな仕様のものがあると嬉しいです。

Ｃ＃とかＪａｖａでハッシュはあるの？

Javaにはある。入門書の真中あたり。

配列の次に習うのね。

>>87
STLPortじゃ駄目なのか?

gperfちょっと使ってみたけど、アプリの実行中に
ハッシュ表の再作成が出来ないと、利用局面があまり多くない気がするんだけど、
どうなの？

>>92
使い道まちがってる。
gperfが役に立つのは予約語みたいにキー集合が固定の時。
同じコンパイラでも変数表には使う意味なし。
あたりまえだろ？

>93
そうなんだ。
……と、rubyのソースを見てみたら、確かに予約語にしか使ってないね。
gccもたぶんそうかな。

ハッシュドビーフ

まず、用語を共通にしようよ

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

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

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

　・・・・てな感じでいい？

>>96
さんくす

>>96-97
いやもう終わってるんだが…

ハッシュテーブルの数は素数がベストで、2 や 10 の累乗だと
衝突が発生しやすいのでダメらしいけど、その理屈がよく分らない。
素数で割ると、なんで余りの数値が散らばりやすくなるの？

誰かうまく解説してちょ。

>>99
たとえ素数がベストでも、実行速度がベストとは限らんからねぇ。
今の時代、
and 0.5clock
mod 39clock
とかザラだし。

キーに使う値が、たまたま割り切れる数ばかりというのは、よくあることです。
その場合、同じく割り切れやすい値をテーブルサイズにすると、値が集中してしまう。
どんな数でも割れない素数なら比較的安全。
・・・ということではないかと。考えてみました。

しょうがない、ちゃんとやるか（←何様だ）。

ハッシュ法(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)でおさまる。

何も考えないで作るならChain-Hash+BTree

わぁ、結構レスがついてますね。
今日は忙しくてレスできそうにないのですが。

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

>>102
ご丁寧にありがとうございます。

1. オープンアドレス法(closed hash table)
2. チェイニング法(open hash table)

これ良く間違えるんだよな。
オープンハッシュというとどちらの事を言ってるのか...

ハッシュポテト

早くも1は飽きた模様。
やはり自己中教えて君だったか(ﾜﾗ

>>107
済みませんねぇ。私はあなたのような引きこもりと違って
仕事もあるし忙しいのです。
アルゴリズムの勉強も仕事とは関係なく、趣味の領域です。
勉強のペースをあなたごときに左右されたくありません。

>>108
相手によって態度変えすぎ。
スレをゴミにしたくなければ言葉に気を付けてくれ。
仕事をしているならそのくらいはできるよな？

>>108
己の趣味の勉強のために単一質問スレ立てたんでしょ？
そういうのって自己中質問君なんじゃないの？

いくらなんでももう終りでいいんじゃないの、このスレ。
あとは教科書ヨメ。

趣味の勉強如きに金払って教科書買うなんて嫌だね。
検索して解説ページ探すのも時間と手間がかかるから嫌だね。

それではあなたの知っているハッシュ関数をage!ていきましょっい。
elfhash

糞スレ化の予感。
つーか、もうまともな人間にとっては書くこと無い。

あらら・・・
ちょっと毒づいてみたら叩かれてしまうとは・・・ ^ ^;

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

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

まだまだハッシュというデータ構造には
利用すべき範疇があると思っていた私は見当違いでしょうか。
叱咤・激励・ご意見があればお願いします。

http://burtleburtle.net/bob/hash/doobs.html

>>115
もちろんハッシュに利用価値はあるよ。フツーの技術、プログラマの
ジョーシキとして使われてる。例えて言えば「配列」とか「リスト構造」
の次くらいに来る基本的なデータ構造だ。

「配列について」とか言うスレ立てたらどういう反応が来ると思う？

>>117
データ構造としてのハッシュは確かに陳腐なテーマだが、
ハッシュ演算自体には他にも応用があるだろう。
MD5やCRCみたいなデータ同一性の確認方法とか、
全文検索のインデックスに利用するとかな。

それって応用なんて言う程のもんか？
ドキュな漏れでも普通にやってるぞ（藁

1は目的を達したんで来なくなったのかな?

age

SHA-512とかRIPEMD-320とかあるんだね。
漏れの中では、SHA-1, RIPEMD-160で止まってた。

123

なんていうか、CMapはカスだよな。

終焉

>>1
＞あらら・・・
＞ちょっと毒づいてみたら叩かれてしまうとは・・・ ^ ^;

終わったな。弔い晒しage。どっちだ。

ところで文字列のハッシュ値ってどうやって作るの?
h = (s[i] * 11) ^ h;//ﾅﾝﾁｬｯﾃ
で偏るんだけど。

除算法 / 平方採中法 / 乗算法

LFSR法

>>127 じゃあ

h = (s[i] * 101) ^ h;//
にしたら？

age

sage

ハッシュ法なんてプログラマとして覚えてて当然だと思っていたが、
ゲームプログラマで知っている人に出会ったことが無い（これマジで)
だから、不特定データの出現頻度チェックとか糞汚いプログラム書いてんだねー

>文字列のハッシュ値
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の手間を極限まで減らすことが可能。

RubyとかPerlとかPythonとかのハッシュ値の出し方
知ってる人がいたら、紹介キボン。

そーす読め、そーす。

>136
面倒くさいからここで聞いてるに決まってるじゃん。

>>135
Rubyなら大抵のクラスで
hoge.hash


と。

>138
そんなことは聞いてねぇー（藁

とりあえず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]];
}

gperfは完全ハッシュ関数を求めるツール。
ふつうは言語のキーワードとかのコンパイル時に静的に決定されるキーへの
ハッシュ関数を作るときに使うんだが。

例によって手を抜けるところは手を抜いているわけだな＞Ruby

>>141
へー、ちゃんとそういうツールがあるんだねぇ

>>142
手を抜いているってどこらへんのこと?

ハッシュに gperf を使ったり、
正規表現に regex.c 使っているところ。
regex.c は LGPL なんで将来書き直したいと言ってるけどね。

>>140で引用されてるのは、予約語のみを探すのに使う部分で、
hoge.hashので呼び出されるハッシュ関数は何処か別のところに有る筈。
何処に有るかは知らん。

文字列用のハッシュ関数見つけた。
なんか他にも色々あったけどオブジェクトそれぞれに
専用のハッシュ関数を持っているみたい。

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;
}

Use the Source , Luke

ウセ、ザ、ソゥアケ、ルケ

ageんなよ。
gperfの話なんてとっくに終わってるだろ。

>>149
んなこたぁない。

俺は、バイナリツリーとハッシュを知ったときは感動したなぁ。
うれしくって、すぐにプログラムを書いたっけ。

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

最近はフリーソフトを公開してるレベルでも
基礎的なアルゴリズムを知らないから困る・・・

授業で聞いた時は「え、どうやって使うの」という疑問が先に湧いた。
（ぶつかった時の事。チェックサムを求めるみたいな話までしかしてくれなかったから。）
で授業の後で聞きにいっても「そこがまた難しいところで」とかなんとか誤魔化されてしまった。
（一般教養的？な授業だった）
ま、今は使えるけどね。

>>150
んなこたあない。
とっくに終わってる。
スレ読み直せ。

>>153
これから新たに質問のあるやつがいるかもしれないだろ。
自分に必要ないからって終わっていると決めつけるのは愚の骨頂。

>>154
そういってあげんな、おめーは必要としてないだろ

>>151
スレ違いな質問になっちゃうけど、
バイナリツリーで感動出来るプログラムってどんなプログラムがあるの?
ハフマン符号化は確かに感動したけど、それ以外に活用出来る用途を知らない。

>>156
クイックソートとかはどうよ？

void *bsearch(const void * key, const void * base,
　　　　　　　　　　size_t nmemb, size_t size,
　　　　　　　　　　int (* compar)(const void *, const void *));

>>158
それってツリーか?

はさみを使って感動的な切り絵や折り紙を作ったとして、
決してはさみに感動するわけではないと思うが。
（最初に良い道具に出会ったときの感動は抜きにして）

プログラムの話は別として
いい道具には感動するよ。
切れ味のいい切出し小刀とか。
必要もないのにいくつも鉛筆削りたくなったりとか。

スマソ、バイナリサーチだった。
鬱氏

木工はマスタベに陥りやすいので要注意。
（本来の目的を見失いがち。木を削る事自体が快感になるので）

>161
そうそう！
必要もないのに人間を斬りつけたくなったりするよね。
犬猫で我慢するけど（藁

俺は大抵Ｋ＆Ｒに載ってるハッシュ関数
ほとんどそのまま使ってるけどダメ？

>>165
原理が分かっていれば、それでいいと思う。
学習者は自分で書くべし。

Ｂ木とかAVL木のスレ立てて良い？

ﾜﾗﾀ＞[[ハッシュ法統合スレッド]] vol.1

「アルゴリズム全般」とか、そゆ名前にしてくれよな。

全然分からない人は逝ってよしなの？

何に使うワケでもないんだけど、
赤黒木作ってみてね、なんでか50000個に１つ位
ノードが行方不明になるんですよ。
で、紙に赤い腺、黒い線、いっぱい描いて。
仕事してないんだけど、ソース打ってるから。ばれない。

こういう日って幸せだなあ、って。そんな１日でした。

>>171
赤黒木の実装ってわけわかんなくなるよね（ｗ
自作で作るならB木が単純で良い気がする。

で、立てて良いの？

>>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

補前亜毛

詳しく書いてあるページを教えて！

ハッシュって連想配列とか
一時方向変数だっけ？

>>176
ttp://www.ietf.org/rfc/rfc1321.txt
ttp://csrc.nist.gov/publications/fips/fips180-1/fip180-1.txt

米語はいやん

ファイルの内容の比較にハッシュ値を使うのって良い考えと思います？計算量とかどうなのかな、と思いまして。
タイムスタンプとかで比較すると新旧がわかってよいですが、中身がね。

>>180
CRC みたいなもの？

>>180
ふつーMD5

>>180
ファイルサイズ比較->違うなら変更されてる
ハッシュ値を比較->違うなら変更されてる
(タイムスタンプを比較->違うなら変更されている)
ファイルは変更されてない

というのはよく使われるね。ハッシュには衝突の少ないアルゴリズム(MD5など)
を使用する。ファイルがどっちもローカルにあるならMD5の計算をするよりファ
イルの中身を直接比較した方が速いだろうけど、ネットワーク経由ならハッシュ
を使った方がいいことが多いのでは?

1対1で比較ならファイルを直接で良いだろうけど、1対多の場合を考えるとハッシュの方が良いだろうねえ。

>>183
サンキュー
ネットワーク経由でファイルを同期させるってものを考えてます。〈よくあるしくみですが〉
さきにMD5とかで衝突の判定しといたらよさげかなぁとか思いましてね。

他の人もどうも。
バージョン管理が絡んでいますが、1:多とは言えなくてほぼ1：1なのです。
で、みんなはどうしてるのかなぁとか思った、と。

>>185
rsyncとかcvsupのソースでも見たら?

オープンアドレス法とリストチェイン法の違いを教えれ。

>>187
ぶっちゃけて言えばタダの配列対リストの配列

ぶっちゃけすぎ

ぶっかけすぎ

はっちゃけすぎ

　口腔内に射精された精液を気管に詰まらせて窒息寸前になり、１１９番
通報する事故が急増している。オーラルセックスが普及したことで、いわ
ゆる「口内射精」をする人が増えたことが原因。
　１１９番通報してくるのは１８歳未満の若者が圧倒的に多い。オーラル
セックスに不慣れなために、フェラチオ中に思わす射精してしまったり、
逆に、わざと突然射精して女性の反応を楽しもうとして事故に繋がってい
る。
　特に最近増えているのが中学校からの通報。休み時間に校内でセックス
をしたり、セックスには至らないまでもフェラチオをしたりする生徒が増
えたため、通報件数が急上昇している。「高校からの通報件数に追いつく
のは時間の問題」と関係者は語る。
　精液は粘性の高い液体であるため、場合によっては窒息死に至る場合が
ある。救急科の医師は「口内射精をする場合には、必ず相手に意思表示を
してから射精するようにして欲しい。そうすれば事故はかなり防ぐことが
出来る」と話している。

コンパイラにどのようにハッシュが活用されているのか
教えてください。

変数名とかの識別子の高速検索とか。

それぐらいしかハッシュのメリットってないものなの？

>>195
なんだ？
もっとインテリジェントなものを期待してるのか？（ｗ

>>196
サーチをO(1)でこなすのなら、
ハッシュを使ってソートを
更にスピードアップできるのではないか、
と思ったのです。

>>197
なるほど。
確かにソートをO(nlogn)より速くしたいな。

>>199
それができたら何かの賞が取れるだろうな。
できないことを証明されてるかは俺は知らんし。

↑
>>197の間違い。
鬱だ、回線切って素振りしてきます。

夜中にそんなことしてると、職務質問されるぞ。

>>99
そこでさっとテストプログラムを書いてテストしてみないから
99は落ちこぼれなわけです。

初心者への GNU perf のススメ
http://sharl.haun.org/gperf.html

条件が限定されるが、分布かぞえソートがO(nlogn)より速いわけO(n+W)で、
たとえば、ハッシュで16bit以下の世界にマップすれば、それなりに
お望みのものになるかと思われ。

http://pc.2ch.net/test/read.cgi/tech/1005053427/l50
こいつが言ってることはハッシュですか？

>>205
そこのどのレスよ？

>>206
ここのスレよ。

>>207
(ﾟДﾟ)ﾊｧ?

ハッシュ法＝ハヤシライス調理法

なんでSTLにはハッシュがないの？
あれば便利じゃん・・・

ハッシュ関数のあたりが面倒だからだろ。

ハッシュの超基礎的なことが学べる
サイトorメルマガはありませんか？

ハッシュドビーフ

>>212
メルマガでなら最近見たような。

>>212
たくさんあるよ。
どこだかは忘れた。済まん。

>>197
限りなく遅レスだが、ビンソートは一種のそういうものだと思う。

>>216
便ソートってどういうの？

>>217
検索かけてみなされ。

>>218
瓶ソート、だめじゃん・・・

$a{"b"} = "c";

a= { 'b' => 'c'}

>>220
それってPerl？
C++で使うにはどーするのよ？

>>222
map<string,string> a;
a["b"]="c";

>>223
mapはlog(n)の検索時間がかかるんだっけ？

>>222
http://mukun_mmg.tripod.co.jp/mmg/cpp.html
ここのページの１３章ってところで
ハッシュも含めていろんなデータ構造を紹介してるよ。
初心者向けだから分かりやすいのでは？

俺が読んでるメールマガジンだが。

>>225
サンクス！早速登録します。

>>225
斜め読みしたけど、そこの作者って丁寧な人だね。
初心者のとっかかりには分かりやすそう。
メルマガだから図がAAなのは見づらいが。

>>227
同意。メルマガにしては良い方だと思う。

ハッシュ最強

kd-tree 最高

結局最強のハッシュは何よ？

>>225
そのメルマガはだめだろ。
スタイル的に。
発行が最近の日付なに書き方も古すぎ。
作者は勉強して無いと思われ。

ハッシュ　ブラウンズ　朝食には最強！

>>232
２月１日に発行されたよ。
バックナンバーを出すのはいつも遅いけど。

定期age

定期age

ハッシュを使った応用プログラムって何か無い？
今度発表しなきゃならなくて困ってるんだけど・・・

過去ログくらい検索すれ！
http://piza.2ch.net/log/food/kako/958/958184629.html

ハッシュを扱うインターフェイスを設計しているのですが、
Listenする人ならリスナー(Listener)ですよね
ハッシュを扱う人ならハッシャー(Hasher)なんでしょうか？
なんか例外とかいろいろ射出しそうでこわいです

>239
ハッシュを作るのは、シェフ(chef)ですよ。

ちなみに、ハシシュを与えられるのはアサシン(assassin)です。
参考: http://www.google.com/search?hl=ja&q=%90%FC%8C%60%83n%83V%83V%83%85

hashの定義ってﾅﾝﾃﾞすか？

ｈａｓｈあげ