Menu
Does anyone know of a C/C++ hash table/map implementation that does not dynamically allocate memory? I'm working on an embedded system that has no standard library & no heap (unless I want to write/port one).
695
If you really want to prevent your C++ programs from using dynamic memory allocation, you should replace all four variants of operator new with versions that cause link errors. Four variants of operator delete (one corresponding to each replaceable variant of operator new ) are also replaceable.
Any Hash Table implementation has the following three components: A good Hash function to map keys to values. A Hash Table Data Structure that supports insert, search and delete operations. A Data Structure to account for collision of keys.
i.e. if the range of key values is very small, then most of the hash table is not used and chains get longer. Below is the Hash Map implementation in C++. HashMap class contains the hash table, which is a double pointer to HashNode class and default table size in constant is used to construct this hash table.
The trick is to use Robin Hood hashing with an upper limit on the number of probes. If an element has to be more than X positions away from its ideal position, you grow the table and hope that with a bigger table every element can be close to where it wants to be.
The terms you're looking for are "Open addressing" or "closed hashing". See http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables#Open_addressing and http://en.wikipedia.org/wiki/Open_addressing
Don't know a specific implementation, though. Sorry.
147
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
