Baza danych Java do odwzorowania wielu kluczy na tę samą wartość

Question

W języku Java szukam sposobu mapowania wielu kluczy na tę samą wartość. Powiedzmy mam numery 0-9 klucze, jak i „X”, „Y” i „Z” jako wartości w następujący sposób:

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

teraz X, Y i Z są naprawdę długie ciągi i mam miliony kluczy, więc nie mogę pozwolić sobie na wielokrotne przechowywanie napisów. Jak byś to zrobił?

Jedną z idei było stworzenie dwóch tablic: wygenerowano sztuczną sekundę do klucza, do której zamapowano oryginalne klucze, a która w innej tablicy jest kluczem do rzeczywistych wartości. W ten sposób wartości są przechowywane tylko raz i oryginalne klucze mogą nadal być pośrednio przypisane do wartości:

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 

Pytanie jednak: Czy istnieje lepsza struktura danych do tego?

Answer 1

Wszelkie Map<Integer,String> zrobi - są przechowywane tylko odniesienie do łańcucha, a nie kopię, więc nie ma znaczenia, jak długo jest.

Jeśli wielokrotnie tworzysz tę samą wartość ciągu, użyj intern(), aby za każdym razem uzyskać ten sam obiekt String.

Answer 2

Nie bardzo rozumiem pytanie. Jeśli masz tablicę ciągów znaków: String[] arr, po prostu ustaw różne indeksy dla tego samego obiektu - podobnie, aby odniesienia były takie 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 3

Dlaczego nie odwrócić parowania klucz/wartość? Użyj Set lub tablicę dla wartości:

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

Answer 4

Java automatycznie konsolidować referencje ciąg dla ciebie, więc nie trzeba tego robić ręcznie w celu zaoszczędzenia pamięci. Możesz po prostu umieścić klucze/wartości w HashMap.

Answer 5

Jeśli nie podoba ci się sugestia Pete'a Kirkhama (która byłaby najlepsza, IMO), możesz użyć Kolekcji Google (er ... Guava teraz) MultiMap.

Answer 6

Każdy wpis mapa użyje kilkaset bitów reprezentuje wartość, która teoretycznie mogłaby być przechowywana w 2.

Jeśli klawisze są bardziej gęste niż jakiegoś numeru z rzędu 1 raz na kilkaset całkowitymi, to będzie szybszy i mniejszy, aby nie korzystać z mapy, ale z tablicy - coś jak Trove TByteArrayList - gdzie wartości bajtów są odwzorowywane na twoje struny. Jeśli chcesz uzyskać 4 razy większą gęstość, spakuj 4 wartości w jeden bajt.

To ma sens tylko wtedy, gdy masz dużo danych - ale powiedziałeś miliony kluczy, więc myślę, że to dobrze pasuje.