Estructura de datos de Java para asignar varias claves al mismo valor

Question

En Java estoy buscando una forma de asignar varias claves al mismo valor. Vamos a decir que tengo los números 0-9 como teclas, y "x", "y" y "z" como valores de la siguiente manera:

0->y 
1->y 
2->y 
3->x 
4->x 
5->y 
6->z 
7->y 
8->z 
9->z 

ahora x, y, z son cadenas muy largas, y tengo millones de claves, así que no puedo permitirme almacenar las cadenas varias veces. ¿Cómo lo harías?

Una idea que tuve fue crear dos matrices: se generó una segunda clave artificial para la cual se mapearon las claves originales y que en otra matriz es la clave de los valores reales. De esta manera los valores sólo se almacenan de una vez las llaves originales todavía se pueden asignar indirectamente a los valores:

0->k1 
1->k1 
2->k1 
3->k2 
4->k2 
5->k1 
6->k3 
7->k1 
8->k3 
9->k3 

k1->y 
k2->x 
k3->z 

pregunta, sin embargo: ¿Hay una mejor estructura de datos para esto?

Answer 1

Cualquier Map<Integer,String> va a hacer - sólo si va a guardar una referencia a la cadena y no una copia de la misma, por lo que no importa cuánto tiempo es.

Si está construyendo el mismo valor de cadena varias veces, use intern() para obtener el mismo objeto String para el valor cada vez.

Answer 2

Realmente no entiendo la pregunta. Si tiene una matriz de Cadenas: String[] arr, simplemente configure diferentes índices para el mismo objeto, también haga las referencias iguales.

String[] map = new String[10]; 
String x = "foo"; 
String y = "bar"; 
String z = "baz"; 
map[0] = x; 
map[1] = y; 
map[2] = x; 
//... 

Answer 3

¿Por qué no invertir el par de clave/valor? Utilizar un conjunto o matriz de los valores:

x->{3, 4} 
y->{0, 1, 2, 5, 7} 
z->{6, 8, 9} 

Answer 4

Java consolidará automáticamente referencias de Cuerda para usted, por lo que no es necesario hacerlo de forma manual con el fin de ahorrar memoria. Puedes simplemente poner las llaves/valores en un HashMap.

Answer 5

Si no te gusta la sugerencia de Pete Kirkham (que sería la mejor manera, IMO), podrías utilizar Google Collections (er ... Guava ahora) MultiMap.

Answer 6

Cada entrada de mapa utilizará varios cientos de bits para representar un valor que teóricamente podría ser mantenido en 2.

Si las teclas son más densos que algún número del orden de 1 cada cientos de números enteros, será más rápido y más pequeño para no usar un mapa, pero una matriz, algo así como Trove TByteArrayList, donde los valores de bytes se asignan a sus cadenas. Si desea obtener 4 veces más densidad, empaquete 4 valores en un solo byte.

Esto solo tiene sentido para molestar cuando tienes una gran cantidad de datos, pero dijiste millones de claves, así que creo que es una buena opción.