When OpenHashMap.put(key, hash, value) probes for a slot, if it finds one already occupied by key (and its hash), it uses that, else it uses the first empty slot. The shortcoming of this algorithm is that get() will potentially have to probe over many deleted entries to find the desired key.

We can shorten this search by instead, in put(), storing into the first slot found in the probe sequence that was either deleted, or that contains the current value of the key; or into the first empty slot (but now only if no deleted slot nor current value was found first).

This implies that if a slot holding an old entry (current or deleted) for the key was found, it will not be used if there was a deleted slot preceding it in the probe sequence. It also implies that, if no entry (current or deleted) for the key was found, the empty slot may not necessarily be used—an earlier, deleted slot from another key would be preferred.

The idea is from Knuth, The art of computer programming, 2nd ed., v. 3, (1998), p. 533: "can be inserted in place of the first deleted or empty position that was encountered."