fast hash search

ddoc has asked for the wisdom of the Perl Monks concerning the following question:

I have a rather large hash as such:

%hash{'key1'}{'key2'}='string'

I need to find key2 when string eq $1 from a previous regex. I would like to avoid another foreach because this hash can have over 1000 key1's and it is already nested inside 4 foreach loops.

That said, any solution is welcome, even with the foreach loops.

I have experimented a bit with grep but it seems to only work on arrays. I also had an idea to print the hash into a long string and then regex or grep it but it never led anywhere.

Update: my hash is 1:1 and I use this structure extensively and need to do this lookup just once. Using the reverse function did exactly what I needed. Thanks all.

Comment on fast hash search Select or Download Code

Replies are listed 'Best First'.
Re: fast hash search by davidrw (Prior) on May 20, 2006 at 00:41 UTC
first, note that `%hash{'key1'}{'key2'}` should be `$hash{'key1'}{'key2'}` If you're not accessing the hash through it's key order of key1, key2, then you should probably re-hash it. not sure what you're looking for, but this will make a hash keyed on 'string' and has an arrayref of the key2's. (no clue if your string:key2 is 1:1 or 1:many) `my %strToKey2Hash; foreach my $href ( values %hash ){ while( my ($key2,$string) = each %$href ){ push @{$strToKey2Hash{$string}}, $key2; } }` [download]	[reply] [d/l] [select]
Re: fast hash search by GrandFather (Saint) on May 19, 2006 at 23:45 UTC
Provide some sample code and data (read I know what I mean. Why don't you? first). Do you mean that you want to find a key given a value? If that is the case generate a hash using the values as keys and the keys as values (invert the hash). DWIM is Perl's answer to Gödel	[reply]
Re: fast hash search by cdarke (Prior) on May 20, 2006 at 07:54 UTC
There is no 'easy' way to find a key from a value, one reason being that values need not be unique. I suggest you need to revisit your design ;-) Iterating through a hash is generally a bad idea, but if you must then you might like to look at the 'each' function (perldoc -f each), usually called in a while loop. The advantage is that you avoid the temporary list generated when you use keys or values with foreach. Another strategy you might consider if you have unique values is to reverse the hash(s) (perdoc -f reverse) making the keys into values, and values into keys.	[reply]
Re: fast hash search by ioannis (Abbot) on May 20, 2006 at 00:06 UTC
Here is solution, for there could be more then one value for key that matches $str in a HoH. `# The could be more then one value for key, # when you search for key $st, in a HoH. my $st = 'alamo'; my @values = map {$_->{$st}} grep {$_->{$st}} @{$h}{keys %$hash};` [download]	[reply] [d/l]
Re: fast hash search by John M. Dlugosz (Monsignor) on May 20, 2006 at 03:40 UTC
In general, either a brute-force search which uses a loop of some kind, whether foreach, while, map, grep, etc. that checks each one until you find it; or Create an index with the thing you are looking up as the hash key. In this case, loop over all the entries once, building another hash such that `$index{string}=key2`. Then reference that index as many times as needed, quickly. If the reverse mapping is not unique, than things are more difficult, but you get the idea.	[reply] [d/l]