swift-collections
swift-collections copied to clipboard
[HashTreeCollections] Nodes should shrink themselves when possible
As the prefix tree grows, items inside nodes are slowly replaced with child references. For some Key
/Value
combinations, this reduces the size of the node; it would be nice if we allowed nodes to reallocate themselves to get rid of superfluous capacity.
(We should only do this when the load factor of a node shrinks below some predetermined minimum.)
Implementing this would likely slow down insertions somewhat, but in exchange it would allow better memory utilization -- which would probably be a worthwhile trade off to make.