- PR -

ハッシュ関数について

参照元記事 | 同じ記事を参照しているスレッド一覧
1
投稿者投稿内容
でゅうく
大ベテラン
会議室デビュー日: 2003/11/30
投稿数: 129
投稿日時: 2004-03-02 14:52
ハッシュ関数について調べております。
具体的には、オブジェクトの等価性がオブジェクトの状態のみに依存する場合の、hashCode() メソッドの実装方法です。
そこで、いくつかのコア API の実装を参考にしたところ、以下のようになっていました。
コード:

	// String#hashCode() の実装
	public int hashCode() {
		int h = hash;
		if (h == 0) {
			int off = offset;
			char val[] = value;
			int len = count;

			for (int i = 0; i < len; i++) {
				h = 31 * h + val[off++];
			}
			hash = h;
		}
		return h;
	}

	// AbstractList#hashCode() の実装
	public int hashCode() {
		int hashCode = 1;
		Iterator i = iterator();
		while (i.hasNext()) {
			Object obj = i.next();
			hashCode = 31 * hashCode +
				(obj == null ? 0 : obj.hashCode());
		}
		return hashCode;
	}

String クラスの JavaDoc にも以下のような記述がありました。
引用:

この文字列のハッシュコードを返します。String のハッシュコードは、次の方法で計算します。

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

int 算術を使います。s[i] は文字列の i 番目の文字、n は文字列の長さ、^ はべき乗を示します。
空の文字列のハッシュ値は 0 です。


一方、AbstractSet や AbstractMap では、構成要素のハッシュ値をただ合計しているだけです。

hashCode() メソッドの戻り値は、そのオブジェクトのダイジェスト値だと云う認識でいます。
AbstractSet 等の実装方法は単純でわかりやすいのですが、何故 String 等が 上記のような実装になっているのかがわかりません。
何か理由がある（シノニムが発生しにくいとか？）のだと思うのですが・・・。

String や abstractList 等での hashCode() アルゴリズムの意図は何でしょうか？
また、｢31｣という数値にはどんな意味があるのでしょうか？（ただ素数ってだけ？）

ご存知の方、お教え下さいませ。
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2004-03-02 15:15
unibon です。こんにちわ。

引用:

でゅうくさんの書き込み (2004-03-02 14:52) より:
一方、AbstractSet や AbstractMap では、構成要素のハッシュ値をただ合計しているだけです。

AbstractList などの List や、String は、要素の順序を意味のあるものとしますが、Set や Map は要素の順序に意味がないし、意味があるものとして取り扱ってはいけないためです。これは同じものなら hashCode の値は同じでなければならないことに由来します。特定の要素に 31 などを掛けて重み付けを要素ごとに違えるのは、要素の順序を加味してしまっています。
ちなみに、違うものでも hashCode は同じ値でもよいです。しかし、ハッシュという目的のためには、違うものはできるだけ違う値になるほうが望ましいです。しかし、同じものは同じ値になる、ということは絶対必要です。
だから、List や String で 31 を掛けないのは許されますが、Set や Map で 31 を掛けるようなことはダメです。

引用:

でゅうくさんの書き込み (2004-03-02 14:52) より:
また、｢31｣という数値にはどんな意味があるのでしょうか？（ただ素数ってだけ？）

どうなんでしょう。素数に意味はありますが、なぜ 31 なのかは分かりません。このあたりについてはうろ覚えですが Effective Java あたりの本に書いてあったような気もします。

＃以下、あとで追加。
上記の「同じもの」・「違うもの」とは、equals が成り立つか成り立たないかを意味します。

[ メッセージ編集済み 編集者: unibon 編集日時 2004-03-02 15:19 ]
coasm
大ベテラン
会議室デビュー日: 2001/11/26
投稿数: 237
投稿日時: 2004-03-02 15:28
ListやStringは要素の並び順が意味を持っている
（同じ要素だけを含んでいた場合でも並び準が異なると等しくない）ので、
並び順を反映するようなハッシュコードを用いた方が（衝突が減るので）効率的です。
この場合、（各要素の単純合計をとるような）並び順を反映しない実装にしたとしても、
それは効率の面で「良くない」実装ですが、「間違っている」わけではありません。

一方、Set や Map では、要素の並び順は意味を持ちません。
{"A","B","C"} というSetと { "C", "B", "A"} というSetは等しいのです。
したがって、equals()やhashCode()の実装は要素の並び順を反映しない
ものでなければなりません。

「31」という数値は、
・それが素数である。
・2**n - 1　という形をしているので、コンパイラによる最適化を期待できる。
という理由で選ばれたのではないでしょうか。
でゅうく
大ベテラン
会議室デビュー日: 2003/11/30
投稿数: 129
投稿日時: 2004-03-02 17:24
unibon さん、coasm さん、わかり易い解説ありがとうございます。
おかげ様で、もやもやが晴れてスッキリしました。
独りで考えていると、なかなか気が付かないもんですね。
かずくん
ぬし
会議室デビュー日: 2003/01/08
投稿数: 759
お住まい・勤務地: 太陽系第三惑星
投稿日時: 2004-03-02 19:49
素数かけると、ハッシュ表がよくばらつくようになる、ってEffective Javaにかいてあったような気がします。
今手元にないので、うる覚えです。
佐々木
大ベテラン
会議室デビュー日: 2003/03/30
投稿数: 121
投稿日時: 2004-03-02 20:05
引用:

かずくんさんの書き込み (2004-03-02 19:49) より:
素数かけると、ハッシュ表がよくばらつくようになる、ってEffective Javaにかいてあったような気がします。
今手元にないので、うる覚えです。


こんなんです。
Effective Java P38 より(日本語版初版第5刷)
引用:

素数を使用することの利点は、あまり明確ではありませんが、このような目的には伝統的に素数が使用されています。

こういう「普通こうするもんだよ」っていう引き出しをたくさん持ってるとデヴェロッパ人生が豊かになりますね。
ちいにぃ
大ベテラン
会議室デビュー日: 2002/05/28
投稿数: 244
投稿日時: 2004-03-02 20:44
Jakarta Commons Langに、hashCode()の実装を支援するビルダクラス
HashCodeBuilder があります。この実装はEffective Javaの方式にしたがってますね。
最近存在に気がつき、気に入って使ってます。

Commons Lang

HashCodeBuilder (API Reference)

# このパッケージには他にEqualsBuilderとかCompareToBuilderとか
# ReflectionToStringBuilder (perlのData::Dumperに似てるかも) があり、
# 重宝してます。
1

スキルアップ／キャリアアップ（JOB@IT）