Well, depending on your rehash trigger (i.e. if it is dictated by the load factor, not the number of reprobes), it can be guaranteed that the new array does not

Well, depending on your rehash trigger (i.e. if it is dictated by the load factor, not the number of reprobes), it can be guaranteed that the new array does not need to be rehashed before the in-progress migration, if you migrate at least one bucket per write operation. If you were to (sensibly) migrate many (say, >= 16) with each write, the likelihood of this happening is very low with any reasonable hash function, since the work of rehashing will typically be done many times faster than the skew can retrigger your rehash. This at least makes the incidence of a latency-inducing event of waiting for the prior rehash to complete very low. If you rehash based on something like "number of reprobes" then it's probably impossible to absolutely guarantee that a rehash cannot be triggered before a prior one begins, but the linked approach would permit growing the backing array discontiguously (assuming an extra level of indirection to the backing array). But this would obviously incur some extra overheads, and is not entirely dissimilar to hash-tries, which also avoid any costly global rehash. I think the class-level comment in the code I linked is perhaps the best introduction to split-ordered lists I know of (not hash-ordered; they're sorted by the reverse bitstring of the hash), since they're not widely discussed and not immediately intuitive.