An open addressing table stores the keys in the array itself. Key k tries the slots
s(k, j) \;=\; (k + j \cdot \mathrm{step}) \bmod m \qquad j = 0, 1, 2, \dots
and takes the first empty one. With step = 1 this is linear probing.
Write open_table(keys, m, step) which inserts the keys in the order given, skipping any key already in the table, and returns the list of m slots with None for the empty ones.
Examples
Input: keys = [10, 15, 20], m = 5, step = 1
Output: [10, 15, 20, None, None]
Explanation: all three hash to slot 0, so the second and third walk on by one.
Input: keys = [0, 5], m = 5, step = 2
Output: [0, None, 5, None, None]
Explanation: 5 starts at slot 0, which is taken, and its next probe is slot 2.
Constraints
1 <= m <= 10**4,1 <= step < mwithgcd(step, m) == 1, so every slot is reachable0 <= len(keys) <= m, keys are non-negative and the distinct ones always fit
Goals
- Place every key inside the table itself, with no side lists
- Follow a probe sequence until an empty slot turns up
- See why the step size must be coprime with the table size