Find my the solution while I was writing this question, so just decided to share.
Object value = map.get(new Integer(2));
if (map.containsKey(new Integer(2))) {
System.gc(); // can happen here
System.out.println(value);
} else {
System.out.println("Key is deleted");
}
I have to get value first and only then check for key existence. That way I am protected against incorrect result. Current result is:
2
2
that is correct, at least for my case.