logo标签列表

Java：如何获取HashMap中具有相同值的键集

javahashmap
17
我有一个如下的哈希表：

1->x

2->y

3->x

4->z

我想知道所有值为x的键（答案：[1,3]）。最好的方法是什么？
暴力的方法是遍历整个哈希表，并将所有值为x的键存储在数组中。
是否有更有效的方法呢？
谢谢
10个回答
13

哈希表是一种针对使用键进行关联访问值进行优化的结构，但在执行反向操作时与数组等数据结构相比并没有更好的表现。我认为你只能通过迭代来实现。唯一提高效率的方法是同时拥有一个反向哈希映射（即哈希映射，其中包含指向给定值的所有键的数组）。

没错。如果只提供一个HashMap，任何其他工具也会进行迭代。 - Denys Séguret
11
你可以使用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());
}
问题陈述中提到他“已经有了一个HashMap。因此，使用Multimaps.forMap()和invertFrom()是更简洁的解决方案。” - noahlz
不确定“更简洁”是什么意思，因为它只减少了一行，但我已经更新以反映您的答案。 - Cuga
8
如果您使用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
1
无法推断Hashmap<>的类型参数。 - Chaitanya Uttarwar
它给出了错误信息“无法推断Hashmap<>的类型参数”。 - Ahmad Tn
6
4

是的，只需要 brute force（暴力破解）。你可以通过同时存储一个 Multimap（从 Value -> Key 集合）来提高速度，但这会牺牲内存和运行时成本。

3

HashMap计算的是键的hashcode()，而不是值。除非您存储了某种附加信息，或者考虑使用不同的数据结构，否则我认为您唯一能够做到这一点的方法就是采用暴力方法。

如果您需要对值执行高效操作，则应考虑是否使用适当的数据结构。

2
如果你已经有了一张地图，你可以考虑使用Google的Guava库来过滤你感兴趣的条目。你可以按照以下方式进行操作：
final Map<Integer, Character> filtered = Maps.filterValues(unfiltered, new Predicate<Character>() {
    @Override
    public boolean apply(Character ch) {
        return ch == 'x';
    }
});
或者...也许是Multimaps.forMap()，当与invertFrom()结合使用时，正好可以满足提问者的要求？ - noahlz
不错的解决方案，我会在以后记住的。 - Jonathan
如果你只想要一个特定值的键（这是 OP 所要求的），那么这个解决方案是最好的；不需要在过程中创建两个 MultiMap。请注意，你不必编写自己的谓词；只需使用 Maps.filterValues(unfiltered, Predicates.equalTo('x')).keySet() 即可。 - Russell Zahniser
2
如果您正在使用哈希映射，那么没有有效的方法可以实现它，除了迭代值。
2

我同意George Campbell的观点，但对于Java 8，我会更加简单:

Map<String, List<Integer>> reverseMap = map.entrySet()
    .stream()
    .collect(Collectors.groupingBy(Map.Entry::getValue,
        Collectors.mapping(
            Map.Entry::getKey,
            Collectors.toList())));
1
从技术上讲，这应该是 Collectors.toSet() 而不是 Collectors.toList()。 - malat
-1

试试这个......

public static void main(String[] args) {
        HashMap<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("cust_tenure", "3_sigma");
        hashMap.put("cust_age", "3_sigma");
        hashMap.put("cust_amb_6m_sav", "3_sigma");
        hashMap.put("cust_amb_6m_chq", "3_sigma");
        hashMap.put("cust_total_prod_6m", "3_sigma");

        HashMap<String, ArrayList<String>> result = new LinkedHashMap<String, ArrayList<String>>();

        for (String key : hashMap.keySet()) {
            ArrayList<String> colName = null;
            if (!result.containsKey(hashMap.get(key))) {
                colName = new ArrayList<String>();
                colName.add(key);
                result.put(hashMap.get(key), colName);
            } else {
                colName = result.get(hashMap.get(key));
                colName.add(key);
                result.put(hashMap.get(key), colName);
            }

            System.out.println(key + "\t" + hashMap.get(key));
        }

        for (String key : result.keySet()) {
            System.out.println(key + "\t" + result.get(key));
        }

        System.out.println(hashMap.size());

    }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接