Hashmap

That would depend on little things like what language you're asking about and which hash map implementation you're talking about.

That would depend on little things like what language you're asking about and which hash map implementation you're talking about.

Sorry. C++ STL datastructure is what I meant.

Thanks

There is no standard 'hashmap' in C++. Maybe you are talking about std::map? In that case, its usually created like a tree, possibly a red-back tree. So new memory node gets allocated on every new insert. Maybe you should post your problem and we could take a look?

Au contraire.


(And also this.)

@Dr. Chettri. I'm not actually looking for the exact datastructure. I'm using an engine that hides that from me. So I was looking at hashmap type datastructures in general.
It seems however that there are various ways that these "hashmap" type datastructures function.

Like the map which is a tree compared to the unordered set.

@Apo I was actually more worried about the unordered set type of implementation where there are buckets involved. I'm not sure, but I think I read it somewhere that the buckets are pre-allocated, which means that there maybe unused data storage. I also read that this would cause fragmentation of memory over time. Hence the concern and question.

Thanks Guys

There is no more reason to worry about unused storage in an unordered_map (a.k.a hash_map) than there is for a vector. Both will only allocate a small amount of memory initially, and will acquire more at the point it becomes necessary. It's not going to allocate 10000 buckets for a container holding only 5 items and it's not going to have only 10000 buckets for a container holding 5 million items. These things adapt.

In all my years of PC programming fragmentation has never been an issue, and there is certainly no way in which the unordered_map is going to cause significantly worse fragmentation than an ordinary map, if it's even worse at all.

Most likely, ALL of your concerns are unfounded. It's pretty much just a trade-off between average-case-speed and orderedness when choosing it over a regular map.

Well thanks.
Thats good to hear.
I tried really hard to find the article I read but couldn't find it .