# @keys = keys %hash;  # done ONCE
# ($k,$v) = rhe(%hash,@keys);

sub rhe (\%\@) {
    my( $hv, $av )= @_;
    my $idx= rand @$av;
    my $key= $av->[$idx];
    my $val= delete $hv->{$key};
    my $last= pop @$av;
    $av->[$idx]= $last   if  $idx < @$av;
    return( $key, $val );
}

##</code><code>##

@keys = keys %hash;
@vals = values %hash;
undef %hash;