Datastructure to store bidirectional relationship

Question

I have googled and couldnt find any DS to store and read bi directional data in O(1) time. E.g. books and authors. With the name of book, authors has to be found. With the name of author, books has to be found.

How in DB, these relations like Join tables are stored?

thanks in advance.

Answer 1

The idea is a combination of the following:

• A hash map of the first element to the second element (or a list of them)
• A hash map of the second element to the first element (or a list of them)

Hash maps give expected O(1) lookup.

I don't believe databases typically use hash maps though, more typically b-trees as far as I know (giving O(log n) performance).

Answer 2

Expanding on Dukeling's answer, I believe Google has an implementation called HashBiMap: http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/HashBiMap.html