>But, if you are making the string part of the entry, that would also require padding the string length to word boundaries so that the struct gets aligned.
It also makes deletion a far more complicated situation. You'd essentially be implementing your own allocator then.
That's true. Maybe you could keep it simpler by making small strings inline with the struct, but larger strings go on the heap. This gives you fixed size records, so removal could be o(1) by swapping with the last one and shortening.
It also makes deletion a far more complicated situation. You'd essentially be implementing your own allocator then.