- PR -

HashCodeBuilderよりも衝突が少ないクラス

1
投稿者投稿内容
マリン
常連さん
会議室デビュー日: 2006/05/28
投稿数: 41
投稿日時: 2009-02-24 18:13
SQLのGROUP BY句では対応しづらいデータベース抽出処理がありまして、ちょっと泥臭いですが古典的(？)なキーブレイク判断で抽出後にグループ化するようにしています。
そのグループ化のキーとしてこれまでHashCodeBuilderクラスを使っていたのですが、グループ化されるべきではないレコードがグループ化されてしまう現象に遭遇し、HashCodeBuilderソースを見てみたら意外と衝突が多そうなことに気付きました。ソースから逆算したので当然ですが、例えば「Integer.valueOf(1)と"U"」と「Integer.valueOf(2)と"0"」で全く同一のハッシュコードが返ってきます。

上記のような抽出処理はけっこうあるのでなるべく互換性があって衝突が少ないハッシュを求められるクラスに乗り換えたいと思うのですが、何かよいライブラリ等はありますでしょうか？
もちろん、ないようであればキー情報群を使われる可能性が低そうな区切り文字で無理矢理連結して文字列として比較する(それ相当の独自クラスを作って乗り換える)ことで対応するしかないと思いますが、似たようなことができる解決法があれば教えてください。
わたなべ
大ベテラン
会議室デビュー日: 2007/12/09
投稿数: 123
お住まい・勤務地: 札幌
投稿日時: 2009-02-24 20:28
ご存じかと思いますが、HashCodeBuilderは比較的に一意になる値を返すだけです。
ハッシュである以上はキーとして使うこと自体が間違っているので、「だいたい区別できればいいや」程度のグルーピングはともかく、別の条件でグルーピングされては困るならば、使うべきではないでしょう。

似たような状況は何度か経験はありますが、HogeHogeKeyクラスを作り、hashとequalsを実装した上でMapのキーとして使えば解決します。また、何をもって一意とするのかは業務に依存するわけですから、おそらくはライブラリで解決できないと思います。
武史
ベテラン
会議室デビュー日: 2007/09/21
投稿数: 71
投稿日時: 2009-02-24 20:40
md5 とか、sha とかはどうでしょうか？

もちろん、それでも重複の可能性は否定できないですけどね。
かつのり
ぬし
会議室デビュー日: 2004/03/18
投稿数: 2015
お住まい・勤務地: 札幌
投稿日時: 2009-02-24 22:49
ハッシュコードは等価性を保障するためのものではありません。
ハッシュコードの考え方とはこんな感じです。

・a.equals(b)であれば、a.hashCode() == b.hashCode()である
・!a.equals(b)であっても、a.hashCode() == b.hashCode()の可能性はある

という考え方です。もちろん実装次第です。

たまたまうまく使えそうに見えるからといって、目的通りに使えるとは限りません。
あくまでハッシュテーブル向けの数値でしかありません。

あと若干危険な考え方なので指摘しますが、
引用:

例えば「Integer.valueOf(1)と"U"」と「Integer.valueOf(2)と"0"」で全く同一のハッシュコードが返ってきます。

ハッシュコードはint型なので4バイトまでしか表現できません。
ですので、どんなに衝突を防げるアルゴリズムを使っても、
char型は2バイトですので2文字までの文字列でしか一意性を保障できません。
マリン
常連さん
会議室デビュー日: 2006/05/28
投稿数: 41
投稿日時: 2009-02-25 14:47
ハッシュというと武史様がおっしゃっているようなMD5やSHAのイメージがあったので、そう衝突することもないだろうという安易な考えでHashCodeBuilderを使ってしまいましたが、かつのり様がおっしゃる通りMD5などのハッシュ値空間に比べてHashCodeBuilderはたかだかintの32bit空間しかないことも含めて、そもそもハッシュをキーブレイク判断に使うのが設計ミスであったと改めて感じました。

わたなべ様がおっしゃっているようにグループ化キー情報を持つクラスを作成し、equalsで判定するように修正しようと思います。

ご回答ありがとうございました。
1

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