Dictionary data structures also known as associative array

Binary search trees - interview

hash tables - wildly used

Dictionaries maintain a set of key value pairs

e.g. 

words and definitions

symbol table of a compiler

Support the following operations:

insert (key)

delete (key)

lookup (key)

Usually the number of keys in your set is mush smaller than the number of possible keys.

e.g. keys are IP addresses.

Ideally, to maintain at most n keys, we will use space “close” to n. (m=1.1m)

# Binary Search Tree 

A BST is a binary tree(i.e. every node has at most 2 children) and each node is associated with a key.

Furthermore, the following holds:

the left subtree of x, key(y)<=key(x)

the right subtree of x, key(y)<=key(x)

For BSTs, the runtime of operations is at most the tree depth. But the tree can have depth n (i.e. only taking one side).

self-balance BSTs. e.g red-block tree, keep the depth O(logN) *not need to know the details

a B tree is not a BST

# Hash Table

Hash table maintain a table with m > n “slots” and a hash function j:keys —>slots

when we want to insert key x, we try to place it in slot h(x). 

If there are keys x,x’ in our set and h(x)=h(x’), this is called a collision. 

There are many ways to deal with them

option 1 - Chaining each slot contains a linked list staring all keys hashing to the slot

Pro:

insertions always take constant time

con store more than there are slots

Con:

linked lists require storing pointers which takes space

poor memory locality

merry allocation/deallocation

Runtime: 

insert are constant time

lookup, delete on key x takes time up to the size of slot h(x)

for each slot, the expected size of the slot is m/n = O(1)

however, with high probability, there will be slots storing ϴ(logN/loglogN) keys —> better than logN(BST)

option 2 - Two-Choice Hashing + Chaining. Same as above, except each key is mapped to two slots and placed i the least loaded slot.

Runtime:

ϴ(logN/loglogN) becomes loglogN *nearly constant < 6

option 3 - Linear Probing *wildly used

If slot h(x) is occupied, try slot h(x)+1, then try h(x)+2 and so forth until an empty slot is found.

Pro:

Great memory locality

simple to implement

Con:

suffer form “clustering”

Runtime:

All operations run in expected constant time

With high probability no operation will take more than O(logN)time —> much better than BST

option 4 - Cuckoo Hushing 

Pro:

All lookups take at most 2 time steps.

A worry:

inserts may the a long time

Rumtime:

with high probability all inserts succeed and more take more than O(logN) time