Perl Threads implementation so far, seems very inadequate - it is good for primary school student exhibiting how parallel programming works.

That is a wrong conclusion drawn through a lack of understanding.

If you would care to describe your application in detail -- not just generics, but rather scales and reasons; with examples of data and processing requirements -- then you would (probably) get help with finding definitive, practical and efficient solutions to those requirements.

Your OP asks a simplistic question with an obvious answer: Yes, of course a multi-level hash can be constructed using multiple threads. It is simple and trivial:

#! perl -slw
use strict;
use threads;
use threads::shared;

sub displayHash {
    my( $ref, $pad ) = @_;
    return "\n" unless keys %{ $ref };
    my $buf = '';
    for my $key ( sort keys %{ $ref } ) {
        $buf .= "$pad" if length $buf;
        $buf .= "{$key}" . displayHash( $ref->{ $key }, $pad . '   ' )
+;
    }
    return $buf;
}

sub worker {
    my( $ref, $reps ) = @_;

    for( 1 .. $reps ) {
        my $copyRef = $ref;
        for my $step ( map chr( 97 + rand 26 ), 1 .. int( rand 10 ) ) 
+{
            if( exists $copyRef->{ $step } ) {
                $copyRef = $copyRef->{ $step };
            }
            else {
                lock %{ $copyRef };
                $copyRef = $copyRef->{ $step } = &share( {} );
            }
        }
    }
}

our $REPS //= 20;
our $THREADS //= 4;

my %HoHos : shared;

my @threads = map threads->create( \&worker, \%HoHos, $REPS ), 1 .. $T
+HREADS;

$_->join for @threads;

print displayHash( \%HoHos, '' );
__END__
C:\test>junk91 -REPS=7
{b}{l}{w}{g}
{d}{t}{k}{f}{g}{g}{g}{i}{j}
{f}{j}{v}
{g}{s}{g}{h}{g}
{i}{f}{j}{r}{m}{v}{u}{v}{b}
{k}{d}{f}{q}{k}
   {z}{t}{m}{h}{e}{i}
{m}{b}{l}
   {l}{u}{p}{t}{d}{h}
   {q}{k}{y}
{n}{f}{u}{v}{z}{z}{l}
{o}{f}
{p}{u}{s}{w}{n}{t}
{q}{h}
   {y}{k}{d}{l}{a}{n}{a}{i}
{r}{q}{t}{g}
{v}{o}{n}{x}{b}{g}{c}
{w}{a}
{y}{a}
   {d}{y}{j}
{z}{a}{p}{t}{i}{r}{t}
   {y}{i}{g}{c}{v}{z}{z}{k}
[download]

But, it is also probably not very helpful to your real application.