There's no other way than a linear search, but if you're making these version-checking calls more than once, it's probably most efficient to create another hash, %latest, to map an application's name to its latest version:

my %apps = qw(
  gcc-3.3 1
  gcc-3.3.1 1
  gcc-3.3.2 1
  gzip-1.2.4a 1
  make-3.79.1 1
);

my %latest = ();

for(keys %apps) {
  my($program, $version) = split /-/, $_, 2;
  $latest{$program} = $version if
      not exists $latest{$program} or
      ($latest{$program} cmp $version) < 0;
}

print "make: $latest{make}\n";
print "gcc: $latest{gcc}\n";
[download]