Java datastructure to map multiple keys to the same value

Question

In Java I'm looking for a way to map multiple keys to the same value. Let's say I have the numbers 0-9 as keys, and "x", "y" and "z" as values as follows:

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

now x,y and z are really long strings, and I have millions of keys so I can't afford to store the strings multiple times. How would you go about it?

One idea I had was to create two arrays: an artificial second to key is generated to which the original keys are mapped and which in another array is the key to the actual values. That way the values are only stored once and the original keys can still be indirectly mapped to the values:

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

Question though: Is there a better data structure for this?

Answer 1

I don't really understand the question. If you have an array of Strings: String[] arr then just set different indices to the same object - aka make the references the same.

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

Answer 2

Any Map<Integer,String> will do - you are only storing a reference to the string, not a copy of it, so it doesn't matter how long it is.

If you are building the same string value multiple times, use intern() to get the same String object for the value each time.

Answer 3

Why not invert the key/value pairing? Use a Set or array for the values:

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

Answer 4

Java will automatically consolidate String references for you, so you don't need to do it manually in order to save memory. You can just put the keys / values in a HashMap.

Answer 5

If you don't like Pete Kirkham's suggestion (which would be the best way, IMO), you could use a Google Collections (er... Guava now) MultiMap.