A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Magical Lookups

One of my favorite go-to optimization techniques is to ask myself, “If I could magically find a desired piece of information in O(1) time, can I make my algorithm faster?” If the answer to this is yes, I then use a data structure (often a hash table) to make that magic happen. I call this technique “magical lookups.”

Let me clarify this technique with an example.

Magically Looking Up Authors

Let’s say we’re writing library software and we have data about books and their authors contained in two separate arrays.

Specifically, the array of authors looks like this:

authors = [
  {"author_id" => 1, "name" => "Virginia Woolf"},
  {"author_id" => 2, "name" => "Leo Tolstoy"},
  {"author_id" => 3, "name" => "Dr. Seuss" ...