Instead of a hash, you may want to use a data structure that maintains an order. An alist (a concept borrowed from lisp) seems suitable...

  my @alist = (
   [1 => 'cat'],
   [3 => 'mouse'],
   [5 => 'whale'],
   );

  alistinsert(\@alist, 2, 'porcupine');
  my $pair = alistatleast(\@alist, 4);
  # $pair now contains [5, 'whale']
  print "The first element of the alist with a key of at least 4 is ($
+$pair[0], $$pair[1])\n";


  sub alistatleast {
    my ($alist, $minval) = @_;
    for (@$alist) {
       return $_ if $$_[0] >= $minval;
    }
  }
  sub alistinsert {
    my ($alist, $car, $cdr) = @_;
    my $posn = 0;
    for (@$alist) { ++$posn if $$_[0] < $car }
    splice @$alist, $posn, 0, [$car, $cdr];
  }
[download]

This saves you from doing a sort for every lookup, which will help performance if you have a lot of elements, taking a worst-case lookup down to O(n) time (from at least O(n log n) time if not more with the sort). It is possible to do better, by making the search binary instead of linear, which should get you down to O(log n) time I think. If your lookups have to be faster than that, you have to take drasting measures that will cost in other areas. e.g., you could have all possible keys be defined, or all keys that are multiples of some value, but if they don't have their own value give them a reference to the next one up with a real value. That gets you down to O(1) time for lookups, but it costs elsewise, by raising storage requirements and greatly complicating your code, among other things.

$;=sub{$/};@;=map{my($a,$b)=($_,$;);$;=sub{$a.$b->()}}
split//,".rekcah lreP rehtona tsuJ";$\=$ ;->();print$/
[download]