[stochastic_monk]

This is getting deep into some wizardry, but if you used a custom pool-like allocator you could group contents close together in cache, and, if necessary/appropriate, even rearrange the elements in the container to be more cache-friendly for your purposes.

[thecompilr]

You could, but the premise of using a tree was to avoid unpredictable rehashing latency, if you start compacting the tree every now and then, you basically pay the same price.

[MaxBarraclough]

That approach tastes rather like a copying+compacting garbage-collector.