CODEWITHSUNDEEP
javahashmap
javaMan
javaMan

Reputation: 6680

Java: How to get set of keys having same value in hashmap

I have a hashmap as below:

1->x

2->y

3->x

4->z

Now i want to know all keys whose value is x (ans: [1,3] ). what is best way to do?

Brute force way is to just iterate over map and store all keys in array whose value is x.

Is there any efficient way for this.

Thanks

Upvotes: 17

Views: 58101

Answers (10)

Pangur
Pangur

Reputation: 594

I agree with George Campbell but for java 8 I would do it a bit easier:

Map<String, List<Integer>> reverseMap = map.entrySet()
    .stream()
    .collect(Collectors.groupingBy(Map.Entry::getValue,
        Collectors.mapping(
            Map.Entry::getKey,
            Collectors.toList())));

Upvotes: 2

user2782963
user2782963

Reputation: 1

Try This.....

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());

    }

Upvotes: -1

George Campbell
George Campbell

Reputation: 576

If Java 8 is an option, you could try a streaming approach:

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);

Which results in:

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

If Java 7 is preferred:

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);
}

As an interesting aside, I experimented with the time required for each algorithm when executing large maps of (index,random('a'-'z') pairs.

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

Upvotes: 8

noahlz
noahlz

Reputation: 10311

If you are open to using a library, use Google Guava's Multimaps utilities, specifically forMap() combined with invertFrom()

Upvotes: 6

Cuga
Cuga

Reputation: 17904

You can use a MultiMap to easily get all those duplicate values.

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());
}

Prints out:

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]

Per @noahz's suggestion, forMap and invertFrom takes fewer lines, but is arguably more complex to read:

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

in place of:

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

Upvotes: 11

Jonathan
Jonathan

Reputation: 20375

If you already have a map, you should consider using Google's Guava library to filter the entries you're interested in. You can do something along the lines of:

final Map<Integer, Character> filtered = Maps.filterValues(unfiltered, new Predicate<Character>() {
    @Override
    public boolean apply(Character ch) {
        return ch == 'x';
    }
});

Upvotes: 2

manub
manub

Reputation: 4100

HashMap computes the hashcode() of the key, not of the values. Unless you store some kind of additional information, or consider using a different data structure, I think the only way you can get this is brute force.

If you need to perform efficient operation on the values, you should think whether you're using the appropriate data structure.

Upvotes: 3

giorashc
giorashc

Reputation: 13713

If you are using a hashmap there is no efficient way doing it but iterating the values

Upvotes: 2

yshavit
yshavit

Reputation: 43391

Yup, just brute force. You can make it fast by also storing a Multimap from Value -> Collection of Key, at the expense of memory and runtime cost for updates.

Upvotes: 4

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70931

A hashmap is a structure that is optimized for associative access of the values using the keys, but is in no way better in doing the reverse then an array for instance. I don't think you can do any better then just iterate. Only way to improve efficiency is if you have a reverse hash map as well(i.e. hash map where you hold an array of keys pointing to a given value for all values).

Upvotes: 13

Related Questions