値の範囲から特定の値を取り込んで、それをキーにマップするデータ構造を見つけようとしています。
たとえば、次の条件があります。
値は5で、キーにマップしたいと思います。したがって、上記の条件に基づいて、Bにマップする必要があります。
問題を解決するために誰かが私に勧めることができるJavaのデータ構造はありますか？
現在、値をキーにのみマップできるハッシュテーブルを使用しています。値の範囲をハッシュテーブルに存在する特定の値にマップしようとしました。しかし、値の範囲を特定の値にマッピングするのに行き詰まりました。だから今、私は値の範囲をキーにマッピングする別の方法をしようとしています。誰かが私がこの問題を解決する方法を知っていますか？
編集：
Martin Ellisのおかげで、TreeMapを使用して問題を解決することにしました。
範囲が重複していませんか? その場合、TreeMap を使用できます。
TreeMap<Double, Character> m = new TreeMap<Double, Character>();
m.put(1.0, 'A');
m.put(2.9, null);
m.put(4.0, 'B');
m.put(6.0, null);
m.put(6.5, 'C');
m.put(10.0, null);
検索ロジックは、おそらく包括的な検索が必要なため、少し複雑です (つまり、2.9 は 'A' にマップされ、未定義ではありません)。
private static <K, V> V mappedValue(TreeMap<K, V> map, K key) {
Entry<K, V> e = map.floorEntry(key);
if (e != null && e.getValue() == null) {
e = map.lowerEntry(key);
}
return e == null ? null : e.getValue();
}
例：
mappedValue(m, 5) == 'B'
その他の結果は次のとおりです。
0.9 null
1.0 A
1.1 A
2.8 A
2.9 A
3.0 null
6.4 null
6.5 C
6.6 C
9.9 C
10.0 C
10.1 null
これは、ツリー構造を使用する自然な状況のようです。
残念ながら、java.util.Mapすべてのキーを返すメソッドが指定されているため、インターフェイスを実装することは実用的ではありません。あなたの状況では、理論的には非現実的な数のキーがあります。
ツリーの各ノードには、最小キー、最大キー、およびその範囲に関連付けられた値が必要です。次に、次に高い範囲と次に低い範囲を表すノードへのリンクを作成できます (存在する場合)。何かのようなもの：
public class RangeMap<K extends Comparable<K>, V> {
protected boolean empty;
protected K lower, upper;
protected V value;
protected RangeMap<K, V> left, right;
public V get(K key) {
if (empty) {
return null;
}
if (key.compareTo(lower) < 0) {
return left.get(key);
}
if (key.compareTo(upper) > 0) {
return right.get(key);
}
/* if we get here it is in the range */
return value;
}
public void put(K from, K to, V val) {
if (empty) {
lower = from;
upper = to;
value = val;
empty = false;
left = new RangeMap<K,V>();
right = new RangeMap<K,V>();
return;
}
if (from.compareTo(lower) < 0) {
left.put(from, to, val);
return;
}
if (to.compareTo(upper) > 0) {
right.put(from, to, val);
return;
}
/* here you'd have to put the code to deal with adding an overlapping range,
however you want to handle that. */
}
public RangeMap() {
empty = true;
}
}
ツリーが提供できるよりも高速なルックアップが必要な場合は、スキップ リストのようなものを調べるか、独自のハッシュ関数を開発することをお勧めします。
範囲と一致する単一の値のハッシュコードを生成するHashMap方法が見つからない限り、範囲を値にマッピングするためには機能しません。しかし、以下のアプローチはあなたが探しているものかもしれません
public class RangeMap {
static class RangeEntry {
private final double lower;
private final double upper;
private final Object value;
public RangeEntry(double lower, double upper, Object mappedValue) {
this.lower = lower;
this.upper = upper;
this.value = mappedValue;
}
public boolean matches(double value) {
return value >= lower && value <= upper;
}
public Object getValue() { return value; }
}
private final List<RangeEntry> entries = new ArrayList<RangeEntry>();
public void put(double lower, double upper, Object mappedValue) {
entries.add(new RangeEntry(lower, upper, mappedValue));
}
public Object getValueFor(double key) {
for (RangeEntry entry : entries) {
if (entry.matches(key))
return entry.getValue();
}
return null;
}
}
あなたができる
RangeMap map = new RangeMap();
map.put(1, 2.9, "A");
map.put(4, 6, "B");
map.getValueFor(1.5); // = "A"
map.getValueFor(3.5); // = null
リストを反復するだけなので、あまり効率的ではありません。競合する範囲をそこに入れても、その状態では文句を言いません。最初に見つかったものを返します。
PS: このようなマッピングは、キーの範囲を値にマッピングします
マップの値としてリストを持っているだけです。
Map<String, List<Double>> map = new HashMap<String, List<Double>>();
また、1つの提案：
同期アクセスが必要でない限り、Hashtable を使用しないでください。
編集：
ハッシュテーブル メソッドは同期されます。つまり、2 つのスレッドが同時にこれらのメソッドにアクセスすることはできません。HashMap メソッドは同期されていません。Hashtable を使用すると、パフォーマンスが低下します。パフォーマンスを向上させるには HashMap を使用してください。
方法の1つは、リスト実装の1つをキーの値として使用することです。
map.put("A", ArrayList<Integer>);