Isn't this problem solved entirely by consistent hashing? Even for a non-distributed hash table, you can "distribute" your table over a collection of fixed-size

Isn't this problem solved entirely by consistent hashing? Even for a non-distributed hash table, you can "distribute" your table over a collection of fixed-size blocks in memory or on disk. Maximum cost of rehashing is the cost of splitting a block, which can be made arbitrarily small. The cost can even be paid in parallel in non-pathological scenarios with a push-down/write-through splitting mechanism.