I am writing my own specialized implementation of a hash table in C#. The purpose is to store string instances where the keys may also be ReadOnlySpan and ReadOnlySequence. I chose closed hashing/open addressing strategy with double hashing where XxHash3 is the initial index hash and FNV1a64 is the function for the probing step.

I have problem with implementing the in-place grow algorithm when the load factor is > 0.75 or if collisions are to large. For the most part my algorithm works as intended. The problem is when a string I need to rehash collides with another string even after resizing. I then calculate the step function and go to the next position. If the next position is already occupied it may be there from before the growth operation or it may have been put there during the growth operation. If it was there before I can switch the value I am currently rehashing with the one that still needs to be rehashed. Otherwise I go to the next position and repeat the process. The problem is that I don’t know how would I determine if given position was put there before or during growth without storing additional data with the values or without extra memory to store it during growth.

If I simply allocate a new memory and iterate over the old one this problem isn’t there since all values in the new memory must be also new. At this point I wonder if an in-place growth algorithm for such a hash table is even possible without additional storage.

If anyone knows or already made such a growth algorithm I am interested in how you solved the problem I described above. Otherwise I would appreciate if someone can explain to me why doing it in-place is not viable.

While I am programming in C# I guess the general topic is language agnostic.