4

何HashMap百万ものエントリがあります。

キーが特定の一連の基準に一致するすべてのエントリを取得する必要があります (この場合、各キーは 2 つの整数プロパティを持つオブジェクトです。これらの整数のそれぞれが指定された範囲内にあるすべてのキーを取得する必要があります)。

そのようなすべてのキーを反復処理する最も高速で効率的な方法は何ですか?

更新: この特定のケースでは、事前に指定しませんでしたが、キーの最初の整数が 2 番目の整数より自然に優先されます。

4

7 に答える 7

7

HashMap は、特定の範囲内にあるキーを見つけるための効率的なデータ構造ではありません。一般に、ハッシュ マップで効率的に見つけることができる唯一のキーは、持っているものと同じハッシュを持つキー (つまり、等しいキー) です。

特定の範囲内にあるキーを見つけるには、SortedMap.subMap(low, high) ビュー メソッドで表示できる TreeMap などの種類のSortedMapを使用することをお勧めします。

2 つのキーに基づいてキーを見つけることに関しては、さらに困難です。あなたの最善の策は、最初の整数の範囲の subMap を反復処理し、2 番目の整数が指定された範囲内にあるかどうかをそれぞれチェックすることです。これにより、少なくとも範囲内の整数の 1 つを持つキーにスキャンが制限されます。検索しなければならない可能性のある範囲にわたって、より自然な値の分布を持つ整数に基づいてマップをソートしてみてください。

于 2009-02-11T17:50:33.847 に答える
3

TreeMapを使用したソリューションは次のとおりです。

public static void main(String[] args) {
    Comparator<Foo> fooComparator = new Comparator<Foo>() {
        @Override
        public int compare(Foo o1, Foo o2) {
            return o1.compareTo(o2);
        }
    };

    TreeMap<Foo, String> map = new TreeMap<Foo, String>(fooComparator);

    map.put(new Foo(1, 4), "");
    map.put(new Foo(1, 3), "");
    map.put(new Foo(2, 4), "");
    map.put(new Foo(3, 4), "");
    map.put(new Foo(8, 10), "");
    map.put(new Foo(8, 17), "");
    map.put(new Foo(10, 10), "");

    int a = 2;
    int b = 5;

    for (Foo f : getKeysInRange(map, a, b)) {
        System.out.println(f);
    }
}

public static List<Foo> getKeysInRange(TreeMap<Foo, String> map, int low, int high) {
    Foo key1 = new Foo(low, low);
    Foo key2 = new Foo(high, high);

    Foo fromKey = map.ceilingKey(key1);
    Foo toKey = map.floorKey(key2);

    if (fromKey != null && toKey != null && fromKey.compareTo(toKey) < 0)
        return new ArrayList<Foo>(map.subMap(fromKey, true, toKey, true).keySet());
    return new ArrayList<Foo>();
}

public static class Foo implements Comparable<Foo> {
    private int i;
    private int j;

    private Foo(int i, int j) {
        super();
        this.i = i;
        this.j = j;
    }

    public int min() {
        if (i < j)
            return i;
        else
            return j;
    }

    public int max() {
        if (i > j)
            return i;
        else
            return j;
    }

    @Override
    public String toString() {
        return "I=" + i + "J=" + j;
    }

    @Override
    public int compareTo(Foo o) {
        if (this.min() > o.min()) {
            return 1;
        } else if (this.min() < o.min())
            return -1;
        else {
            if (this.max() > o.max())
                return 1;
            else if (this.max() < o.max())
                return -1;
            else
                return 0;
        }
    }
}
于 2009-02-11T18:49:13.067 に答える
1

keySet 全体を反復処理しないと実行できません。

これらの整数プロパティの同じ値を持つエントリが他にないことが確実な場合は、2 つの整数プロパティの組み合わせで並べ替える並べ替え条件で TreeMap を使用できます。その後、最初のエントリを見つけることができます。直接一致し、そこから最初の不一致まで反復します。しかし、これらの条件を達成できる可能性は低いようです。

コレクションのオーバーヘッドは非常に低いため (すべてが参照によって格納される)、2 つの並べ替えられたコレクション (おそらく TreeSets) を作成することを検討します。両方のコレクションを結合し、それらを結合します。

于 2009-02-11T17:50:30.010 に答える
1

bruno conde が提供するソリューションは良いスタートです。ただし、元の質問を読んだ方法は、キーオブジェクトに2つの整数が含まれており、最初の整数の1つの範囲に一致し、2番目の範囲の2番目の範囲に一致するすべてのキーと値のペアを取得する最速の方法に関する質問でした.整数。ブルーノの解決策は、キーには最初の整数が常に 2 番目の整数よりも優先される自然な順序があると想定しています。また、範囲が 1 つしかないことも前提としています。

このより一般的なケースでは、次のようにします。 integer1 を優先するコンパレーターを使用して TreeMap にキー/値を挿入します。

次に、範囲を使用して各 TreeMap で subMap() を使用し、基になる TreeMap の順序付きビューを取得できます。次に、これらのサブマップの keySet() の共通部分 (retainAll()) に基づいて、新しい結果 TreeSet を作成できます。

于 2009-02-11T20:24:32.210 に答える
0

次のようなものよりも速い解決策はおそらくないでしょう:

for (final KeyObj key : map.keySet()) {
    // do work
}
于 2009-02-11T17:49:35.363 に答える
0

TreeSet何らかの理由でaが機能しない場合、反復する標準的な方法は、エントリ セットを使用することです。

for (Map.Entry<MyKeyType, MyValueType> entry : myMap.entrySet()) {
    MyKeyType key = entry.getKey();
    if (isValid(key)) {
        // do whatever
        validList.add(entry.getValue());
    }
}

myMap.get(key)この方法では、有効なキーに対して余分な呼び出しを行う必要はありません。

于 2009-02-11T17:49:55.190 に答える