return key for common values in hash map

Question

I have a hash map. Multiple keys have same value. What is the best way to find the

keys for repeated Values without iterating. ?

Reading this documentation it feels there is no function for it.

NOTE: Key | Value pair are of Int type

see here http://stackoverflow.com/questions/1383797/java-hashmap-how-to-get-key-from-value — PSR, Mar 06 '13 at 13:59
@PSR I did went through the Question, but I still don't find a function to return me what i need. — Umesh Moghariya, Mar 06 '13 at 14:00
That may be a stupid question, but why don't you want to iterate? Iterating is fine, you know, it's not dirty. — Cyrille Ka, Mar 06 '13 at 14:02
@CyrilleKarmann Iterating is not dirty, but if there is a Smarter way. — Umesh Moghariya, Mar 06 '13 at 14:03
It's important to note whether or not you're strictly limited to a standard map, or if you can use different structures. — Dave Newton, Mar 06 '13 at 14:06

score 0 · Answer 1 · answered Mar 06 '13 at 14:00

There is no way to find all the keys for a value without iterating on the Map in standard JDK API.

You can use the Guava library, either by :

using Maps.filterValues that returns entries whose values satisfy a Predicate
converting to a Guava Multimap and use Multimaps.invert
using a BiMap.

Sergey Kalinichenko · Accepted Answer · 2013-03-06T14:12:53.317

0

One way or the other, you will end up iterating the collection. The iteration may be hidden from view in some library, but it would necessarily be there.

You can easily write a simple method that does what you need:

public static <K,V> Set<K> keysOfDupValues(Map<K,V> m) {
    Set<K> res = new HashSet<K>();
    Map<V,K> seen = new HashMap<V,K>();
    for (Map.Entry<K,V> e : m.entrySet()) {
        V v = e.getValue();
        K k = e.getKey();
        if (seen.containsKey(v)) {
            res.add(k);
            res.add(seen.get(v));
        } else {
            seen.put(v, k);
        }
    }
    return res;
}

Demo on ideone.

edited Mar 06 '13 at 14:12

answered Mar 06 '13 at 14:03

Sergey Kalinichenko

714,442
84
1,110
1,523

Still wondering, I have multiple values to multiple keys which are same. But I think I can tweak this. – Umesh Moghariya Mar 06 '13 at 14:15

score 0 · Answer 3 · answered Mar 06 '13 at 14:06

It's really not possible. The very implementation of method containsValue(), in the superclass java.util.AbstractMap iterates through the values.

So, you'll have to itarate through the values to achieve that.

You can take a look at the implementation of containsValue() to have a hint on how to do that.

didierc · Answer 4 · 2013-03-06T14:21:59.010

If you get that map read made from code you don't have control on, then you have no other choice but to iterate on the map.

In any case, you can avoid the issue of doing several iterations by building a reverse map, which will boil down to a multimap, but since there is no specific class definition for that pattern in Java, you will have to build it using a map and lists.

Each time you need to include a new pair <k,v> in your original map, you also include the reverse pair <v,k> in your reverse map. If v as a key (ie. the original value) doesn't yet exist in the reverse map, you map it to a list solely containing k as the value (ie. the original key). If the key v already exists in the reverse map, then you simply push the value k to the existing list.

When you need to know which keys map to a given value in your original map, you query for the value in the reverse map, and get the list of keys.

The Java tutorial on maps includes a section on implementing multimaps using maps.

This solution should be very effective if you have control on the map creation process. However, if the map is created and regularily updated by some outside mechanism, it will be of little gain.

If you can only control the creation of the map, but not its update, you could implement a new class exposing the Map interface, which internally holds the reverse map as well and update it when a new pair is inserted/removed, or support a notification mechanism to let your code know the map has been changed and how.

score 0 · Answer 5 · answered Mar 06 '13 at 15:14

0

Try change

File newxmlfile = new File(Environment.getExternalStorageDirectory()
+ ts);
to
File newxmlfile = new File(Environment.getExternalStorageDirectory()
+ "/"+ts);

answered Mar 06 '13 at 15:14

QArea

4,955
1
12
22

return key for common values in hash map

5 Answers5