Definition
Generating fixed-sized output from an input variable size using mathematical functions known as hash functions
Purpose
Creates a data structure that can store and search for values in constant time, O(1)
Components
- Key
- Hash function
- Hash table
Collisions
- open addressing
- all elements are stored in hash table
- hash table must be bigger than # of keys
- separate chaining
- in the hash table, values are stored as linked lists, called a chain
- Each node in the chain contains information about the key and value
- Searching finds the matching hash(key) and loops the chain for the matching key to get the value
- expandable