4

多くの場合、ハッシュ マップを使用する際のパフォーマンスのボトルネックはequalsメソッドです。equals深いデータ構造の場合、非常に高価になる可能性があります。

以下は不変のハッシュマップに関するものであることに注意してください。したがって、少なくともキーを削除することはありません。キーの追加は問題ないと思います。

安全でないget

クエリされたキーが確実に含まれているハッシュ マップをクエリするとします。次に、指定されたキーに衝突がない場合、見つかった単一のエントリは、クエリされたオブジェクトでなければならないため、ハッシュ ヒットに基づいて返すことができます。

これにより、ほとんどの場合 (衝突がない場合) の呼び出しを回避できequalsます。get

質問

  1. この概念はどのように呼ばれますか?
  2. getこのような安全でない操作をサポートする、Java または Scala で使用可能なハッシュ マップの実装はありますか?

ところで、より良い件名の提案をお待ちしています。

4

4 に答える 4

7

この概念はどのように呼ばれますか？

アイデンティティマップ。equals()要素を探すときに呼び出されず、IDを使用するだけです（つまり==）。

正しい解決策は、マップを「修正」することではなく、デフォルトを使用するキーのみを使用することですObject.equals()。

public boolean equals( Object other ) { return this == other; }

問題は、すべてのキーがシングルトンでない限り、このマップで要素を見つけることが問題になる可能性があることです。したがってString、たとえば、Javaはすべての文字列インスタンスがインターンされることを保証しないため、を使用することはできません。同じことが当てはまりますInteger：インスタンス<-128と>127は異なります。

ただし、キーに独自の最適化された実装を使用する場合は、これを解決できます。

于 2012-11-19T10:36:03.290 に答える
4

このようなデータ構造は、安全ではないため、私の知る限り存在しません。特定の状態を確実にエンコードする方法はありません。

しかし残念なことに、Scala Collection Library を使用すると、新しい豊富なデータ構造を少量の新しいコードで非常に迅速に実装できます。リクエストの実装は次のとおりです。

class ParticularHashMap[A, +B] private(buckets: Vector[List[(A, B)]]) extends Map[A, B]{

    def this() = this(Vector.fill(ParticularHashMap.BucketsNo)(List.empty))

    def get(key: A) = {
        val bucket = buckets(bucketIndex(key))

        bucket match {
            case List((_, v)) => Some(v) //YOUR SPECIAL OPTIMIZATION !
            case list => list.find(key == _._1).map(_._2)
        }
    }

    def iterator = buckets.flatten.iterator

    def -(key: A) = mkWithUpdatedBucket(key, _ filterNot (_._1 == key))

    def +[B1 >: B](kv: (A, B1)) = mkWithUpdatedBucket(kv._1, insert(kv._1, kv._2.asInstanceOf[B], _))

    //if you're wondering why it's Bucket[A, Any] and not Bucket[A, B] it's because of the covariance of B
    private def mkWithUpdatedBucket(key: A, f: Bucket[A, Any] => Bucket[A, Any]) = {
        val index = bucketIndex(key)
        val newBucket = f(buckets(index))
        (new ParticularHashMap[A, Any](buckets.updated(index, newBucket))).asInstanceOf[ParticularHashMap[A, B]]
    }

    private def insert(k: A, v: Any, bucket: List[(A, Any)]): Bucket[A, Any] = bucket match {
        case List() => List((k, v))
        case (k1, v1) :: kvs if k == k1 => (k, v) :: kvs
        case (k1, v1) :: kvs => (k1, v1) :: insert(k, v, kvs)
    }

    private def bucketIndex(key: A) = Math.abs(key.hashCode()) % ParticularHashMap.BucketsNo
}

object ParticularHashMap {
    private val BucketsNo = 256

    private type Bucket[+A, +B] = List[(A, B)]

    def apply[A, B](kvs: (A, B)*) = new ParticularHashMap[A, B] ++ kvs

}

