Estruturas de dados que podem mapear um intervalo de chaves para um valor

Eu estou tentando encontrar uma estrutura de dados que leva em um determinado valor de um intervalo de valores e mapeá-lo para uma chave.

Por exemplo, tenho as seguintes condições:

  1. De 1 a 2.9, quero mapeá-lo para A.
  2. De 4 a 6, quero mapeá-lo para B.
  3. De 6,5 a 10, quero mapeá-lo para C.

Eu tenho um valor de 5 e gostaria de mapeá-lo para uma chave. Então, com base nas condições acima, eu deveria mapeá-lo para B.

Existe alguma estrutura de dados em Java que alguém possa me recomendar para resolver o problema?

Atualmente, estou usando uma hashtable que pode mapear apenas um valor para uma chave. Eu tentei mapear o intervalo de valores para um valor específico que existe no hashtable. No entanto, fiquei preso no mapeamento do intervalo de valores para um valor específico. Então, agora estou tentando fazer outra maneira de mapear os intervalos de valores para uma chave. Alguém tem alguma ideia de como posso resolver este problema?

EDITAR:

Graças a Martin Ellis, decidi usar o TreeMap para resolver o problema.

Suas faixas não se sobrepõem? Se assim você poderia usar um TreeMap:

TreeMap m = new TreeMap(); 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); 

A lógica de pesquisa é um pouco complicada pelo fato de que você provavelmente deseja uma consulta abrangente (ou seja, 2.9 mapeia para ‘A’ e não é indefinida):

 private static  V mappedValue(TreeMap map, K key) { Entry e = map.floorEntry(key); if (e != null && e.getValue() == null) { e = map.lowerEntry(key); } return e == null ? null : e.getValue(); } 

Exemplo:

 mappedValue(m, 5) == 'B' 

Mais resultados incluem:

 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 

Isso parece uma situação natural para usar uma estrutura de tree.

Infelizmente, não será prático implementar a interface java.util.Map porque ela especifica um método para retornar todas as chaves e, em sua situação, teoricamente, você tem um número de chaves impraticável.

Cada nó da sua tree deve ter uma chave mínima, uma chave máxima e um valor associado a esse intervalo. Você pode então ter links para os nós que representam o próximo intervalo superior e o próximo menor (se existirem). Algo como:

 public class RangeMap, V> { protected boolean empty; protected K lower, upper; protected V value; protected RangeMap 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(); right = new RangeMap(); 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; } } 

Se você precisa de pesquisas mais rápidas do que a tree pode fornecer, você pode querer olhar para algo como uma lista de pulos ou desenvolver sua própria function de hash.

Um HashMap não funcionará para mapear intervalos para valores, a menos que você encontre uma maneira de gerar um hashcode para intervalos e valores únicos correspondentes. Mas a abordagem abaixo pode ser o que você está procurando

 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 entries = new ArrayList(); 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; } } 

Você poderia fazer

 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 

Não é muito eficiente, pois é apenas iterar sobre uma lista e, nesse estado, não reclamará se você colocar intervalos conflitantes lá. Apenas retornará o primeiro que encontrar.

PS: mapeamento como este seria mapear um intervalo de chaves para um valor

Esse tipo de estrutura de dados é chamado de Árvore de Intervalo . (A página da Wikipédia apresenta apenas o caso em que os intervalos podem se sobrepor, mas pode-se imaginar um caso em que você deseja remover mapeamentos para intervalos sobrepostos ao adicionar um novo intervalo. Pesquise no Google por implementações e veja se elas atendem às suas necessidades.

Guava RangeMap fornece solução especializada fora da checkbox:

 RangeMap 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" 

Basta ter uma lista como um valor no seu mapa.

 Map> map = new HashMap>(); 

e também um Suggustion :

não use o Hashtable, a menos que você queira access sincronizado.

EDITAR:

Os methods de tabela de hash são sincronizados, ou seja, não há dois segmentos podem acessar esses methods em um único ponto do tempo. Os mentodos do HashMap não são sincronizados. Se você usar o Hashtable, haverá um impacto no desempenho. use o HashMap para um melhor desempenho.

Uma das maneiras seria usar uma implementação de lista como valor para key.

 map.put("A", ArrayList);