28

私は大きなを使って作業しているArrayList<HashMap<A,B>>ので、ランダムなHashMapからランダムなキーを繰り返し選択する必要があります（そしてそれを使って何かをする必要があります）。ランダムなHashMapを選択するのは簡単ですが、このHashMap内からランダムなキーを選択するにはどうすればよいですか？

速度は重要です（これを10000回実行する必要があり、ハッシュマップが大きいため）。したがって、[0,9999]で乱数kを選択.next()し、イテレーターをk回実行するだけでは、実際にはオプションではありません。同様に、ランダムピックごとにHashMapを配列またはArrayListに変換することは実際にはオプションではありません。返信する前にこれを読んでください。

技術的には、HashMapはキーをEntry[]内部に格納し、配列からランダムに選択するのは簡単なので、これは可能であると思いますが、これにアクセスする方法がわかりませんEntry[]。したがって、内部にアクセスするためのアイデアEntry[]は大歓迎です。もちろん、他のソリューション（ハッシュマップサイズで線形時間を消費しない限り）も歓迎します。

注：ヒューリスティックは問題ないので、要素の1％を除外する方法がある場合（たとえば、複数のバケットがいっぱいになっているため）、まったく問題ありません。

4

10 に答える 10

28

頭のてっぺんから

List<A> keysAsArray = new ArrayList<A>(map.keySet())
Random r = new Random()

その後、ちょうど

map.get(keysAsArray.get(r.nextInt(keysAsArray.size()))
于 2012-09-12T09:44:39.217 に答える
14

パフォーマンスを低下させることなく解決策を見つけることができました。他の人に役立つ可能性があるため、ここに投稿します。このトピックに関するいくつかの未解決の質問に回答する可能性があります（これらは後で検索します）。

必要なのはSet、キーを格納するための2番目のカスタムのようなデータ構造です。ここで提案されているようなリストではありません。リストのようなデータ構造は、アイテムを削除するのにコストがかかります。必要な操作は、一定時間内に要素を追加/削除し（HashMapで最新の状態に保つため）、ランダムな要素を選択する手順です。次のクラスMySetはまさにこれを行います

class MySet<A> {
     ArrayList<A> contents = new ArrayList();
     HashMap<A,Integer> indices = new HashMap<A,Integer>();
     Random R = new Random();

     //selects random element in constant time
     A randomKey() {
         return contents.get(R.nextInt(contents.size()));
     }

     //adds new element in constant time
     void add(A a) {
         indices.put(a,contents.size());
         contents.add(a);
     }

     //removes element in constant time
     void remove(A a) {
        int index = indices.get(a);
        contents.set(index,contents.get(contents.size()-1));
        indices.put(contents.get(index),index);
        contents.remove((int)(contents.size()-1));
        indices.remove(a);
     }
}
于 2012-09-12T10:58:26.107 に答える
7

基になるエントリテーブルにアクセスする必要があります。

// defined staticly
Field table = HashMap.class.getDeclaredField("table");
table.setAccessible(true);
Random rand = new Random();

public Entry randomEntry(HashMap map) {
    Entry[] entries = (Entry[]) table.get(map);
    int start = rand.nextInt(entries.length);
    for(int i=0;i<entries.length;i++) {
       int idx = (start + i) % entries.length;
       Entry entry = entries[idx];
       if (entry != null) return entry;
    }
    return null;
}

これでもエントリをトラバースしてそこにあるエントリを見つける必要があるため、最悪の場合はO（n）ですが、一般的な動作はO（1）です。

于 2012-09-12T10:36:25.343 に答える
4

リストに保存するには、補助的なキーのリストか、マップではなく実際のオブジェクトのいずれかを検討する必要があるようです。

于 2012-09-12T09:42:02.927 に答える
2

@Alberto Di Gioacchinoが指摘したように、削除操作で受け入れられたソリューションにバグがあります。これが私がそれを修正した方法です。

class MySet<A> {
     ArrayList<A> contents = new ArrayList();
     HashMap<A,Integer> indices = new HashMap<A,Integer>();
     Random R = new Random();

     //selects random element in constant time
     A randomKey() {
         return contents.get(R.nextInt(contents.size()));
     }

     //adds new element in constant time
     void add(A item) {
         indices.put(item,contents.size());
         contents.add(item);
     }

     //removes element in constant time
     void remove(A item) {
        int index = indices.get(item);
        contents.set(index,contents.get(contents.size()-1));
        indices.put(contents.get(index),index);
        contents.remove(contents.size()-1);
        indices.remove(item);
     }
}
于 2021-04-29T03:25:59.883 に答える
1

HashMap後日調べなければならないので使っていると思いますか？

そうでない場合はHashMap、Array/に変更してくださいArrayList。

このような場合は、オブジェクトをMapANDに格納して、ArrayListランダムにまたはキーで検索できるようにしてください。

TreeMapまたは、代わりに使用できますHashMapか？キーの種類はわかりませんが、TreeMap.floorKey()キーランダマイザーと組み合わせて使用​​します。

于 2012-09-12T09:58:42.610 に答える
1

しばらく時間をかけて、キーを維持するためにaList<Map<A, B>>とaでバックアップできるモデルを作成する必要があるという結論に達しました。とList<A>のアクセスを維持する必要があります。呼び出し元に操作/メソッドを提供するだけです。このようにして、実装を完全に制御でき、実際のオブジェクトは外部の変更からより安全になります。List<Map<A, B>>List<A>

ところで、あなたの質問は私を導きます、

この例、IndexedSetは、ハウツーについてのアイデアを与えるかもしれません。

[編集]

このクラスSetUniqueListは、独自のモデルを作成する場合に役立つ可能性があります。listコピーではなく、をラップすることを明示的に示しています。だから、私たちは次のようなことができると思います、

List<A> list = new ArrayList(map.keySet());
SetUniqueList unikList = new SetUniqueList(list, map.keySet);
// Now unikList should reflect all the changes to the map keys
...
// Then you can do
unikList.get(i);

注： 私はこれを自分で試していません。後でそれを行います（家に急いで）。

于 2012-09-12T10:21:40.797 に答える
1

Java 8以降、O（log（N））追加メモリを使用したO（log（N））アプローチがあります。viaを作成しSpliterator、map.entrySet().spliterator()log（map.size（））trySplit()呼び出しを行い、前半または後半をランダムに選択します。 。に残っている要素が10未満の場合はSpliterator、それらをリストにダンプしてランダムに選択します。

于 2019-02-26T20:15:21.167 に答える
0

どうしてもHashMapのEntry配列にアクセスする必要がある場合は、リフレクションを使用できます。ただし、プログラムはHashMapの具体的な実装に依存します。

提案されているように、マップごとに個別のキーのリストを保持できます。キーの深いコピーを保持しないので、実際のメモリの非正規化はそれほど大きくありません。

3番目のアプローチは、独自のMap実装を実装することです。これは、キーをセットではなくリストに保持するものです。

于 2012-09-12T10:40:01.773 に答える
0

Mapの別の実装でHashMapをラップするのはどうですか？もう1つのマップはリストを維持し、put（）では次のことを行います。

if (inner.put(key, value) == null) listOfKeys.add(key);

（containsKeyを使用している場合、値のnullは許可されないと思いますが、それは遅くなります）

于 2012-09-12T19:54:50.163 に答える