U-map can degrade to O(N) performance if the hash keys are not friendly to your data.
map retains O lg(N) even when things go wrong.
you can get back to O(1) if you hand-roll your own hash table into a vector with no collisions if the data is well suited to it. Some data cannot be hashed clean easily.
also, remember, that a O(1) where 1 takes 20 min is slower than O(N*N) where N*N takes 2 nanoseconds until N becomes big enough to slow the N*N part more than the O(1).
Not easily. I would have to craft something that performs poorly in U-map and then show it working better with regular map. Let me think on that one. You can search the web on this issue too -- should say what I said with many more words and much more depth.
I could show you how to roll your own table...
you just want an oversized array/vector and a function such that
arrayindex = f(data);
such that vector[f(data)] is your guy, and F should be as fast as you can make it. Making F can be a major effort for weird data, or very simple.
if you allow collisions in your table (and sometimes this cannot be avoided) you need to handle that. Handling this makes it slower... its best if you can find a way to not collide at all.