The hash table is implemented as an open-addressed table with
linear probing collision resolution.
- In regular language, it means that all the hash entries (pairs of
- pointers key and value) are stored in a contiguous array. The
- position of each mapping is determined by the hash value of its key
- and the size of the table: location := hash(key) % size. If two
- different keys end up on the same position (collide), the one that
- came second is placed at the next empty position following the
- occupied place. This collision resolution technique is called
- "linear probing".
+ The above means that all the hash entries (pairs of pointers, key
+ and value) are stored in a contiguous array. The position of each
+ mapping is determined by the hash value of its key and the size of
+ the table: location := hash(key) % size. If two different keys end
+ up on the same position (collide), the one that came second is
+ placed at the next empty position following the occupied place.
+ This collision resolution technique is called "linear probing".
There are more advanced collision resolution methods (quadratic
probing, double hashing), but we don't use them because they incur