DeadLock In ConcurrentHashMap

Question

Following code when run, never terminates and stuck in endless loop.

I am not sure where it is getting stuck.

Interesting thing is when I change AaAa to AAAA every thing works fine as expected.

 public class Test {

    public static void main(String[] args) {

        Map<String, Integer> map = new ConcurrentHashMap<>(16);
        map.computeIfAbsent(
                "AaAa",
                key -> {
                    return map.computeIfAbsent(
                            "BBBB",
                            key2 -> 42);
                }
        );
    }

}

Can some one help me understanding this behavior.

FYI : http://stackoverflow.com/questions/9406775/why-does-string-hashcode-in-java-have-many-conflicts — Mehraj Malik, May 09 '17 at 06:09

Eran · Answer 1 · 2017-05-09T05:49:58.503

16

"AaAa" and "BBBB" have the same hashCode() - 2031744. Therefore both keys are mapped to the same bin of the Map.

The outer map.computeIfAbsent locks that bin, and the inner map.computeIfAbsent tries to lock it before the lock is released - hence the deadlock.

edited May 09 '17 at 05:49

answered May 09 '17 at 05:46

Eran

387,369
54
702
768

1

@Eran--OMG how do you check all this so quickly ...awesome stuff...(Y) – T-Bag May 09 '17 at 05:47
1

@ShowStopper I happen to be sitting next to a computer with Eclipse open, so it doesn't take much time to run `System.out.println ("AaAa".hashCode ());` and `System.out.println ("BBBB".hashCode ());` :) – Eran May 09 '17 at 05:49
2

I love it when those perfect answers come in quickly. I just hate it when I am not the author of it. Still, you got my vote. – GhostCat May 09 '17 at 05:51
Some [more](http://stackoverflow.com/questions/9406775/why-does-string-hashcode-in-java-have-many-conflicts) conflicts for `String.hashCode()` . – Sanket Makani May 09 '17 at 05:53
But the interesting thing is that, should not hashcode() generate unique hash value for two different String? – Mehraj Malik May 09 '17 at 05:59
2

@MehrajMalik No, it should not and cannot. The are 2^32 unique hashCodes. There are many more unique Strings. – Eran May 09 '17 at 06:03
@Eran Thanks, **a2 * 31^2 + b2** I got clear answer by merging your theory with this formulate. – Mehraj Malik May 09 '17 at 06:08
It's interesting that a thread can deadlock itself this way. Normal `synchronized` uses reentrant monitor locks that don't have this problem, but I guess `ConcurrentHashMap` uses some type of lock that does. I wonder if this should be considered a bug? – ruakh May 09 '17 at 06:28
@ruakh--Why are you pointing it to bug , its the user who created dead lock not the implementation ...:( Could you please explain it bit more seems you have interesting point here – T-Bag May 09 '17 at 06:41
@ShowStopper: I suggested that it might be a bug because client code shouldn't have to worry about the exact lock implementation used by `ConcurrentHashMap`; but I was wrong, because I now see that [the documentation for `computeIfAbsent`](https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html#computeIfAbsent-K-java.util.function.Function-) explicitly says not to do this, so the client code is indeed ill-behaved. – ruakh May 10 '17 at 04:13

score 0 · Answer 2 · answered May 09 '17 at 06:27

Whenever two different objects have the same hash code, we call this a collision.

A collision is nothing critical, it just means that there is more than one object in a single bucket, so a HashMap lookup has to look again to find the right object. A lot of collisions will degrade the performance of a system, but they won’t lead to incorrect results.

But if you mistake the hash code for a unique handle to an object, e.g use it as a key in a Map, then you will sometimes get the wrong object.

In Java there are 4,294,967,296 compartments (2^32 possible int values). With 4 billion slots, collisions seem to be extremely unlikely, right? Because even though collisions are rare, they are inevitable. For example, the Strings "Aa" and "BB" produce the same hashCode: 2112."AaAa" and "BBBB" have the same hashCode() - 2031744 and many more.

Objects that are equal must have the same hash code within a running process

Please note that this does not imply the following common misconceptions:

Unequal objects must have different hash codes – WRONG!
Objects with the same hash code must be equal – WRONG!

DeadLock In ConcurrentHashMap

2 Answers2