21

Java で次のようなマップがあるとします。

{ 
 39:"39 to 41",
 41:"41 to 43",
 43:"43 to 45",
 45:">=45"
}

キーがソートされている場合(treemapまたはlinkedhashmapのいずれかを使用)。ここで、>=39および<41の値を取得しようとすると、文字列「39 to 41」を取得する必要があります。これを効率的に行うにはどうすればよいですか? ?

4

6 に答える 6

55

SortedMap;以上が必要なようです。あなたがしたいNavigableMap！具体的には、操作を使用できますfloorKey。

次に例を示します。

    NavigableMap<Integer,String> map =
        new TreeMap<Integer, String>();

    map.put(0, "Kid");
    map.put(11, "Teens");
    map.put(20, "Twenties");
    map.put(30, "Thirties");
    map.put(40, "Forties");
    map.put(50, "Senior");
    map.put(100, "OMG OMG OMG!");

    System.out.println(map.get(map.floorKey(13)));     // Teens
    System.out.println(map.get(map.floorKey(29)));     // Twenties
    System.out.println(map.get(map.floorKey(30)));     // Thirties
    System.out.println(map.floorEntry(42).getValue()); // Forties
    System.out.println(map.get(map.floorKey(666)));    // OMG OMG OMG!

ceilingKey、lowerKey、higherKey、および の代わりに を返す代わりの操作もあること…Entryに注意してください。…KeyMap.Entry<K,V>K

于 2010-08-19T09:12:31.833 に答える
7

Java6を試してくださいjava.util.NavigableMap。http://download.oracle.com/javase/6/docs/api/java/util/NavigableMap.html。

特別な用途でfloorKey/ floorEntry。

例：floorKey(40)を返す必要があり39ます。floorEntryは、探している値を返します。

于 2010-08-19T08:58:10.307 に答える
1

ソートされたマップを使用すると、次のようなことができます。

SortedMap<Integer,String> head = map.headMap(value+1);
if (head.isEmpty()) {
    return null;
} else {
    return head.get(head.lastKey());
}
于 2010-08-19T08:37:57.393 に答える
0

そのようなマップを自分で実装する必要があると思います。並べ替える必要があるのは正しいです。の実装でgetは、引数以下の最大のキーが見つかるまでキーを反復処理する必要があります。

サブクラスTreeMap化すると、最初はメソッドをオーバーライドするだけでこれを機能させることができるように見えますget()。ただし、Map コントラクトをできるだけ多く維持するには、一貫性を保つために他のメソッドをオーバーライドする必要があります。

そして、例えばcontainsKey()どうですか？メインに のマッピングが含まれています40か? が返された場合false、クライアントはget()この情報に基づいて呼び出さないことを決定できます。これらの理由 (および正式な定義) から、 を返す必要がありますtrue。しかし、マップが特定のマッピングを「本当に含んでいる」かどうかを判断するのが難しくなります。既存のものを上書きせずに更新などを行いたい場合。

remove()方法もややこしいかもしれません。インターフェースの私の読書から、

// Calling map.remove "Removes the mapping for a key from this map if it is present."
map.remove(x);

// Now that the mapping is removed, I believe the following must hold
assert map.get(x) == null;
assert map.containsKey(x);

ここで一貫して行動するのは非常に難しいでしょう。たとえば、35-40 からのマッピングがあり、 を呼び出すremove(38)場合、私が理解しているようnullに、キー 38 の後続の取得のために戻る必要がありますが、キー 35-37 または 39-40 の前述のマッピングを返します。 .

したがって、TreeMap をオーバーライドすることでこれを開始することはできますが、おそらく の全体的な概念は、Mapここで求めているものとはまったく異なります。を受け取る既存のメソッドにこの動作を挿入する必要がない限りMap、それを独自のクラスとして作成する方が簡単かもしれません。これは、定義している方法では完全に Map ではないためです。

于 2010-08-19T08:39:19.530 に答える
0

それが簡単になるかどうかはわかりません。1 つの提案は、「ギャップを埋める」、つまり値40->"39 to 41"などを入れることです。これは、マップで可能な数値の範囲全体を知っている場合にのみ可能になると思います。

getまたは、値がマップにあるかどうかを確認するためにオーバーライドし、何かが見つかるまで展開するものかもしれません。値の文字列を解析する必要があるため、現在の形でそれが可能になるかどうかはわかりません。

于 2010-08-19T08:27:28.460 に答える
0

再帰的に下限を探すことができます。

public String descriptionFor(int value) {
    String description = map.get(value);
    return description == null ? descriptionFor(value--) : description;
}

最低限の境界が必要です。

于 2010-08-19T08:34:46.057 に答える