If you really need a hash, you could always keep the order information in arrays in the hash like this:

$VAR1 = {
    'order' => [ 'Foo' ],
    'data' => {
        'Foo' => {
            'order' => [ 'D', 'A', 'E', 'B', 'C' ],
            'data' => {
                'D' => {
                    'order' => [ '1' ],
                    'data' => {
                        '1' => {}
                    },
                'A' => {},
                'E' => {
                    'order' => [ '1', '2', '3', '4' ],
                    'data' => {
                        '1' => {},
                        '2' => {},
                        '3' => {},
                        '4' => {}
                    }
                }
...etc.
[download]

Of course, maintaining that structure could be a chore. Java has what you're looking for - a hash that maintains order - it's called a LinkedHashMap. Basically it's a hash with a linked list running through it. <handwaving>I leave the Perl implementation as an exercise for the reader...</handwaving>

---

Update

Ok, I feel like an idiot. Ignore the Java ramblings - IxHash is the same as a LinkedHashMap. The data structure works, however (even if it is a pain).