外部インターフェースがHashMapのhashCode / equalsを提供することを許可しないのはなぜですか？
https://stackoverflow.com/questions/214136
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
TreeMap を使用すると、カスタムの Comparator を提供するのは簡単です。したがって、マップに追加された Comparable オブジェクトによって提供されるセマンティクスをオーバーライドします。ただし、 HashMap はこの方法では制御できません。ハッシュ値と等価性チェックを提供する関数は「サイドロード」できません。
インターフェイスを設計し、これを HashMap （または新しいクラス）に後付けするのは簡単で便利だと思いますか？より良い名前を除いて、このようなもの：
interface Hasharator<T> {
int alternativeHashCode(T t);
boolean alternativeEquals(T t1, T t2);
}
class HasharatorMap<K, V> {
HasharatorMap(Hasharator<? super K> hasharator) { ... }
}
class HasharatorSet<T> {
HasharatorSet(Hasharator<? super T> hasharator) { ... }
}
大文字と小文字を区別しない Map 問題は簡単な解決策になります：
new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY);
これは実行可能でしょうか、またはこのアプローチに根本的な問題がありますか？
既存の（非JRE）ライブラリでアプローチが使用されていますか？ （グーグルで試してみましたが、運がありません。）
編集：hazzenが提示した素晴らしい回避策ですが、これは回避しようとしている回避策だと思います...;）
編集：タイトルが＆quot; Comparator＆quot;に言及しないように変更されました。これは少しわかりにくいと思います。
編集：パフォーマンスに関して受け入れられた回答。より具体的な回答が必要です！
編集：実装があります。以下の承認済みの回答を参照してください。
編集：最初の文を言い換えて、それが私が求めているサイドローディングであることをより明確に示すようにしました（順序付けではなく、順序付けはHashMapに属しません）。
解決 4
Trove4j には、私が求めている機能があり、ハッシュ戦略と呼ばれています。
マップにはさまざまな制限があり、したがって前提条件も異なる実装があるため、Javaの「ネイティブ」実装が暗黙的に意味されるわけではありません。 HashMapは実現可能です。
他のヒント
少し遅れましたが、将来の訪問者にとって、commons-collectionsには AbstractHashedMap （ 3.2.2 および 4.0 ） 。これらの保護されたメソッドをオーバーライドして、目的の動作を実現できます。
protected int hash(Object key) { ... }
protected boolean isEqualKey(Object key1, Object key2) { ... }
protected boolean isEqualValue(Object value1, Object value2) { ... }
protected HashEntry createEntry(
HashEntry next, int hashCode, Object key, Object value) { ... }
このような代替 HashedMap の実装例は、commons-collections独自の IdentityMap （ 3.2.2 Javaには独自のもの（1.4以降）。
これは、外部の＆quot; Hasharator ＆quot;を提供するほど強力ではありません。 Map インスタンスに。ハッシュ戦略ごとに新しいマップクラスを実装する必要があります（構成と継承の逆戻り...）。しかし、知っておくといいでしょう。
.NETには、IEqualityComparer（2つのオブジェクトを比較できるタイプの場合）およびIEquatable（それ自体を別のインスタンスと比較できるタイプの場合）があります。
実際、java.lang.ObjectまたはSystem.Objectで平等とハッシュコードを定義するのは間違いだったと思います。特に平等は、継承で意味のある方法で定義するのが困難です。私はこれについてブログを書く意味を持ち続けています...
しかし、はい、基本的にはアイデアは健全です。
HashingStrategy はあなたが探しているコンセプトです。これは、equalsとhashcodeのカスタム実装を定義できる戦略インターフェースです。
public interface HashingStrategy<E>
{
int computeHashCode(E object);
boolean equals(E object1, E object2);
}
組み込みの HashSet または HashMap で HashingStrategy を使用することはできません。 GSコレクションには、 UnifiedSetWithHashingStrategy というjava.util.Setとjava .util.Mapは UnifiedMapWithHashingStrategy と呼ばれます。
例を見てみましょう。
public class Data
{
private final int id;
public Data(int id)
{
this.id = id;
}
public int getId()
{
return id;
}
// No equals or hashcode
}
UnifiedSetWithHashingStrategy を設定して使用する方法は次のとおりです。
java.util.Set<Data> set =
new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(Data::getId));
Assert.assertTrue(set.add(new Data(1)));
// contains returns true even without hashcode and equals
Assert.assertTrue(set.contains(new Data(1)));
// Second call to add() doesn't do anything and returns false
Assert.assertFalse(set.add(new Data(1)));
なぜ Map を使用しないのですか？ UnifiedSetWithHashingStrategy は、 UnifiedMap の半分のメモリを使用し、 HashMap の4分の1のメモリを使用します。また、便利なキーがなく、タプルのような合成キーを作成する必要がある場合もあります。それはより多くのメモリを無駄にする可能性があります。
検索を実行するにはどうすればよいですか？セットには contains（）がありますが、 get（）はありません。 UnifiedSetWithHashingStrategy は、 Set に加えて Pool を実装するため、 get（）の形式も実装します。
大文字と小文字を区別しない文字列を処理する簡単な方法を次に示します。
UnifiedSetWithHashingStrategy<String> set =
new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(String::toLowerCase));
set.add("ABC");
Assert.assertTrue(set.contains("ABC"));
Assert.assertTrue(set.contains("abc"));
Assert.assertFalse(set.contains("def"));
Assert.assertEquals("ABC", set.get("aBc"));
これはAPIを示していますが、実稼働には適していません。問題は、HashingStrategyが String.toLowerCase（）に常に委任して、ガベージ文字列の束を作成することです。大文字と小文字を区別しない文字列に対して効率的なハッシュ戦略を作成する方法を次に示します。
public static final HashingStrategy<String> CASE_INSENSITIVE =
new HashingStrategy<String>()
{
@Override
public int computeHashCode(String string)
{
int hashCode = 0;
for (int i = 0; i < string.length(); i++)
{
hashCode = 31 * hashCode + Character.toLowerCase(string.charAt(i));
}
return hashCode;
}
@Override
public boolean equals(String string1, String string2)
{
return string1.equalsIgnoreCase(string2);
}
};
注：私はGSコレクションの開発者です。
注：他のすべての回答で述べたように、HashMapsには明示的な順序はありません。彼らは「平等」のみを認識します。ハッシュベースのデータ構造から順序を取得することは、各オブジェクトがハッシュ（基本的には乱数）に変換されるため、意味がありません。
慎重に行う限り、クラスのハッシュ関数をいつでも作成できます（多くの場合、必要です）。ハッシュベースのデータ構造は、ハッシュ値のランダムで均一な分布に依存しているため、これを適切に行うのは困難です。効果的なJavaでは、適切な動作でハッシュメソッドを適切に実装するためのテキストが大量にあります。
以上のことから、ハッシュで String の大文字小文字を無視したい場合は、この目的のために String の周りにラッパークラスを記述し、代わりにデータ構造内にあります。
簡単な実装：
public class LowerStringWrapper {
public LowerStringWrapper(String s) {
this.s = s;
this.lowerString = s.toLowerString();
}
// getter methods omitted
// Rely on the hashing of String, as we know it to be good.
public int hashCode() { return lowerString.hashCode(); }
// We overrode hashCode, so we MUST also override equals. It is required
// that if a.equals(b), then a.hashCode() == b.hashCode(), so we must
// restore that invariant.
public boolean equals(Object obj) {
if (obj instanceof LowerStringWrapper) {
return lowerString.equals(((LowerStringWrapper)obj).lowerString;
} else {
return lowerString.equals(obj);
}
}
private String s;
private String lowerString;
}
良い質問、ジョシュ・ブロッホに聞いてください。私はJava 7でその概念をRFEとして提出しましたが、それは破棄されました、理由はパフォーマンスに関連する何かだったと思います。しかし、私は同意すべきでした。
hashCodeキャッシングを妨げるため、これが行われていないと思われますか？
すべてのキーが静かにラップされる一般的なマップソリューションを作成しようとしました。ラッパーは、ラップされたオブジェクト、キャッシュされたhashCode、および等価チェックを行うコールバックインターフェイスへの参照を保持する必要があることが判明しました。これは明らかに、元のキーともう1つのオブジェクトをキャッシュするだけでよいラッパークラスを使用するほど効率的ではありません（hazzensの回答を参照）。
（ジェネリックに関連する問題にもぶつかりました; getメソッドは入力としてObjectを受け入れるため、ハッシュを行うコールバックインターフェイスは追加のinstanceof-checkを実行する必要があります。それまたはマップクラスはそのキーのクラスを知っています。）
これは興味深いアイデアですが、パフォーマンスにとっては非常に恐ろしいことです。この理由は、ハッシュテーブルのアイデアの非常に基本的なものです。順序は信頼できません。ハッシュテーブルは非常に高速です（一定時間）。テーブルの要素にインデックスを付ける方法のためです。 ：その要素の疑似一意整数ハッシュを計算し、配列内のその場所にアクセスすることにより。文字通りメモリ内の位置を計算し、要素を直接保存しています。
これは、ルートで開始し、ルックアップが必要になるたびに目的のノードに到達する必要があるバランスの取れたバイナリ検索ツリー（ TreeMap ）とは対照的です。ウィキペディアには、詳細な分析があります。要約すると、ツリーマップの効率は一貫した順序に依存しているため、要素の順序は予測可能であり、健全です。ただし、「目的地へのトラバース」によって課せられるパフォーマンスヒットのため、アプローチでは、BSTは O（log（n））パフォーマンスのみを提供できます。大きなマップの場合、これはパフォーマンスに大きな影響を与える可能性があります。
ハッシュテーブルに一貫した順序を設定することは可能ですが、そのためには、 LinkedHashMap に似た手法を使用し、順序を手動で維持する必要があります。または、ハッシュテーブルとツリーという2つの個別のデータ構造を内部的に維持できます。テーブルはルックアップに使用でき、ツリーは反復に使用できます。もちろん問題は、必要なメモリの2倍以上を使用することです。また、挿入はツリー（O（log（n）））と同じ速さしかありません。コンカレントトリックはこれを少し下げることができますが、それは信頼できるパフォーマンス最適化ではありません。
要するに、あなたのアイデアは本当に良いサウンドですが、実際にそれを実装しようとすると、そうすることはパフォーマンスに大きな制限を課すことがわかります。最終的な判定は（そして何十年も続いています）：パフォーマンスが必要な場合は、ハッシュテーブルを使用します。順序付けが必要で、パフォーマンスが低下しても問題ない場合は、バランスの取れたバイナリ検索ツリーを使用します。どちらか一方の保証の一部を失うことなく、2つの構造を効率的に組み合わせることは本当にできないのではないかと思います。
com.google.common.collect.CustomConcurrentHashMap にはそのような機能がありますが、残念ながら、現在のところ Equivalence を設定する方法は公開されていません（ Hasharator ）。彼らはまだそれを使っていないかもしれませんし、多分彼らはその機能が十分に役立つとは考えていないかもしれません。 guavaメーリングリストで質問してください。
このトーク 2年以上前。
