• Advertisement

Archived

This topic is now archived and is closed to further replies.

Do I need a hash table?

This topic is 6013 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a static number of slots in an array that I want to allocate on demand. I want to efficiently allocate these array entries. Currently to find an empty element I start at array[0] and iterate through till I find a null value then allocate that, of course as the numbers get big the chance that you''ll have to iterate more to find an empty slot will be higher. I briefly read a text book on hashing algorithms that use some random tricks to find an empty slot faster. Is this what a hash table is built for? Some uses I need this for: -Alloacating UserID''s when connecting to a server. -Allocating resources when loaded(sounds, images, shaders etc, etc)

Share this post


Link to post
Share on other sites
Advertisement
Hashtables may not be suitable for what you''re trying to accomplish. They are good for fast lookup and insertions using some sort of unique key.



I think some sort of Memory Pool would work well.

The basic idea is to make a linked list of the free elements (or a freelist) in the large array you want to manage. When an allocation request comes in, you can just return the first element the freelist. When a de-allocation request comes in, your can return the piece of memory to either the head or the tail of the freelist. This makes allocation + deallocation request a constant time operation.

Of course, it doesn''t make much sense to use a bunch of memory to store the linked list, especially when the array elements are fairly small. The trick here is to use the array elements themselves as nodes in the freelist. Since Memory Pools track the list elements not being used, it means there are no important information stored in the elements. It is perfectly reasonable, then, to use the memory occupied by the unused elements for some othe purpose. You can simply "overlay" your link list structure on top free array elements that are being managed.

I think the book, "Effective C++", mentions this particular structure and has sample source code included as well. You might want to search around on the net for it.

Share this post


Link to post
Share on other sites

  • Advertisement