- - PR -
ハッシュ関数について
1
投稿者 | 投稿内容 | ||||||||
---|---|---|---|---|---|---|---|---|---|
|
投稿日時: 2004-03-02 14:52
ハッシュ関数について調べております。
具体的には、オブジェクトの等価性がオブジェクトの状態のみに依存する場合の、hashCode() メソッドの実装方法です。 そこで、いくつかのコア API の実装を参考にしたところ、以下のようになっていました。
String クラスの JavaDoc にも以下のような記述がありました。
一方、AbstractSet や AbstractMap では、構成要素のハッシュ値をただ合計しているだけです。 hashCode() メソッドの戻り値は、そのオブジェクトのダイジェスト値だと云う認識でいます。 AbstractSet 等の実装方法は単純でわかりやすいのですが、何故 String 等が 上記のような実装になっているのかがわかりません。 何か理由がある(シノニムが発生しにくいとか?)のだと思うのですが・・・。 String や abstractList 等での hashCode() アルゴリズムの意図は何でしょうか? また、「31」という数値にはどんな意味があるのでしょうか?(ただ素数ってだけ?) ご存知の方、お教え下さいませ。 | ||||||||
|
投稿日時: 2004-03-02 15:15
unibon です。こんにちわ。
AbstractList などの List や、String は、要素の順序を意味のあるものとしますが、Set や Map は要素の順序に意味がないし、意味があるものとして取り扱ってはいけないためです。これは同じものなら hashCode の値は同じでなければならないことに由来します。特定の要素に 31 などを掛けて重み付けを要素ごとに違えるのは、要素の順序を加味してしまっています。 ちなみに、違うものでも hashCode は同じ値でもよいです。しかし、ハッシュという目的のためには、違うものはできるだけ違う値になるほうが望ましいです。しかし、同じものは同じ値になる、ということは絶対必要です。 だから、List や String で 31 を掛けないのは許されますが、Set や Map で 31 を掛けるようなことはダメです。
どうなんでしょう。素数に意味はありますが、なぜ 31 なのかは分かりません。このあたりについてはうろ覚えですが Effective Java あたりの本に書いてあったような気もします。 #以下、あとで追加。 上記の「同じもの」・「違うもの」とは、equals が成り立つか成り立たないかを意味します。 [ メッセージ編集済み 編集者: unibon 編集日時 2004-03-02 15:19 ] | ||||||||
|
投稿日時: 2004-03-02 15:28
ListやStringは要素の並び順が意味を持っている
(同じ要素だけを含んでいた場合でも並び準が異なると等しくない)ので、 並び順を反映するようなハッシュコードを用いた方が(衝突が減るので)効率的です。 この場合、(各要素の単純合計をとるような)並び順を反映しない実装にしたとしても、 それは効率の面で「良くない」実装ですが、「間違っている」わけではありません。 一方、Set や Map では、要素の並び順は意味を持ちません。 {"A","B","C"} というSetと { "C", "B", "A"} というSetは等しいのです。 したがって、equals()やhashCode()の実装は要素の並び順を反映しない ものでなければなりません。 「31」という数値は、 ・それが素数である。 ・2**n - 1 という形をしているので、コンパイラによる最適化を期待できる。 という理由で選ばれたのではないでしょうか。 | ||||||||
|
投稿日時: 2004-03-02 17:24
unibon さん、coasm さん、わかり易い解説ありがとうございます。
おかげ様で、もやもやが晴れてスッキリしました。 独りで考えていると、なかなか気が付かないもんですね。 | ||||||||
|
投稿日時: 2004-03-02 19:49
素数かけると、ハッシュ表がよくばらつくようになる、ってEffective Javaにかいてあったような気がします。
今手元にないので、うる覚えです。 | ||||||||
|
投稿日時: 2004-03-02 20:05
こんなんです。 Effective Java P38 より(日本語版初版第5刷)
こういう「普通こうするもんだよ」っていう引き出しをたくさん持ってるとデヴェロッパ人生が豊かになりますね。 | ||||||||
|
投稿日時: 2004-03-02 20:44
Jakarta Commons Langに、hashCode()の実装を支援するビルダクラス
HashCodeBuilder があります。この実装はEffective Javaの方式にしたがってますね。 最近存在に気がつき、気に入って使ってます。 Commons Lang HashCodeBuilder (API Reference) # このパッケージには他にEqualsBuilderとかCompareToBuilderとか # ReflectionToStringBuilder (perlのData::Dumperに似てるかも) があり、 # 重宝してます。 |
1