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};
}
gives a running time nearly identical to the first.