TMTOWTDI. The core module List::Util can be useful here:

#! perl
use strict;
use warnings;
use List::Util qw( first min );

my %h =
(
    17 => 2,
    23 => 5,
    42 => 1,
     7 => 3,
    35 => 4,
);

my $min_key = min keys %h;

printf "The smallest key   is %d, and its associated value is %2d\n",
        $min_key, $h{$min_key};

my $min_val = min values %h;

printf "The smallest value is %d, and its associated key   is %2d\n",
        $min_val, first { $h{$_} == $min_val } keys %h;
[download]

Output:

22:21 >perl 876_SoPW.pl
The smallest key   is 7, and its associated value is  3
The smallest value is 1, and its associated key   is 42

22:21 >
[download]

Hope that helps,