After some thought, you can avoid so much reserve by just not having any reserve buckets (and thus no need for the header either). You can only resize once ever

After some thought, you can avoid so much reserve by just not having any reserve buckets (and thus no need for the header either). You can only resize once every O(sqrt n) operations and a resize costs O(n), so it's amortized O(n / sqrt n) = O(sqrt n) insertion. You can lower the constant factors a bit by doing occasional local reshuffling. Not sure if it's a great idea, but it's tempting.