Lab 14, Task 4

1. The key "dog" has been inserted incorrectly. It should have been 
   hashed to position 4. For it to end up in position 5, something would 
   need to have been present in position 4, but this position is white, 
   indicating that nothing has ever been there.

2. h("ferret") = 5
   We start at position 5 and keep incrementing by 1 (wrapping around as 
   needed) until we reach an empty cell.
   Thus, the probe sequence is: 5, 6, 0, 1, 2, 3, 4

3. It ends up in position 6, the first removed position seen during probing.

4. h("dolphin") = 3
   probe sequence:       3 % 7 = 3 (occupied)
                   (3 + 1) % 7 = 4 (removed)
                   (3 + 4) % 7 = 0 (occupied)
                   (3 + 9) % 7 = 5 (empty)

   The item ends up in position 4, the first removed position seen
   during probing.

5. h("ant") = 0
   probe sequence:       0 % 7 = 0 (occupied)
                   (0 + 1) % 7 = 1 (occupied)
                   (0 + 4) % 7 = 4 (occupied)
                   (0 + 9) % 7 = 2 (occupied)
                  (0 + 16) % 7 = 2 (occupied)
                  (0 + 25) % 7 = 4 (occupied)
                  (0 + 36) % 7 = 1 (occupied)
   
   And now we have checked 7 positions (where 7 is the table size) 
   without finding an empty cell. We stop probing, because the 
   probe sequence will repeat itself. There are two empty cells (5 and 6), 
   but quadratic probing is not able to find them.
   
   Because no removed or empty cells were encountered during probing, 
   the item cannot be inserted, and we have overflow.

6. If we use separate chaining, every position in the table acts as a 
   bucket that can store more than one item. These items are chained 
   together using a linked list.

   Every item will go in the position given by its hash code, and we 
   don't need to perform any probing.
 
   Thus: 
    - "canary" will join "cat" in position 2
    - "dolphin" will move to position 3
    - "ant" will join "aardvark" in position 0.

   The resulting table looks like this:

    0: aardvark, ant
    1: bison
    2: cat, canary
    3: dolphin
    4:
    5:
    6: