public boolean put(@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;
          }
        }
      }

      //probing sequence went through all the table: i.e. table is full -- but maybe there are tombstones to replace?

      //TODO RC: In the current design we never clear tombstones: during segment split we copy half of alive entries
      // to a new segment, but we leave the tombstones in old one -- hence, 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.
      // Hence, in the current design it could be there are not-so-many alive entries, but a lot of tombstones -- which
      // deteriorates performance.
      // The simplest solution would be to prune the tombstones on segment split in old segment also: currently we copy
      // ~1/2 alive entries in the new segment -- instead we should copy _all_ alive entries into memory buffer first,
      // clean the old segment entirely, and copy the entries from in-memory buffer into old/new segments afterwards.

      if (aliveValues(table) == 0) {
        //If there is 0 alive records => it is OK to clear all the tombstones.
        // We can't clear all tombstones while alive entries exist because such a cleaning breaks lookup: we treat
        // free slots and tombstones differently during the probing -- continue to probe over tombstones, but stop
        // on free slots. Converting tombstone to free slot could stop the probing earlier than it should stop, thus
        // making some existing entries unreachable.
        // But if there are no alive entries anymore -- we finally _can_ clear everything without breaking anything!

        //This deals with the issue above -- table being overflowed by tombstones -- but only partially. This branch
        // fixes correctness (table doesn't fail if there is at least 1 unfilled slot), but doesn't fix performance,
        // which likely is awful long before we reach this branch due to looooong probing sequences

        for (int slot = 0; slot < capacity; slot++) {
          table.updateEntry(slot, NO_VALUE, NO_VALUE);
        }
        return put(table, key, value);
      }

      if (firstTombstoneIndex != -1) {
        //Probing sequence is terminated if:
        // 1) key is found
        // 2) free slot is found
        // 3) no more slots to look for key -- all slots was visited (=key is definitely absent in the map)
        // So, if we scan all the entries and not found a key, but we have found a tombstone along the way
        //  => we can replace it with the entry at hand:
        table.updateEntry(firstTombstoneIndex, 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: " + table
      );
    }
public boolean put(@NotNull HashTableData table,
                       int key,
                       int value)