| CPSC 327 | Data Structures and Algorithms | Spring 2024 |
For separate chaining, elements are inserted at the head of the chain rather than the tail — O(1) to insert at head of a linked list but O(n/N) to insert at the tail (which can be mitigated with a tail pointer, but since the order in the chain doesn't matter, it is simpler and easier just to insert at the head).
For open addressing, deleted elements must be replaced with a special deletion marker which is treated the same as a full spot (i.e. keep going) for find but the same as an empty spot for insert. (An alternative is rehash everything after the deleted element.)