CS136 Study Guide - List Of Dos Commands, Pigeonhole Principle, Hash Table
Document Summary
Dictionary/associative array: an abstract data type which holds a collection of (key, value) pairs, where each key appears at most once: this allows one to store a value in the associative array using a key as an index". The value can later be extracted if one knows the key it was stored under: typical operations are. Insert(k, v): add value v, associated to key k. Delete(k): remove item associated to key k. Search(k): return value associated to key k (if one exists: for simplicity, keys are usually assumed to be integers. (if not, we can always map the keys to integers. Direct addressing (array a of size m , store v at a[k]) O(1) (key tells us exactly where item will be stored) Question: what is the downside to direct addressing: space required is o(m ), even if n is very small, which is wasteful.
