That you want your output "in the same order as the hash" is a not a good sign. Hashes are unordered. If you want a specific order, then you'll need to specify it each time you access the hash.

That said, here's what I think you want:

my %fruit_map;
@fruit_map{@apple_ids}  = ("apple")     x @apple_ids;
@fruit_map{@orange_ids} = ("orange")    x @orange_ids;
@fruit_map{@lemon_ids}  = ("lemon")     x @lemon_ids;

while (my($k,$v) = each %hash) {
   print "$fruit_map{$k}-$fruit_map{$v}\n";
}
[download]

%fruit_map is just a hash that maps the ID to the appropriate fruit given that you have a list of IDs that belong to known fruit. I've used hash-slice syntax and the x operator in list context to set the hash in groups.