Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Bi-Directional Hash Lookup

by PerlingTheUK (Hermit)
on Oct 11, 2005 at 11:15 UTC ( [id://499110]=perlquestion: print w/replies, xml ) Need Help??

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

Dear Monks,
I have a database table with two column, either of them is unique. Now I need to lookup values both ways:
$a = $a{ $b }; $b = $b{ $a };
I am looking for a decent datastructure to do this that will be less heavyweight than a object but more efficient than storing the table in two separate hashes.

Cheers,
PerlingTheUK

Replies are listed 'Best First'.
Re: Bi-Directional Hash Lookup
by Skeeve (Parson) on Oct 11, 2005 at 11:42 UTC

    What's wrong with 2 hashes?

    Maybe a HoH is what you need?

    my %bidir= ( column1 => { a => 'b', }, column2 => { b => 'a', }, );
    So  $a= $bidir{'column2'}->{$b} will give you "the other" value.

    s$$([},&%#}/&/]+}%&{})*;#$&&s&&$^X.($'^"%]=\&(|?*{%.+=%;.#_}\&"^"-+%*).}%:##%}={~=~:.")&e&&s""`$''`"e
      The problem about HoH is that I regularly update the content. In which case both hashes need updating. I do not like the idea of doing that for both especially as I access and manipulate the data at several locations. I think I will pick a Class structure giving me a getA and a getB method. This will at least make sure that data of a HoH is consistent as long as my setColumn method is fine.

      Cheers,
      PerlingTheUK
        If you tie Skeeve's hash, you will have the chance to do sync when one of them updated...
Re: Bi-Directional Hash Lookup
by Moron (Curate) on Oct 11, 2005 at 11:38 UTC
    The only thing I can think of that is per se inefficient about multiple hashes is the need to have multiple references being passed around. The way I usually avoid this is simply a HoH:
    $hash{ column_name1 }{ value1 } = value2; $hash{ column_name2 }{ value2 } = value1;
    Update: Although, a more complex scenario might even require something like this to maintain a one-hash-for-all structure:
    $hash{ DATA }{ table1 }{ column_name1 }{ value1 } = value2; $hash{ DATA }{ table1 }{ column_name2 }{ value2 } = value1;

    -M

    Free your mind

Re: Bi-Directional Hash Lookup
by thor (Priest) on Oct 11, 2005 at 11:56 UTC
    What about something like this
    #assume that %hash is already initialized %hash = (%hash, reverse %hash);
    Of course, you are still storing everything twice, but in order to be able to lookup on either value, you'll need something like this.

    thor

    Feel the white light, the light within
    Be your own disciple, fan the sparks of will
    For all of us waiting, your kingdom will come

      I had thought of this too, but the OP claimed that each of the keys and the values are unique. He didn't exclude that any of the keys may also be a value, although it is definitely reasonable to doubt about this. I'm pointing this out just to let him/her know that this solution may fail in the case it is so:
      use Data::Dumper; my %hash=(foo => 'bar', bar => 'baz'); %hash=(%hash, reverse %hash); print Dumper \%hash;

      Incidentally I wouldn't have used your smart and elegant syntax -of which I may have thought, but but which didn't occur to me- and I would have done a clumsier

      @hash{values %hash} = keys %hash;
      instead.
        He didn't exclude that any of the keys may also be a value, although it is definitely reasonable to doubt about this.
        I took the OP to mean that each value would be unique in the hash. That is to say that for any key or value in the hash, there would not exist any other key or value that would have the same..erm...value.

        thor

        Feel the white light, the light within
        Be your own disciple, fan the sparks of will
        For all of us waiting, your kingdom will come

Re: Bi-Directional Hash Lookup
by blazar (Canon) on Oct 11, 2005 at 11:53 UTC
    What is the problem of keeping two separate hashes?
    my %hash=(a => 'foo', b => 'bar', c => 'baz'); my %reverse; @reverse{values %hash}=keys %hash; # if(f) values are unique, as you c +laim.
    If what bothers you is having "two" for what is "one" thing, then you're giving it up -or better: trading it- for the advantage of hash lookup.

    To re-gain the psychological feeling of unity you may make them into a single HoH with keys qw/direct reverse/ associated to the "direct" and "reverse" hashrefs.

Re: Bi-Directional Hash Lookup
by radiantmatrix (Parson) on Oct 11, 2005 at 17:22 UTC

    This sounds like a job for overload.

    ## untested "idea" code ## package TwoWayHash; use overload '%{}' => \&as_hash; sub new { my $self = shift; my $hashref = shift; my %struct = ( 'data' => $hashref ); bless \%struct, $self; } sub as_hash { my $self = shift; # this will only work for simple hashes, really my $temp = reverse $self->{data}; return $temp{shift}; }

    Which in turn might be used as:

    use TwoWayHash; my %a = get_results_from_query; # assume this populates %a; # then, when you need $b{$a}: { my $b = TwoWayHash->(\%a); print "I need ",$$b{'item'}; ## finds key where $a{key} eq 'item' }

    Just ideas, not tested, to get you thinking down this type of road. You could also do this with a function that implements the logic of as_hash(), and then merely call it like:

    print "I need", rv_lookup('item',\%a);
    <-radiant.matrix->
    A collection of thoughts and links from the minds of geeks
    The Code that can be seen is not the true Code
    "In any sufficiently large group of people, most are idiots" - Kaa's Law
Re: Bi-Directional Hash Lookup
by TedPride (Priest) on Oct 11, 2005 at 18:34 UTC
    This being Perl, you're not going to get much in the way of structure efficiency with or without hashes, and you haven't supplied us with some crucial information:

    1) How many records does the database table have?
    2) What's the average size of each field?
    3) What's the ratio of updates to searches?
    4) Do you need to support multiple simultaneous searches? If so, up to how many?
    5) What are your memory limits?

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://499110]
Approved by dorward
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others sharing their wisdom with the Monastery: (2)
As of 2024-04-19 21:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found