It's really the regular hash counting problem:

sub somefunction {
    my ($hash, $key) = @_;
    my %outputhash;
    $outputhash{$_->{$key}}++ for values %$hash;
    %outputhash;
}
[download]

By not checking for truth of $_->{$key}, you get also get a count of missing entries in $outputhash{""} and you don't miss Department Zero if it's spelled 0.