java - lineales - Estructuras de datos que pueden asignar un rango de claves a un valor

importancia de la estructura de datos

Question

Estoy tratando de encontrar una estructura de datos que tome un valor particular de un rango de valores y lo asigne a una clave.

Por ejemplo, tengo las siguientes condiciones:

1. Del 1 al 2.9, quiero mapearlo a A.
2. De 4 a 6, quiero mapearlo a B.
3. De 6.5 a 10, quiero mapearlo a C.

Tengo un valor de 5 y me gustaría asignarlo a una clave. Entonces, basado en las condiciones anteriores, debería mapearlo a B.

¿Hay alguna estructura de datos en Java que alguien pueda recomendarme para resolver el problema?

Actualmente estoy usando una tabla hash que solo puede asignar un valor a una clave. Intenté asignar el rango de valores a un valor particular que existe en la tabla hash. Sin embargo, me quedé atascado en el mapeo del rango de valores a un valor particular. Así que ahora estoy tratando de hacer otra forma de asignar los rangos de valores a una clave. ¿Alguien tiene alguna idea de cómo puedo resolver este problema?

EDITAR:

Gracias a Martin Ellis, decidí usar TreeMap para resolver el problema.

Answer 1

¿Sus rangos no se superponen? Si es así podrías usar un 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);

La lógica de búsqueda es un poco complicada por el hecho de que probablemente desee una búsqueda inclusiva (es decir, 2.9 mapas a ''A'', y no indefinido):

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

Ejemplo:

mappedValue(m, 5) == ''B''

Más resultados incluyen:

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

Answer 2

Este tipo de estructura de datos se denomina árbol de intervalos . (La página de Wikipedia solo presenta el caso en que los intervalos pueden superponerse, pero uno puede imaginar un caso en el que desee eliminar asignaciones para cualquier intervalo superpuesto cuando agregue un nuevo intervalo. Haga una búsqueda en Google para las implementaciones y vea si alguna se ajusta a sus necesidades.

Answer 3

Esto parece una situación natural para usar una estructura de árbol.

Desafortunadamente, no será práctico implementar la interfaz java.util.Map porque especifica un método para devolver todas las claves, y en su situación teóricamente tienes un número de claves poco práctico.

Cada nodo de su árbol debe tener una clave mínima, una clave máxima y un valor asociado con ese rango. Luego puede tener enlaces a los nodos que representan el siguiente rango superior e inferior (si existen). Algo como:

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

Si necesita búsquedas más rápidas de las que puede proporcionar el árbol, puede buscar algo así como una lista de salto o desarrollar su propia función hash.

Answer 4

Guava RangeMap provides una solución especializada lista para 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"

Answer 5

Un HashMap no funcionará para asignar rangos a valores a menos que encuentre una manera de generar un código hash para rangos y valores únicos que coincidan. Pero a continuación el enfoque podría ser lo que buscas

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

Podrías hacerlo

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

No es muy eficiente, ya que solo está iterando sobre una lista y en ese estado no se quejará si coloca rangos en conflicto allí. Solo devolveré lo primero que encuentre.

PD: la asignación de este tipo sería la asignación de un rango de claves a un valor

Answer 6

Una de las formas sería usar una implementación de lista como valor para la clave.

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

Answer 7

acaba de tener una lista como un valor en su mapa.

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

y también una Suggustion :

No utilice Hashtable a menos que desee un acceso sincronizado.

EDITAR:

Los métodos hash se sincronizan, es decir, no hay dos hilos que puedan acceder a esos métodos en un solo punto de tiempo. Los métodos de HashMap no están sincronizados. Si usas Hashtable habrá un impacto de rendimiento. Usa HashMap para un mejor rendimiento.