Структура данных Java для сопоставления нескольких ключей одному значению

Question

В Java я ищу способ сопоставить несколько ключей одному значению. Допустим, у меня есть цифры 0-9 в качестве ключей, а "x", "y" и "z" в качестве значений следующим образом:

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

теперь x, y и z - действительно длинные строки, и у меня есть миллионы ключей, поэтому я не могу позволить себе хранить строки несколько раз. Как бы вы пошли об этом?

Одна из идей, которые у меня были, заключалась в создании двух массивов: создается искусственный второй ключ, которому сопоставляются исходные ключи и который в другом массиве является ключом к фактическим значениям. Таким образом, значения сохраняются только один раз, и оригинальные ключи могут быть косвенно сопоставлены со значениями:

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

Вопрос, хотя: есть ли лучшая структура данных для этого?

Answer 1

Любой Map<Integer,String> подойдет - вы храните только ссылку на строку, а не ее копию, поэтому не имеет значения, как долго это будет.

Если вы строите одно и то же строковое значение несколько раз, используйте intern(), чтобы каждый раз получать один и тот же объект String для значения.

Answer 2

Почему бы не инвертировать пару ключ / значение? Используйте набор или массив для значений:

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

Answer 3

Если вам не нравится предложение Пита Киркхэма (что будет лучшим способом, ИМО), вы можете использовать Коллекции Google (э-э ... Гуава сейчас) MultiMap.

Answer 4

Я не очень понимаю вопрос. Если у вас есть массив строк: String[] arr, тогда просто установите разные индексы для одного и того же объекта - иначе сделайте ссылки одинаковыми.

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

Answer 5

Каждая запись карты будет использовать несколько сотен битов для представления значения, которое теоретически может быть сохранено в 2.

Если ключи более плотные, чем некоторое число порядка 1 на каждые несколько сотен целых чисел, это будет быстрее и меньше, если вообще не использовать карту, но массив - что-то вроде Trove TByteArrayList - где значения байтов отображаются в ваших строках. Если вы хотите увеличить плотность в 4 раза, упакуйте 4 значения в один байт.

Это имеет смысл беспокоиться только тогда, когда у вас много данных - но вы сказали, что миллионы ключей, так что я думаю, что это хорошо подходит.

Answer 6

Java автоматически объединит для вас ссылки на строки, поэтому вам не нужно делать это вручную, чтобы сэкономить память.Вы можете просто поместить ключи / значения в HashMap.