coldfingertips,
I seriously question using numeric keys soley on the basis of sorting or the need to re-order them when they are deleted, but I think this will do what you want:

#!/usr/bin/perl -w
use strict;

my %hash = (1 => 'foo', 2 => 'bar', 3 => 'asdf', 4 => 'blah', 10 => 'w
+oah');
delete $hash{3};

FixHash(\%hash);
print "$_ : $hash{$_}\n" for sort { $a <=> $b } keys %hash;

sub FixHash {
    my $hashref = shift;
    my $index = 0;
    for my $key ( sort { $a <=> $b } keys %$hashref ) {
        $index++;
        next if $key == $index;
        $hash{$index} = delete $hash{$key};
    }
}
[download]

I would probably look at one of the modules for sorted hashes like Tie::IxHash and Tie::Hash::Sorted or use an array.

Cheers - L~R