14

を使用TreeMapして custom を提供するのは簡単です。したがって、マップに追加されたオブジェクトComparatorによって提供されるセマンティクスをオーバーライドします。ただし、この方法では制御できません。ハッシュ値と等価性チェックを提供する関数は「サイドロード」できません。ComparableHashMap

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 によって提示された素晴らしい回避策ですが、これは私が回避しようとしている回避策です... ;)

編集: タイトルを変更して、「コンパレーター」について触れないようにしました。これは少し混乱したと思います。

編集：パフォーマンスに関連して受け入れられた回答。より具体的な答えが欲しいです！

編集: 実装があります。以下の受け入れられた回答を参照してください。

編集:最初の文を言い換えて、それが私が求めているサイドローディングであることをより明確に示します(順序付けではありません。順序付けは HashMap に属しません)。

4

9 に答える 9

9

.NET は、IEqualityComparer (2 つのオブジェクトを比較できる型の場合) と IEquatable (自分自身を別のインスタンスと比較できる型の場合) を介してこれを行います。

実際、java.lang.Object や System.Object で等価性とハッシュコードを定義するのは、まったく間違いだったと思います。特に等価性は、継承で意味のある方法で定義するのが困難です。私はこれについてブログを書くつもりです...

しかし、はい、基本的にアイデアは健全です。

于 2008-10-17T23:40:48.160 に答える
4

Trove4jには私が求めている機能があり、彼らはそれをハッシュ戦略と呼んでいます。

彼らのマップには、さまざまな制限があり、したがってさまざまな前提条件を持つ実装があるため、これは、Java の「ネイティブ」HashMap の実装が実現可能であることを暗に意味するものではありません。

于 2009-12-09T20:42:35.497 に答える
3

注:他のすべての回答で述べたように、HashMaps には明示的な順序付けがありません。彼らは「平等」しか認識していません。各オブジェクトがハッシュ (基本的には乱数) に変換されるため、ハッシュベースのデータ構造から順序を取得しても意味がありません。

慎重に行う限り、クラスのハッシュ関数をいつでも作成できます (多くの場合、作成する必要があります)。ハッシュベースのデータ構造はハッシュ値のランダムで均一な分布に依存しているため、これを適切に行うのは困難です。効果的な Java には、適切な動作をするハッシュ メソッドを適切に実装することに専念する大量のテキストがあります。

以上のことから、ハッシュ処理で a の大文字と小文字を区別したくない場合は、この目的のために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;
}
于 2008-10-17T23:09:31.810 に答える
0

これは興味深いアイデアですが、パフォーマンスに関してはまったくひどいものです。この理由は、ハッシュテーブルの考え方にとって非常に基本的なものです。つまり、順序付けに依存することはできません。ハッシュテーブルは、テーブル内の要素にインデックスを付ける方法により、非常に高速です (定数時間)。その要素の疑似一意の整数ハッシュを計算し、配列内のその場所にアクセスすることによります。文字通り、メモリ内の場所を計算し、要素を直接保存しています。

TreeMapこれは、ルックアップが必要になるたびにルートから開始し、目的のノードまで下っていく必要がある平衡二分探索木 ( ) とは対照的です。ウィキペディアには、さらに詳細な分析があります。要約すると、ツリー マップの効率は一貫した順序に依存するため、要素の順序は予測可能で正常です。ただし、「目的地までのトラバース」アプローチによってパフォーマンスが低下するため、BST はO(log(n))パフォーマンスしか提供できません。大きなマップの場合、これはパフォーマンスに大きな影響を与える可能性があります。

LinkedHashMapハッシュテーブルに一貫した順序を課すことは可能ですが、そうするには、順序を手動で維持するのと同様の手法を使用する必要があります。あるいは、ハッシュテーブルとツリーという 2 つの別個のデータ構造を内部で維持することもできます。テーブルはルックアップに使用でき、ツリーは反復に使用できます。もちろん問題は、これが必要なメモリの 2 倍以上を使用することです。また、挿入はツリーと同じくらい高速です: O(log(n))。同時実行のトリックでこれを少し下げることができますが、それは信頼できるパフォーマンスの最適化ではありません。

要するに、あなたのアイデアは非常に良さそうに見えますが、実際に実装しようとすると、大幅なパフォーマンスの制限が課せられることがわかります。最終的な判断は次のとおりです (そして何十年もの間): パフォーマンスが必要な場合は、ハッシュテーブルを使用してください。順序付けが必要で、パフォーマンスの低下に耐えられる場合は、バランスのとれた二分探索木を使用してください。残念ながら、どちらか一方の保証の一部を失うことなく、2 つの構造を効率的に組み合わせる方法はありません。

于 2008-10-18T16:26:48.203 に答える
0

良い質問です。josh bloch に聞いてください。私はその概念を Java 7 の RFE として提出しましたが、削除されました。その理由はパフォーマンスに関連したものだと思います。私は同意しますが、行われるべきでした。

于 2008-10-18T01:35:09.833 に答える
0

hashCode のキャッシングが妨げられるため、これが行われていないのではないかと思います。

すべてのキーが静かにラップされる一般的な Map ソリューションを作成しようとしました。ラッパーは、ラップされたオブジェクト、キャッシュされた hashCode、および等価性チェックを担当するコールバック インターフェイスへの参照を保持する必要があることが判明しました。これは明らかに、元のキーともう1つのオブジェクトをキャッシュするだけでよいラッパークラスを使用するほど効率的ではありません（hazzensの回答を参照）。

(ジェネリックに関連する問題にも遭遇しました。get メソッドはオブジェクトを入力として受け入れるため、ハッシュを担当するコールバック インターフェイスは追加の instanceof-check を実行する必要があります。それか、マップ クラスがクラスを認識している必要があります。そのキーの。)

于 2008-10-18T15:43:56.700 に答える
0

にはそのような機能がありますが、残念ながら、 (自分の)com.google.common.collect.CustomConcurrentHashMapを設定する一般的な方法は現在ありません。たぶん、彼らはまだ使い終わっていないのかもしれませんし、機能が十分に有用であるとは考えていないのかもしれません。guava メーリング リストで質問してください。EquivalenceHasharator

2 年以上前にこの講演で言及されていたのに、なぜまだ実現していないのだろうか。

于 2011-04-18T10:54:45.037 に答える