java 可以将一系列键映射到值的数据结构

Data structures that can map a range of keys to a value

提问by Sakura

I am trying to find a data structure that takes in a particular value from a range of values and map it to a key.

我试图找到一种数据结构，它从一系列值中获取特定值并将其映射到一个键。

For example, I have the following conditions:

例如，我有以下条件：

1. From 1 to 2.9, I want to map it to A.
2. From 4 to 6, I want to map it to B.
3. From 6.5 to 10, I want to map it to C.

1. 从1到2.9，我想把它映射到A。
2. 从4到6，我想把它映射到B。
3. 从6.5到10，我想把它映射到C。

I have a value of 5 and I would like to map it to a key. So based on the above conditions, I should map it to B.

我的值为 5，我想将它映射到一个键。所以根据上面的条件，我应该把它映射到B。

Is there any data structure in Java that anyone can recommend to me to solve the problem?

任何人都可以向我推荐 Java 中的任何数据结构来解决问题？

Currently I am using a hashtable that can only map a value to a key. I tried to map the range of values to a particular value that exists in the hashtable. However, I got stuck in the mapping of the range of values to a particular value. So now I am trying to do another way of mapping the ranges of values to a key. Does anyone have any idea how I can solve this problem?

目前我正在使用一个只能将值映射到键的哈希表。我试图将值的范围映射到哈希表中存在的特定值。但是，我陷入了将值范围映射到特定值的问题。所以现在我正在尝试做另一种将值的范围映射到键的方法。有谁知道我如何解决这个问题？

EDIT:

编辑：

Thanks to Martin Ellis, I decided to use TreeMap to solve the problem.

感谢 Martin Ellis，我决定使用 TreeMap 来解决这个问题。

回答by Martin Ellis

Are your ranges non-overlapping? If so you could use a 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);

The lookup logic is a bit complicated by the fact that you probably want an inclusive lookup (i.e. 2.9 maps to 'A', and not undefined):

查找逻辑有点复杂，因为您可能需要包含查找（即 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();
}

Example:

例子：

mappedValue(m, 5) == 'B'

More results include:

更多结果包括：

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

回答by Samuel Edwin Ward

This seems like a natural situation to use a tree structure.

这似乎是使用树结构的自然情况。

Unfortunately it won't be practical to implement the java.util.Mapinterface because it specifies a method to return all of the keys, and in your situation you theoretically have an impractically large number of keys.

不幸的是，实现该java.util.Map接口是不切实际的，因为它指定了一种返回所有键的方法，而在您的情况下，理论上您拥有大量不切实际的键。

Each node of your tree should have a minimum key, a maximum key, and a value associated with that range. You can then have links to the nodes representing the next higher and next lower range (if they exist). Something like:

树的每个节点都应该有一个最小键、一个最大键和一个与该范围相关的值。然后，您可以链接到代表下一个更高和下一个更低范围的节点（如果它们存在）。就像是：

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;
    }
}

If you need faster lookups than the tree can provide, you may want to look into something like a skip list or developing your own hash function.

如果您需要比树提供的更快的查找速度，您可能需要查看诸如跳过列表之类的内容或开发您自己的哈希函数。

回答by Andy

This type of data structure is called an Interval Tree. (The Wikipedia page only presents the case where intervals may overlap, but one can imagine a case where you want to remove mappings for any overlapped intervals when you add a new interval. Do a Google search for implementations and see if any fit your needs.

这种类型的数据结构称为区间树。（维基百科页面只介绍了间隔可能重叠的情况，但可以想象一种情况，当您添加新间隔时，您想删除任何重叠间隔的映射。请在 Google 上搜索实现，看看是否有任何适合您的需要。

回答by Vadzim

Guava RangeMapprovidesspecialized solution out of the box:

Guava RangeMap提供开箱即用的专业解决方案：

RangeMap<Integer, String> rangeMap = TreeRangeMap.create();
rangeMap.put(Range.closed(1, 100), "foo"); // {[1, 100] => "foo"}
rangeMap.put(Range.open(3, 6), "bar"); // {[1, 3] => "foo", (3, 6) => "bar", [6, 100] => "foo"}

rangeMap.get(42); // returns "foo"

回答by zapl

A HashMapwill not work for mapping ranges to values unless you find a way to generate a hashcode for ranges and single values in there that matches. But below approach could be what you are looking for

HashMap除非您找到一种方法来为匹配的范围和单个值生成哈希码，否则A将不适用于将范围映射到值。但下面的方法可能是你正在寻找的

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;
    }
}

You could do

你可以做

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

It's not very efficient since it's just iterating over a list and it will in that state not complain if you put conflicting ranges in there. Will just return the first it finds.

它不是很有效，因为它只是迭代一个列表，如果你在那里放置冲突的范围，它不会在那种状态下抱怨。只会返回它找到的第一个。

P.S.: mapping like this would be mapping a range of keysto a value

PS：这样的映射会将一系列键映射到一个值

回答by PermGenError

just have an List as a value in your Map.

只需在您的地图中有一个列表作为值。

Map<String, List<Double>> map = new HashMap<String, List<Double>>();

and also one Suggustion:

还有一个建议：

do not use Hashtable unless you want synchronized access.

除非您想要同步访问，否则不要使用 Hashtable。

EDIT:

编辑：

Hashtable methods are synchronized, i.e., no two threads can access those methods at a single point of time. HashMap menthods are not Synchronized. If you use Hashtable there will be a performance hit. use HashMap for better performance.

哈希表方法是同步的，即没有两个线程可以在一个时间点访问这些方法。HashMap 方法未同步。如果您使用 Hashtable，则会影响性能。使用 HashMap 以获得更好的性能。

回答by kosa

One of the way would be, use one of list implementation as value for key.

一种方法是，使用列表实现之一作为键的值。

map.put("A", ArrayList<Integer>);