Multi-level hashes without eval or modules

brian_d_foy on 2004-04-28T20:18:47

Last night a friend passed along a short problem to me. I need to take the keys for a multi-level hash, say $hash{a}{b}{c}{d}, and create that structure from just the list qw(a b c d), without using eval or a module, and it had to be really short, and it had to be delivered right away

After my initial solution, I came up with this concept (the argument checking and so on to be done by someone else). I use two hash references. One references the top level of the hash I want to create, and the other one is something like a cursor inside that hash so I can move around in it.

sub set_multi_level_hash
	{
	my( $hash, $tiers, $value ) = @_;

	my $work_hash = $hash;
	foreach my $tier ( @$tiers )
			{
			$work_hash->{ $tier } = {} unless exists $work_hash->{ $tier };
			$work_hash = $work_hash->{ $tier };
			}
			
	$work_hash = _get_multi_hash_last_level( $hash, $tiers );

	$work_hash->{ $tiers->[-1] } = $value;
	}

I do not really like that part where I have to back up a bit to figure out where to assign the value. I am sure there is a better way to do this, but I got the problem at 1 am and I needed to deliver it right away.

The _get_multi_hash_last_level routine uses the same trick as the earlier routine, but I do not have to remember anything about the original hash. I just need to drill-down to the right level.

sub _get_multi_hash_last_level
	{
	my( $hash, $tiers ) = @_;
			
	foreach my $tier ( @{$tiers}[0..$#$tiers-1] )
		{
		$hash = $hash->{ $tier };
		}
		
	$hash;
	}

That may look short, but it was longer before because I had made a mistake that required me to handle two special cases. The original version worked, but before I was able to become unconscious in bed, I came up with that version.

Somewhere else, somebody else created the code to read the multi-level hash under the same restrictions, I think, but I did not get to see that code. I wonder what it does to get to the right place.

---

make use of the indices of the $tiers

danboo on 2004-04-28T21:25:37

The only real innovation is using only one hash, and using the tier indices to avoid the backing up.

use strict;
use warnings;

use Data::Dumper;

my $hash = {};

set_multi_level_hash($hash, [qw/ a b c d /], 'potato');

print Dumper $hash;

sub set_multi_level_hash
      {
      my ( $hash, $tiers, $value ) = @_;

      for (0 .. $#$tiers)
            {
            $hash->{$tiers->[$_]} ||= ( $_ == $#$tiers ? $value : {} );
            $hash = $hash->{$tiers->[$_]};
            }
      }


Re:make use of the indices of the $tiers

danboo on 2004-04-28T21:44:36

Oops, to be able to change the value, I suppose the first line in the for loop should be split into:

$hash->{$tiers->[$_]} = {} unless exists $hash->{$tiers->[$_]};
$hash->{$tiers->[$_]} = $value if $_ == $#$tiers;


Re:make use of the indices of the $tiers

brian_d_foy on 2004-04-28T22:21:01

Yeah, I thought about something like that, but then I should go through 0..$#$tiers-1, and do the special case for the last value.

Oh well, too late now. It is out of my hands.

Thanks for the code :)

Re:make use of the indices of the $tiers

jhi on 2004-04-29T06:30:09

I think one needs to specify what happens in this case:

set_multi_level_hash($h, [qw(a b c)], 42);
set_multi_level_hash($h, [qw(a b)], 66);

Oops, we just nuked the first value and the whole "subhash".

In other words, is the level of multiness going to stay the same?

Personally, I would either create a class that guards against the multiness changing, or would make the data structure to be an array reference of hash references, keyed off in the array reference on the depth of $tiers (the latter can of course be wrapped into a class, too.)

Also, after this

set_multi_level_hash($h, [qw(a b c)], 42);

what should this return:

get_multi_level_hash($h, [qw(a b)]);

Are we supposed to get the "subhash", or not, or should we have two different functionalities, "get one value" and "get a subhash with potentially multiple values"?

Re:make use of the indices of the $tiers

brian_d_foy on 2004-04-29T06:52:38

What you are "supposed" to get depends on what your requirements are. In this case, you assign a different value to a hash key, you replace the value, just like you do if you had written it out as "$h->{a}{b} = 42".

I suppose you could create a class to limit operations, but then, you probably would have need ed a lot more time to deliver the code. One of the requirements was "right now". I didn't build in a lot of extra stuff to make variables not be variable.

There is no get_multi_level_hash function, so it shouldn't return anything. If you write one, you can decide what it should do. :)

Got a similar problem

BooK on 2004-05-04T12:01:35

I had to do someting similar to create a multilevel hash table that returns a list of "cached" things given a list of parameters that represent the hashing value.

The main problem was not creating the various anonymous hashes, but that the last item is not a {} but a []. The trick was to keep a reference to the previous step, to be able to go back and turn a newly created hash reference into an anonymous array.

# $thing is a hash reference
# @keys is the list of $thing attributes I'm using for the hashing algorithm
# $hashtable is a reference to the hash table itself
my $list = $hashtable;
my $last;
($last, $list) = ( $list, $list->{$thing->{$_}} ||= {} ) for @keys;
$list = $last->{$thing->{$keys[-1]}} = [] if ref $list eq 'HASH';
# and now $list points to the list of interesting items
# which was created (empty) if needed

Using $list, $last adds extra obfuscation points, but that wasn't intended, since those are fitting names.