これは単純な実装であることに注意してください。ただし、ニーズに合わせて改善することもできます。

期待どおりに動作します：

val myMap = ParticularHashMap("hello" -> 2, "world" -> 4)
println(myMap.get("hello")) >> Some(2)
println(myMap.get("world")) >> Some(4)
println(myMap.get("world1")) >> None

ただし、もちろん、契約を尊重しないと、悪いことが起こることに注意してください。以下は、欠点を示すために特別に作成された例です。

val evilMap = ParticularHashMap(1 -> 2)
println(evilMap.get(1)) >> Some(2)
println(evilMap.get(257)) >> Some(2) //BUT 257 IS NOT IN THE MAP !!!
于 2012-11-19T13:40:50.533 に答える
0

この場合、必要なのは配列だけですよね。

衝突がないことがわかっている場合 (これは、2 つのキーが同じハッシュコードを持たないことを意味します)、ハッシュコードをアドレスとして使用して、配列にインデックスを付けることができます。たとえば、キー オブジェクトのハッシュコードの 1 つが 1003 の場合、対応する値オブジェクトを yourArray[1003] に入れることができます。

「安全でない」取得操作を実行しても問題ない場合、巨大な配列を使用できない場合は、アドレスを key.hashcode() % yourArray.length として計算できます。モジュロ演算のために key1 と key2 が同じスロットにマップされている場合は、スロットを上書きするだけです。

class SimpleMap<K, V> {
    private V [] data;

    public SimpleMap(int size){
        data = (V[])new Object[size];
    }

    public void put (K key, V value){
        data[key.hashCode() % data.length] = value;
    }

    public V get(K key) {
        return data[key.hashCode() % data.length];
    }
}
于 2016-10-26T16:39:37.233 に答える
0

1) この概念はどのように呼ばれますか?

私の知る限り、名前はありません。人々は通常、機能するソリューションにのみ名前を付けます。機能しない (または非常に限られた状況でしか機能しない) ソリューションは、一般的に名前を付ける価値はありません。

2) そのような安全でない get 操作をサポートする、Java または Scala で使用可能なハッシュ マップの実装はありますか?

私が知っているわけではありません。繰り返しになりますが、限られた状況でしか機能しないライブラリや、動作に問題のあるライブラリを作成して公開することはあまりありません。

それのどこに欠陥がありますか？なぜ機能しないのですか？

まず、Map.get(...)認識されないキーを指定した場合に間違った値を返すメソッドは、根本的に JavaMap.get契約を破っています。また、壊れたメソッドが他にもある可能性があります。例: Map.containsKey、Map.put、Map.putAllおよび/またはMap.remove。

第二に、仮定が正しくない場合に間違った答えを与えるデータ構造は悪い考えです...それを避けることができれば。

第三に、あなたの実際のユースケースがわからない場合は、問題を解決するためのより良い方法がほぼ確実にあります。明らかなものは次のとおりです。

  • キークラスを変更equalsしてコストを下げます。
  • を変更できない場合はequals、プロキシ キー クラスを定義して使用するか、
  • Map<Integer, List<Pair<Key,ValueClass>>>キーとして使用される整数が実際のキーのハッシュコードである aを使用します。

(最後のアプローチでは、疑わしい「常にキーが含まれている」という前提が必要ですが、少なくとも Map の抽象化を破っていないため、必要に応じて適切なチェックを行うことができます。)

最後に、「汚い」最適化がアプリケーションに必要であると判断し、それを自分で実装することにしたとしても。私の答えは、次の点については依然として正しい説明であると主張します。

  1. この「ハッキング」に一般的に受け入れられている用語がない理由、および
  2. 3 つの主要な Java コレクション ライブラリ (または私が現在認識しているその他のライブラリ) に既製の実装がない理由

気に入らないかもしれませんが、これ以上の説明はありません。

于 2012-11-19T11:38:33.473 に答える