boolean (@NotNull HashTableData table, int key, int value) { //MAYBE RC: check hash(key) has correct hashSuffix -- but this violates an abstraction of HashAlgo, // so this check is better to be moved to HashSegment? checkNotNoValue("key", key); checkNotNoValue("value", value); int capacity = capacity(table); int startIndex = Math.abs(hash(key) % capacity); int firstTombstoneIndex = -1; for (int probe = 0; probe < capacity; probe++) { int slotIndex = (startIndex + probe) % capacity; int slotKey = table.entryKey(slotIndex); int slotValue = table.entryValue(slotIndex); if (slotKey == key && slotValue == value) { return false;//record already here, nothing to add } if (!isSlotOccupied(slotKey)) { if (slotValue != NO_VALUE) { //slot removed ('tombstone') -> remember the index (for later insertion), but continue lookup if (firstTombstoneIndex == -1) { firstTombstoneIndex = slotIndex; } } else { //(NO_VALUE, NO_VALUE) == free slot // => end of probing sequence, no (key, value) found // => insert it: int insertionIndex = firstTombstoneIndex >= 0 ? firstTombstoneIndex : slotIndex; table.updateEntry(insertionIndex, key, value); incrementAliveValues(table); return true; } } } //Table must be resized well before such a condition occurs! throw new AssertionError( "Table is full: all " + capacity + " items were traversed, but no free slot found" + "table.aliveEntries: " + table.aliveEntriesCount() + ", table: " + table ); //MAYBE RC: actually, it could be there are not-so-many alive entries, but a lot of tombstones, and no free // slots remain. This is because in the current design we never clear tombstones: during segment split we copy // half of alive entries to a new segment, leaving tombstones in old one -- but we never clean the tombstones // in the old segment. Tombstones are somewhat 'cleaned' by reusing their slots for new records, but this is // stochastic, and could be not very effective }