Just checking the internal impl of Java HashMap.containsKey(). It uses the getNode method. 1 interesting thing I saw is that it always checks the first node. I'm not sure how efficient this is, but these simple checks can make any algo significantly faster, even by a few %