Memory fragmentation can be avoided by construction, e.g. using trees allocated in linear storage (e.g. like std::map is implemented, or the maps in libsrt [1])

Memory fragmentation can be avoided by construction, e.g. using trees allocated in linear storage (e.g. like std::map is implemented, or the maps in libsrt [1]). For strings a binary tree (or a B/B+ could be faster), and it would not require defragmentation nor rehashing (and worst access time would be log(n), instead of O(n)). Make growing the tree using realloc() is "free" on systems with virtual memory map/remap. [1] https://github.com/faragon/libsrt https://github.com/faragon/libsrt