my %hash; # hash of stored values
my $PRIME = some_large_prime(); # random or fixed, your choice
my $PRIME_HALF = int($PRIME/2); # or some other known value or function
...
my $i = $initial_index; # wherever you get this from
my $failed_tries = $PRIME;
while (defined($hash{$i}) and $failed_tries--) {
    my $offset = $hash{$i} % $PRIME;
    $offset = $PRIME_HALF if ($offset == 0);
    $i = ($i + ($hash{$i}) % $PRIME;
}

if ($failed_tries) {
    $hash{$i} = $value;
} else { 
    warn "Hash full\n";
}