Maps and Sets Study Guide

Definitions and Variations

Definitions

dictionary - data structure in which values are mapped to keys, or act as their own keys.

dictionary problem - a find/insert/delete lookup problem in which you learn nothing if your search fails

map - mathematical analog term for dictionary, like a function (one input gives one output)

sorted map - data structure storing keys in a sorted order to provide data in order

hash table - a fast, unordered lookup table that works by turning an object (key or value) into a unique slot in an array via a hashing function

hash code - maps keys to integers

compression function - maps integers to a set of slots 0..N-1

bucket array - array storing the data of the hash table

hash function - a function h that maps keys k to an integer between 0 and N-1, denoted h(k)

immutability - a property required of keys

collisions - when two unique/distinct objects have the same output of the has function $ h(k_i) = h(k_j), i \neq j $

chaining - technique to deal with collisions

exact search - lookups tell you nothing about nearby data

inexact search - (timestamps example) can use sorting to get context info, less than, greater than, subset, etc.

maxima sets - storing (x,y) points used to model a cost/performance tradeoff. (a,b) dominates (c,d) if a <= c and b >= d. (a,b) is maximum pair if not dominated by any other pairs.

skip lists - data structure for storing data in sorted order, high probability of O(log N) access, simpler to implement relative to balanced search trees

• motivated by inefficiency of sorted lists
• efficient search/update compromise
• randomized data structure gives O(log N) with high expectation, randomizing DS so keys don't have to be randomized

height of skip list - number of linked lists to maintain

pseudo-random number generators - generate random-like numbers

start position of skip list - left-most node of top-most sparsest list

frozen set - an immutable set (Python type)

set - collection of related entities that does not allow duplicates, allows membership tests

multiset - set-like container allowing duplicates (counting map)

multimap - associates keys to values, but allows one key mapping to multiple values

template method pattern - virtual or unimplemented methods in parent class that are extended by children or by algorithms/functionality

Variations

Maps:

• Sorted Map
  • Tree-based
  • Array-based
  • Skip list
• Unsorted Map
  • Hash table based
  • Array based

Sets:

• Sorted sets
  • Tree implementation
  • Skip list implementation
  • Array implementation
• Unsorted sets
  • Hash table implementation
  • Array implementation

(NOTE: While the array implementations are inefficient for larger maps, for a small map like in a B-Tree, O(N) insertion is not a big deal if in return you get O(log N) or O(1) lookup and/or if you have a map with a max of 4 items.)

Skip lists

Hash tables

• See Hash Tables Study Guide

ADTs and Interfaces

Map ADT

Map ADT:

• get
• set
• delete

contains

• size
• empty
• iterator

Utilities:

• key iterator/key set
• value iterator/value set
• clear
• equality checks

Sorted Map ADT:

• find min
• find max
• find less than/lte
• find greater than/gte
• find range
• iterator
• reversed

Hash Table ADT

Hash table ADT:

• get
• set
• delete
• resize
• hash function: ak+b mod p mod N

Skip Lists

Skip list interface:

• Same as map
• get
• set
• delete
• contains

Set ADT

Set ADT has 5 essential methods:

• add
• remove
• contains
• size
• empty

From these 5, others can be extended:

• pop
• equals/not equals
• lt/lte
• gt/gte
• union of sets
• intersection of sets
• symmetric difference
• not operator