This is not a new problem. You must 'invert' your hash. A super search of this forum for 'invert hash' discovers several solutions. The book
Perl Cookbook has a 'recipe' on the subject. Your issue of printing the resulting hash in the correct order is covered in the FAQ.
perldoc -q "How do I sort a hash"