Java:如何在hashmap中获取具有相同值的键集

Question

我有一个hashmap如下:

1-> X

2->ÿ

3-> X

4->ž

现在我想知道值为x的所有键(ans:[1,3]).什么是最好的方法？

蛮力方式是迭代map并将所有键存储在值为x的数组中.

有没有有效的方法.

谢谢

Answer 1

散列映射是一种优化的结构,用于使用键对值进行关联访问,但在执行反向操作时却没有比使用数组更好的结构.我不认为你可以做得更好,然后迭代.提高效率的唯一方法是,如果您也有反向哈希映射(即哈希映射,其中您持有指向所有值的给定值的键数组).

Answer 2

您可以使用a MultiMap轻松获取所有这些重复值.

Map<Integer, String> map = new HashMap<Integer, String>();
map.put(1, "x");
map.put(2, "y");
map.put(2, "z");
map.put(3, "x");
map.put(4, "y");
map.put(5, "z");
map.put(6, "x");
map.put(7, "y");

System.out.println("Original map: " + map);

Multimap<String, Integer> multiMap = HashMultimap.create();
for (Entry<Integer, String> entry : map.entrySet()) {
  multiMap.put(entry.getValue(), entry.getKey());
}
System.out.println();

for (Entry<String, Collection<Integer>> entry : multiMap.asMap().entrySet()) {
  System.out.println("Original value: " + entry.getKey() + " was mapped to keys: "
      + entry.getValue());
}

打印出来:

Original map: {1=x, 2=z, 3=x, 4=y, 5=z, 6=x, 7=y}

Original value: z was mapped to keys: [2, 5]
Original value: y was mapped to keys: [4, 7]
Original value: x was mapped to keys: [1, 3, 6]

每@ noahz的建议,forMap并invertFrom需要更少的线,但可以说是更加复杂的阅读:

HashMultimap<String, Integer> multiMap =
    Multimaps.invertFrom(Multimaps.forMap(map), 
        HashMultimap.<String, Integer> create());

取代:

Multimap<String, Integer> multiMap = HashMultimap.create();
for (Entry<Integer, String> entry : map.entrySet()) {
  multiMap.put(entry.getValue(), entry.getKey());
}

Answer 3

如果Java 8是一个选项,您可以尝试流式处理方法:

Map<Integer, String> map = new HashMap<>();
map.put(1, "x");
map.put(2, "y");
map.put(3, "x");
map.put(4, "z");

Map<String, ArrayList<Integer>> reverseMap = new HashMap<>(
    map.entrySet().stream()
        .collect(Collectors.groupingBy(Map.Entry::getValue)).values().stream()
        .collect(Collectors.toMap(
                item -> item.get(0).getValue(),
                item -> new ArrayList<>(
                    item.stream()
                        .map(Map.Entry::getKey)
                        .collect(Collectors.toList())
                ))
        ));

System.out.println(reverseMap);

结果如下:

{x=[1, 3], y=[2], z=[4]}

如果首选Java 7:

Map<String, ArrayList<Integer>> reverseMap = new HashMap<>();

for (Map.Entry<Integer,String> entry : map.entrySet()) {
    if (!reverseMap.containsKey(entry.getValue())) {
        reverseMap.put(entry.getValue(), new ArrayList<>());
    }
    ArrayList<Integer> keys = reverseMap.get(entry.getValue());
    keys.add(entry.getKey());
    reverseMap.put(entry.getValue(), keys);
}

有趣的是,我在执行(索引,随机('a' - 'z')对的大型映射时,尝试了每种算法所需的时间.

              10,000,000        20,000,000
Java 7:         615 ms            11624 ms         
Java 8:        1579 ms             2176 ms

Answer 4

如果您愿意使用库,请使用Google Guava的Multimaps实用程序,特别是forMap()与之结合使用invertFrom()