I made several attempts at returning a sorted hash:

#!/usr/bin/perl

use strict;
use Data::Dumper;

my %unsorted = ( key3 => 'bread',
                 key2 => 'apples',
                 key1 => 'steak',
                 key4 => 'butter',
                 key5 => 'oranges',
                 key6 => 'cake',
                );
my @keys_by_value = sort { $unsorted{$a} cmp $unsorted{$b} } keys %uns
+orted;

print "Keys by value: @keys_by_value\n";
print "Sorted values: @unsorted{ @keys_by_value }\n";

my @sorted_keys_values = map { $_, $unsorted{$_} }  sort { $unsorted{$
+a} cmp $unsorted{$b} } keys %unsorted;

print "Keys/values by value: @sorted_keys_values\n";

#my $foo = { @sorted_keys_values };
my $as_hash = { map { $_, $unsorted{$_} }  sort { $unsorted{$a} cmp $u
+nsorted{$b} } keys %unsorted };

print "Data Dumper:\n";
print Data::Dumper->Dump( [$as_hash],['as_hash'] );
[download]

and though it's fairly easy to get the keys and values sorted by value, as soon as perl converts the data back into a hash structure, it goes back to its natural (unordered) state:

Keys by value: key2 key3 key4 key6 key5 key1
Sorted values: apples bread butter cake oranges steak
Keys/values by value: key2 apples key3 bread key4 butter key6 cake key
+5 oranges key1 steak
Data Dumper:
$as_hash = {
             'key1' => 'steak',
             'key2' => 'apples',
             'key3' => 'bread',
             'key4' => 'butter',
             'key5' => 'oranges',
             'key6' => 'cake'
           };
[download]

So I was unable to create a sorted hash without resorting (as IlyaM and dws mentioned) to 'tie'.

Rather than roll my own tie-based solution, I went to CPAN: Tie::SortHash or Tie::IxHash may do what you need.

Impossible Robot