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

问题是：是否有更好的数据结构可用于此？

- eikes

Answer 1

任何一个 Map<Integer,String> 都可以 - 你只是在存储字符串的引用，而不是它的副本，因此字符串的长度如何并不重要。

如果您多次构建相同的字符串值，请使用 intern() 每次获取相同的 String 对象。

- Pete Kirkham

---

彼得，说得好。我真的没有时间写一篇论文，所以我刚刚删除了这条评论。 - Kevin Bourrillion

这绝对是正确的答案，但是如果有重复值时不用每次都 map.put(k,v) 不是更好吗？可以像这样做：map.put(k1, k2, ... , kn, v)。 - Christopher Perry

Answer 2

我不是很理解这个问题。如果您有一个字符串数组：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;
//...

- Mark Peters

Answer 3

为什么不将键/值对进行反转？ 使用集合（Set）或数组（array）来存储值：

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

- Jim Kiley

Answer 4

如果您不喜欢Pete Kirkham的建议（在我看来这是最好的方法），您可以使用Google Collections（现在称为Guava）{{link2：MultiMap}}。

- Powerlord

---

我本来也想建议使用MultiMap，但他需要多个键映射到相同的值，而不是相反的情况。 - Stevko

Answer 5

每个地图条目将使用几百个位来表示理论上可以保存在2中的值。

如果密钥比大约1个几百个整数中的1个密度更高，则不使用地图而使用数组会更快且更小——类似于Trove TByteArrayList——其中字节值映射到您的字符串。 如果要获得4倍的密度，请将4个值打包成一个字节。

只有当您拥有大量数据时才有意义——但是您说有数百万个键，因此我认为它非常适合。

- Ed Staub

Answer 6

Java会自动为您合并字符串引用，因此您无需手动执行以节省内存。您只需将键/值放入HashMap中即可。

- btreat

---

这不是真的。如果它是一个字面量，编译器将会内部化字符串，以便相等的字面量被替换为相同的字符串对象，并且您可以手动调用intern()，但Java永远不会在运行时隐式/自动执行任何操作。一旦您有了对Java字符串的引用，Java就不会更改该引用以指向其他后台内容，您始终可以使用new关键字拥有相同字符串的唯一实例。因此，例如从输入流或用户输入中读取的字符串都不会发生这种情况。 - Mark Peters