https://twitter.com/kinaba のログ (twilog の方が便利です。)
| @cocoatomo うーん、よくわかりません。たとえば http://ibm.co/gwHMdq で 31倍して足しているのはなぜそれで良いのか、とか、的なことを読んだことが無くて。奇数なのはその方が情報ロスがないから、というのは見るけれどじゃあこれを3に変えてもいいのか (続 | |
| @cocoatomo 続) それとも3ではマズいのか、の判断ができない…。Javaなら「commons先生がそう言っているので任せる」でいいんですけど、HashCodeBuilder相当のものを他言語で作ろう、という時に理由を理解せずデッドコピーではいかんなーと… | |
| @cocoatomo お、これは面白そうなドキュメントですね。ありがとうございます自分も読んでみます。 @kumagi さんとの会話を見逃していました...不覚(^^;; | |
| ハッシュ関数について教えておしえてもらったページ読んでる http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/ と https://svn.apache.org/repos/asf/tuscany/sca-cpp/trunk/kernel/hash.hpp 。前者はなんかこれ書いた人わかってないんじゃないか感があるのでまあいいや…。後者(のtimes33hashのコメント)は面白そげ | |
| 掛け算式のハッシュ計算だと、実験してみたら奇数ならだいたいあんまり変わらなかった（たぶんハッシュ表のサイズが2のベキ乗として実験してるんだと推測）のでシフトで計算しやすい乗数を選びますよー的なことが書いてある。それでどっちにも適切に説明されたことはないと書いてあるがホンマかいな | |
| 自分の疑問点をもう一度ランダムにまとめよう。「ハッシュ表のキーとして使う用途において、複数のハッシュ値を合成して一つのハッシュ値にまとめる良い計算式は何か。複数というのは2個や3個の固定個数の場合も、可変個数の場合もどっちも知りたい」。 | |
| 「hash=hash*31+new_data; という更新式で足し込む物を結構見かける。31は33だったりも。で、h=(h*A+d)%M形の式なら、AとMが互いに素な方が情報落ちなくて良いというのはまあわかる。Mが不明ならAが素数の方がその意味で良いという主張も良しとしよう。」 | |
| 「で、じゃあ互いに素なら何でもいいのか。それとも違ったりするのか。31掛けを使っている文献は割と8bit文字列のハッシュ化に使っているものが多い気がするんだけど、32bitハッシュ値の配列の合成に同じ31を使うのってOKなんすか本当に」 | |
| 「あとそもそも、掛けて足すという演算ってえらく単純だけど、乱数生成だとそれがマズいとよく言われていると思うけどハッシュ関数はそれでいいのはなんでみたいな疑問も」 | |
| 「何がいい悪いというのは結局、「同時にハッシュ表に突っ込まれやすいデータが別のハッシュ値になりやすい」のが良い、ので同時にハッシュ表に突っ込まれやすいデータとは統計的にどんなであるかに依るわけだけど、そういうデータってないのかなとか」 | |
| http://burtleburtle.net/bob/hash/hashfaq.html と http://burtleburtle.net/bob/hash/evahash.html の "permute and no funnel" という基準は非常に明確でいい感じだ | |
| Hash functions: An empirical comparison http://www.strchr.com/hash_functions そういえば文字列のハッシュ化はドラゴンブックの旧版に色々書いてあった気がするな…売ってしまったよ… | |
| @finalfusion 文字列のハッシュ化にはとりあえず全く興味が無いのですが、たぶん関係が無いことは無いだろうなーくらいの。 | |
| @xagawa そういうことになるんでしょうか。自分でもよくわかっていないです(^^;。「型Aの値の十分良いハッシュ関数faと型Bの十分良いfbが既に存在するときにpair<A,B>のハッシュ関数をfaとfbから作る時に気にした方がいいポイントが仮に何かあるとすればそれは何か」 | |
| @xagawa ふむ。そうなりますね。 | |
| ところでそろそろいい加減screenの使い方を覚えないと業務に差し支える気がしてきているので覚えるか | |
| @karatsubaki おつかれさまです… | |
| @filil 新しい方も実家に置いてきてしまったのですぐに確かめられないのですが、コードが全部Javaになってハッシュ表は標準ライブラリの使えば済むようになってしまったので、その辺全部簡略化されてたように記憶しています。もしかしたら僕が読み飛ばしただけかも…(自信ない | |
| @sumita12 複数開きたいというよりは、デタッチして複数のマシンでセッションを持ち回りたい欲求が… |