Ooops, apologies, didn't analyze this condition properly, you're right, it will go past REMOVED:
while (currentKey != null && (currentKey == REMOVED || !key.equals(currentKey))) { But then -- the same thing applies to put; if you don't find the key in the map and there is a removed slot on the lookup chain, you should probably insert the key in there, instead of taking a new empty slot, right? This is not strictly a bug, but wouldn't cause map growth (or rehashing) if you have interleaved put/removes. Dawid