What is an appropriate data structure for a two-way name ↔ id relation?

I have a list of student names and their id. Sometimes I need to search name using id, sometimes I need to search id using name.

• If using array[id] = name, then it is quick to find a name using an id but slow to find the id using a name.
• If using hash{name} = id, then it is quick to find the id using a name but slow to find the name from an id.

What is the best data structure to represent student a name ↔ id relation? Note: the student name is a string while id is a sequential intege开发者_如何转开发r from 1 to the total number of these students.

Thanks.

---

If you're trying to do this without using an actual database, then you'll want to have two indexes. There are several ways of doing this, and you haven't really given enough info on what you're using this for, but here's something that will work well for many cases:

# Store student records sequentially, in any convenient order
my @student =
  ( { id=27,  name => 'Alice Amber', class = 'X' }
  , { id=2,   name => 'Bob Brown',   class = 'y' }
  , ...
  , { id=104, name => 'Zacharia Zebra', class = 'x' }
  );

# build index by id
my @student_by_id;
$student_by_id[$student[$_]{id}] = $student[$_] for 0..$#student;

# build index by name
my %student_by_name;
$student_by_name{$student[$_]{name}} = $student[$_] for 0..$#student;

What that gives you is a single copy of the student records, stored in @student in arbitrary order, and two indexes called @student_by_id and %student_by_name. Because the indexes store references into the student records, any change made to a record through either index will be visible from the other. The only hitches come about when you need to change either a student's name or id number, as this will require updating the affected index.

---

You could just combine both "fast" approaches. Use an array to lookup id -> name, and a hash to go from name -> id.

By "database," I assume you're just talking about some data structure (like an array or hash) and not a relational database (like MySQL).

---

I often create hashes that contain a record of information and different index hashes to locate them.

my $record 
    = { name          => 'James'
      , rank          => 'Captain'
      , serial_number => '007'
      };

foreach my $field ( qw<name rank serial_number> ) { 
    my $ref = \$lookup{ $field }{ $record->{ $field } };
    if ( ref( $$ref ) eq 'ARRAY' || !$lookup{meta}{$field}{is_unique} ) { 
        push @$ref, $record;
    }
    else { 
        $$ref = $record;
    }
}

That's the guts, though I'd probably encapsulate the record and the lookup mechanism.

---

One way could be to use both of these implementations. Use array when you need name from id and use hash when you need id from name. Not sure if it's the best way though.

---

Use both an array and a hash. Your question is a special case of this question.

In Perl, you can use the tie mechanism to make a class that looks like a hash with an additional method for look up by id, but where additions and deletions maintain both a hash and an array behind the scenes.

Tie::Hash::TwoWay provides a dual-lookup data structure with a hash both ways. It would probably be suitable for your purpose (there isn't much to be gained by storing student ids in an array except fast enumeration in student id order), and if not it can serve as inspiration.