HashMap is implemented as a dynamic array, and you could probably get "good enough" random performance from accessing the underlying array, picking a random element, then iterating over that bucket and picking a random element. In the average case this will be pretty much constant time.

I'd be a little worried about the randomness of the distribution, but if you need a proper random distribution, you shouldn't be using a map.