liveBook · Manning

Key

As explained in Advanced Algorithms and Data Structures

A dictionary key is a value that identifies an associated entry in a dictionary.

A dictionary key is a value that identifies an associated entry. In a dictionary, each possible key appears at most once, and the key retrieves its value directly. section 4.3

Keys support several related data-structure roles:

  • Generalize array indices: an ordinary array uses positions from zero through size minus one as its keys, while a dictionary can draw keys from virtually any domain. section 4.3
  • Define ordering in a binary search tree: smaller keys belong in the left subtree and larger keys in the right subtree. section 3.3
  • Remain distinct from priority: a treap orders entries by key while using a separate priority to maintain heap behavior. section 3.2 section 3.3
  • Permit lookup by transformation into indices; with bounded key length, checking the resulting positions takes constant time. section 4.9.4

Email contacts

Store contacts as key-value pairs in an in-memory dictionary, using a contact identifier as the key. When a recipient is entered, check the dictionary before asking whether to save the contact; insert and remove keep the local collection synchronized. section 4.3

Abstract data structure: Associative array (aka dictionary)

API

 
class Dictionary {
  insert(key, value)
  remove(key) → value
  contains(key) → value
}

Contract with client

A dictionary permanently stores all the pairs added by the client(s). If a pair (K,V) was added to the dictionary (and not removed afterward), then contains(K) will return V.

The associative-array API makes the key’s operational role explicit through insert, remove, and contains. section 4.3

How Advanced Algorithms and Data Structures covers it

How deep it goes
Defines uniqueness and retrieval, then explains array indices, tree ordering, and bounded-length lookup complexity.
Examples
Uses array positions, product names in treaps, and contact identifiers in an email address book.
What you can do after
Apply keys via dictionary insertion, removal, containment checks, and direct value retrieval.
How it connects
Connects keys with dictionaries, associative arrays, binary search trees, heaps, priorities, and array indices.
Cover of Advanced Algorithms and Data Structures
liveBookmanning.com
Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Also explained in

Compare how 10 books explain key →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.