[dspeyer]

So we want to insert a value. We find an empty slot. We find the bucket it's in. Do we have to realloc the bucket and move all downstream data down by one? That sounds slow.

[Someone]

'All the data' most of the time are references to all the data.

Also, I would not reallocate, but allocate at max size or, possibly, half size and grow if needed.

With that change, once you access the array, you likely have all pointers to shift in your level 1 cache.

Because of that, I expect it to be plenty fast enough.

(Hm, are there CPUs that have instructions for shifting parts of cache lines around?)