Thank you for your comment, it is really informative and I appreciate it a lot. We looked at the different approaches and I asked my teacher if there is no in-between method, that is, open address hashing combined with linked list hashing where e.g. after an arbitrary amount of elements in the linked list the table is scanned to find the next possible place. I'm sure many things have been tried before. What I don't get is, when is the rehashing done? After a specific insert operation? So then that insert operation will be much slower than all others? I understand that it doesn't matter if the runtime has the same upper bound but it's just not what I instinctively would have thought.