how can i get the number of same-value-more-than-once occurrences for a HashMap in Java?

Question

Is there any easy way to get the keys for which same value exist? Or more importantly, how can i get the number of same-value-more-than-once occurrences?

Consider the hashmap:

1->A
2->A
3->A
4->B
5->C
6->D
7->D

here same-value-more-than-once occurred 3 times(A two times, D one time).That(3) is what i want in return.

I could iterate over the hashmap by the keyset/map.values() list, but it seems quite cumbersome to do that way. Any suggestions or solutions?

EDIT : My context is, i'm working on a timetable generator. The data-structure for a time-slot is

{String day-hour, HashMap<String,Event> Rooms}

For a day-hour, some Event-s are assigned on Rooms map. While checking the fitness of the solution, i need to know if one staff is assigned multiple events on same hour. Hence i want to check how many violations are there in Rooms map by the values Event.getStaff() .

EDIT : Values are objects here, I don't want to count the occurrences of the same objects, rather a field of the object. The EVENT object has a field staff and i need to count the multiple occurrences of staffs.

Answer 1

You could create a wrapper class around (Hash)Map, with decorating the put()-remove() methods to maintain another map, of which the values of the original Map are the keys, and the values are the numbers of occurrences. Then you just have to implement the method to query that...

However, this is rather tricky! You have to be careful not to have links to objects that are not in the map anymore... This could lead to a memory leak!

Also, null value tolerance has to be taken into count...

public static class MyCountingMap<K,V> implements Map<K,V> {
  private final Map<K,V> internalMap;
  //hashmap tolerates null as a key!
  private final Map<V,Long> counterMap = new HashMap<V, Long>();

  public MyCountingMap(Map<K, V> internalMap) {
    super();
    this.internalMap = internalMap;
  }


  @Override
  public V put(K key, V value) {
    boolean containedOriginally = internalMap.containsKey(key);

    V origValue = internalMap.put(key, value);

    updateCounterPut(containedOriginally, origValue, value);

    return origValue;
  }

  @Override
  public void putAll(Map<? extends K, ? extends V> m) {
    //now this is the awkward part...
    //this whole thing could be done through a loop and the put() method, 
    //but I'd prefer to use the original implementation...
    for(Map.Entry<? extends K, ? extends V> entry :m.entrySet()) {
      boolean containedOriginally = internalMap.containsKey(entry.getKey());
      V origValue = internalMap.get(entry.getKey());
      updateCounterPut(containedOriginally, origValue, entry.getValue());
    }


    internalMap.putAll(m);
  }

  // this method updates the counter
  private void updateCounterPut(boolean containedOriginally, V origValue, V newValue) {
    //if it was in the map, and it is different than the original, decrement 
    if(containedOriginally && isDifferent(origValue, newValue)) 
    {
      decrement(origValue);
    }

    //if it was NOT in the map, or the value differs
    if(!containedOriginally || isDifferent(origValue, newValue)) {
      increment(newValue);
    }
  }

  // nothing special, just nicer to extract this to a method. Checks if the two values are the same or not.
  private static boolean isDifferent(Object origValue, Object newValue) {
    return ((origValue==null && newValue!=null) || !(origValue!=null && origValue.equals(newValue)));
  }

  //this method returns the counter value for the map value
  public Long getValueCount(V value) {
    return counterMap.get(value);
  }

  @Override
  public V remove(Object key) {
    V toReturn = internalMap.remove(key);
    if(toReturn!=null) {
      decrement(toReturn);
    }
    return toReturn;
  }

  private void increment(V value) {
    Long count = counterMap.get(value);
    if(count == null) {
      count = 0L;
    }
    counterMap.put(value, count+1);
  }

  private void decrement(V value) {
    Long count = counterMap.get(value);
    if(count == null) {
      count = 0L;
    }

    //last! Have to remove reference to prevent memory leak!!
    if(count == 1L) {
      counterMap.remove(value);
    } else {
      counterMap.put(value, count-1);
    }

  }
  //... boring wrapper methods ...
  public void clear() { internalMap.clear(); }
  public boolean containsKey(Object key) { return internalMap.containsKey(key); }
  public boolean containsValue(Object value) { return internalMap.containsValue(value);   }
  public Set<Entry<K, V>> entrySet() { return internalMap.entrySet();    }
  public V get(Object key) { return internalMap.get(key); }
  public boolean isEmpty() { return internalMap.isEmpty(); } 
  public Set<K> keySet() { return internalMap.keySet(); }
  public int size() { return internalMap.size(); }
  public Collection<V> values() { return internalMap.values(); }
}

Answer 2

How about (expanding on Jon's answer)

Multiset<V> counts = HashMultiSet.create(map.values());
Predicate<Map.Entry<K,V>> pred = new Predicate<Map.Entry<K,V>>(){
   public boolean apply(Map.Entry<K,V> entry){
       return counts.count(entry.getValue()) > 1;
   }
}
Map<K,V> result = Maps.filterEntries(map, pred);

This will result in a map where each key is mapped to a value that is duplicated.

This answer is only needed to address the first part of the question (the "less important part"), to get the keys that have duplicate values.

Answer 3

This is nice way I think:

int freq = Collections.frequency(map.values(), "A");

which returns "3" for your example. Cheers!

EDIT: sorry I misunderstood the question in my first attempt, this should do the trick:

int k = 0;
Set<String> set = new HashSet<String>(map.values());
for (String s : set) {
   int i = Collections.frequency(map.values(), s);
   k += i > 1 ? i - 1 : 0;
}

You will still not be able to retreive the actual keys though. But that was not the most important thing, right?

Answer 4

I don't know the context but what if you use a multimap:

Map<String, List<Integer>>

so this way your map would look like this:

A->1, 2, 3
B->4
C->5
D->6, 7

Answer 5

I could iterate over the hashmap by the keyset/map.values() list, but it seems quite cumbersome to do that way.

Well it's inefficient, but there's not a lot you can do about that, without having some sort of multi-map to store reverse mappings of values to keys.

It doesn't have to be cumbersome in terms of code though, if you use Guava:

Multiset<String> counts = HashMultiSet.create(map.values());
for (Multiset.Entry<String> entry : counts.entrySet) {
  if (entry.getCount() > 1) {
    System.out.println(entry.getElement() + ": " + entry.getCount());
  }
}