Theoretical question

[weary pier]

is it quite common for std::unordered_map to have unusually high collisions while working with real world data?

I understand that, when the data is completely random, the no of collisions are pretty much constant but, is it very unlikely for data to be such that there are very high number of collisions because of which it takes too much time to compute? How safe is it to use std::unordered_map in real world projects?

and in what situations would you use std::map over std::unordered_map? and vice-versa

[crude burrow]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For more information use !howto ask.

[lone forge]

you can use the buckets API of unordered_map to see how many elements are in a bucket

the benefit of map over unoredered_map is less memory usage, the disadvantage is insertion/deletion and lookup speeds

[weary pier]

what would be the idea situation of use for both ds? and what do you usually prefer using?

[lone forge]

unordered for the speed

[white storm]

the performance of unordered_map in terms of collision are all entirely dependent on the data you have and the quality of the hash function

and the strategy used to convert the hash into a bucket id

typically implementations kinda assume your hash is good

and will use a conversion strategy in consequence

so it's down to the hash and the data

and if you have pathological data for the hash, then you can devolve into a huge linked list

I never had a use for an actual unoredered_map, and map is simpler to setup, so I typically only use a map

[weary pier]

what do you mean by simpler to setup?

[white storm]

and when performance becomes an issue then I would setup a better map, possibly an unordered one, and perform measures on what would/wouldn't be a good hash

map doesn't need a hash function

you just need an order

[weary pier]

true but doesn't the inbuilt hash map already have one?

[lone forge]

ummm, for performance don't people use some 3rd party library with open addressing instead?

[white storm]

which in most cases I've run into, is trivial to define properly

[weary pier]

so you're saying, if you do use an std::unordered_map, you use a custom hash function?

[white storm]

depends but that's an option, which I typically cannot be bothered to test first

since in all cases I need the hash to work

if I got to a hash map I mean

[white storm]

there's no builtin hash for the vast majority of types

so you must provide a hash function in the vast majority of cases

[lone forge]

hash_combine to the rescue

[white storm]

if you use a string as key then there is a hash already provided

[weary pier]

true. The inbuilt one can can't hash user-defined class objects. Is that right?

[white storm]

and oftentime you'd define your "custom" hash in terms of already available ones

since whatever custom key type you want often has some id or string or whatever

[weary pier]

ok thanks!

!solved

[crude burrow]

Thank you and let us know if you have any more questions!

[SOLVED] Theoretical question