Зависит от того, какой у вас ключ - природа хеш-карты не позволяет легко это сделать.
То, что я могу придумать, вне головы - выбрать случайное число в диапазоне от 1 до размера хэш-карты, а затем начать итерацию по нему, поддерживая счет на ходу - когда счет равен случайное число, которое вы выбрали, это ваш случайный элемент.