How to update a value, given a key in a java hashmap?

Question

Suppose we have a `HashMap<String, Integer>` in Java. How do I update (increment) the integer value of the string key for each existence of the string I find? One could remove and reenter the pair, but overhead would be a concern. Another way would be to just put the new pair and the old one would be replaced. In the latter case, what happens if there is a hashcode collision with a new key I am trying to insert? The correct behavior for a hashtable would be to assign a different place for it, or make a list out of it in the current bucket.

Answer 1

Well, let me offer some practical advice here. When using the Java Collections [and related] framework, we need to assume that the Class implementations of Map, List, Set, .... are as efficient as they need to be.

Regardless the "hostile" environment an instance of HashMap might find itself, the aMap.put(key, value) method will always do something reasonable if / when there's a key collision - anything from resizing the table to what you suggest above using a list or a secondary hashtable.

Whatever it does, a collision will be handled as efficiently as possible.

So in response to your final line of questioning, I might ask, why do you care? ;-)

If it's strictly an academic exercise, or you have evidence of not-so-efficiently handled collisions, okay, read on.

There are things we can do as developers to almost guarantee that collisions won't occur (or better stated, seriously reduce the odds).

1) always instantiate a Map implementation with a pre-defined size.

Map<String, Integer> aMap = new HashMap<String, Integer>( n );

// rather than using the default constructor - Map aMap = new HashMap( );

2) as a developer who's familiar with the application you're building/updating, you should know

the rough number (within a range) of key/value pairs that would tend to be managed in the map at runtime.

So oversize the initial size (if it's practical to do so) ... go 10/20 X

3) Better yet, make that number a nice odd/prime number. Why? Because of the way modulo arithmetic is

used to determine the placement of a key/value pair, initial sizing the table to a prime number will reduce

the chances of collisions. So if I were defining the Map you describe here, and I knew there were to be

about 50~100 key/value pairs stored, I might instantiate the map as follows:

Map<String, Integer> aMap = new HashMap<String, Integer>( 541 );

4) As for the most efficient "counter" update logic, I suggest something like this:

int count = 1;

if(aMap.containsKey(aKey) == true) {

count = aMap.get(aKey);

count++;

}

aMap.put(aKey, count);

Don't remove a key/value pair only to put it back in - no need.

And we can interrogate the KeySet before getting a count value that may not be present ...

The put() is performed unconditionally - count will either be 1, or > 1.

Finally, if you're really interested in how a Map implementation handles a collision, go look at the code.

It's Java - it's all there.

In the 1.8 Java platform that I'm using, I can drill down through HashMap.put as follows (at first glance, I decided that I'm not particularly interested ;-) ):

public V put(K key, V value) {

return putVal(hash(key), key, value, false, true);

}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n, i;

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

else {

Node<K,V> e; K k;

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

e = p;

else if (p instanceof TreeNode)

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

else {

for (int binCount = 0; ; ++binCount) {

if ((e = p.next) == null) {

p.next = newNode(hash, key, value, null);

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

treeifyBin(tab, hash);

break;

}

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

break;

p = e;

}

}

if (e != null) { // existing mapping for key

V oldValue = e.value;

if (!onlyIfAbsent || oldValue == null)

e.value = value;

afterNodeAccess(e);

return oldValue;

}

}

++modCount;

if (++size > threshold)

resize();

afterNodeInsertion(evict);

return null;

}