Cơ sở hạ tầng Java để ánh xạ nhiều khóa tới cùng một giá trị

Question

Trong Java, tôi đang tìm cách ánh xạ nhiều khóa tới cùng một giá trị. Hãy nói rằng tôi có những con số 0-9 như phím, và "x", "y" và "z" như các giá trị như sau:

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

tại x, y và z là chuỗi rất dài, và tôi có hàng triệu khóa để tôi không thể đủ khả năng để lưu trữ các chuỗi nhiều lần. Làm thế nào bạn sẽ đi về nó?

Một ý tưởng tôi có là tạo hai mảng: một giây nhân tạo đến khóa được tạo ra để các khóa gốc được ánh xạ và trong đó một mảng khác là khóa cho các giá trị thực. Bằng cách đó, các giá trị chỉ được lưu trữ một lần và các khóa ban đầu vẫn có thể được ánh xạ gián tiếp tới các giá trị:

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 

Câu hỏi: Có cấu trúc dữ liệu tốt hơn không?

Answer 1

Bất kỳ Map<Integer,String> sẽ làm - bạn chỉ được lưu trữ một tham chiếu đến chuỗi, không phải là một bản sao của nó, vì vậy nó không quan trọng nó là bao lâu.

Nếu bạn đang tạo cùng một giá trị chuỗi nhiều lần, hãy sử dụng intern() để nhận cùng một đối tượng Chuỗi cho giá trị mỗi lần.

Answer 2

Tôi thực sự không hiểu câu hỏi. Nếu bạn có một chuỗi các chuỗi: String[] arr thì chỉ cần đặt các chỉ mục khác nhau cho cùng một đối tượng - hay còn gọi là tham chiếu giống nhau.

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

Tại sao không đảo ngược cặp khóa/giá trị? Sử dụng Tập hợp hoặc mảng cho các giá trị:

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

Answer 4

Java sẽ tự động hợp nhất tham chiếu Chuỗi cho bạn, do đó bạn không cần phải thực hiện thủ công tham chiếu để tiết kiệm bộ nhớ. Bạn chỉ có thể đặt các khóa/giá trị trong HashMap.

Answer 5

Nếu bạn không thích đề xuất của Pete Kirkham (đó sẽ là cách tốt nhất, IMO), bạn có thể sử dụng Google Collections (er ... Guava bây giờ) MultiMap.

Answer 6

Mỗi mục bản đồ sẽ sử dụng vài trăm bit để đại diện cho một giá trị về mặt lý thuyết có thể được giữ trong 2.

Nếu các phím có nhiều dày đặc hơn một số số vào thứ tự của 1 mỗi vài trăm số nguyên, nó sẽ được nhanh hơn và nhỏ hơn để không sử dụng bản đồ nào cả, nhưng một mảng - giống như một số Trove TByteArrayList - nơi các giá trị byte được ánh xạ tới các chuỗi của bạn. Nếu bạn muốn nhận được mật độ nhiều hơn 4 lần, hãy đóng gói 4 giá trị thành một byte đơn.

Điều này chỉ có ý nghĩa khi bận tâm khi bạn có nhiều dữ liệu - nhưng bạn đã nói hàng triệu khóa, vì vậy tôi nghĩ nó phù hợp.