I find your hashref-checking code quite strange—you are de-referencing (%{$HASH_REF}) a hashref ($HASH_REF), then treating the de-reference as a hash-ref itself ({%{$HASH_REF}}->{$random_number})—which I wouldn't expect to run at all. (UPDATE: kyle explained what I was too sleepy to notice—the extra pair of braces is re-creating a hashref from the de-referenced hashref, and you're then de-referencing it again before checking for existence.) Anyway, it does run, and I also observe a significant slow-down in the second loop, whatever it's doing.

Since I don't know what the second loop is doing, there could be lots of reasons, but one obvious candidate is that indirection has a cost, and all that de-referencing doesn't come for free. Changing the second loop to

my %HASH_DEREF = %$HASH_REF;
for(...){
    my $random_number = ...;
    1 if exists $HASH_DEREF{$random_number};
}
[download]

gives a running time nearly identical to the first.