delete-hashtable.c

// Delete an item from a hash table that uses linear probing to deal with collisions.
void delete(HashTable ht, Key k) {
    int numSlots = ht->nslots;
    Item *data = ht->items; // the actual hash table

    int i; // i is a better counter variable name than j
    int hashPos = hash(k, numSlots); // the position in the hash table

    // probe through the possible slots it could be,
    // starting from the value it actually hashed to,
    // then going along to the next one and so on
    for (i = 0; i < numSlots; i++) {
        // the current position we're looking at, which is the original hash location
        // of the key plus however many slots along we've moved.
        // mod by the table size to "wrap around"
        int currPos = (hashPos + i) % numSlots; 

        // if the item we're looking for is actually in that slot
        // equivalent to something like:
        // if data[currPos] == key_we're_looking_for
        // (but using the function cmp means it can work for things other than ints)
        if (cmp(k, key(data[currPos])) == 0) {
            // we found it in this slot!
            // break here, keeping our current position
        }
        else if (data[currPos] == NoItem) {
            // we've hit an empty slot
            // since we started out on the slot that should have had the
            // item we were looking for, if the key were actually in the
            // hash table, either it would have been in that slot, or
            // it would have been linearly-probed until it found a free slot
            // since this is an empty slot, we didn't find the key in its
            // original slot, nor in any of the slots it could have been
            // pushed into through probing.
            // so, we return from the function to quit:
            return;
        }

        // okay, time to clean up after ourselves
        // since we've just removed something, it's possible that other items
        // had been linearly-probed *past* the thing we just removed
        // since we've just removed an item, there's now an empty slot, so
        // our algorithm to find a node would stop before finding it.
        // so, we go through everything that could have been probed here
        // and make sure it's in the right spot
        
        data[currPos] = NoItem; // removed it from the hash table
        ht->nitems--; // decrease the item counter since we deleted something

        // start from the slot after this one, since we know this one is empty
        i = currPos+1;

        // loop through until we find an empty slot.
        // why does an empty slot mean we can terminate?
        // (answer below)
        while (data[i] != NoItem) {
            // make a temporary copy
            Item tmpItem = data[i];
            // set the slot to be empty
            data[i] = NoItem;

            // we've just deleted something -- why do we decrease but not increase?
            ht->nitems--;

            // reinsert into the hash table
            insert(ht, tmpItem);

            // move to the next slot, wrapping around if we hit the end
            i = (i+1) % numSlots;
        }
    }
}

// And now for the answers:
// We can stop when he hit an empty slot in the hash table because it's not possible
// that some value that was probed past the spot we deleted went past there --
// it would have been inserted into an empty slot (thus not leaving it empty).
//
// We decrease the number of items but don't increase it ourselves because