Class7.md

Class 7: Maps & Hash Tables

Topics

• Abstract data types: map (dictionary, associative array)
• Concrete data structures: hash table
• Hash functions, collision resolution, load factor, dynamic resizing

Resources

• Review Make School's hash table slides
• Watch Make School's hash table video lecture
• Read Vaidehi Joshi's articles on hash tables and hash functions with beautiful drawings and excellent examples
• Watch HackerRank's hash table video
• Watch Harvard's old hash table video and new hash table video
• Play with VisuAlgo's interactive hash table visualization

Challenges

• Add new features to improve HashTable class using hash table starter code:
  • Add size property that tracks the number of hash table entries in constant time
  • Implement load_factor - return the load factor, the ratio of number of entries to buckets
  • Implement _resize - perform dynamic resizing when load_factor exceeds 0.75 after an insertion (set is called with a new key) and rehash all key-value entries
  • Run python hashtable.py to test HashTable class instance methods on a small example
  • Run pytest hashtable_test.py to run the hash table unit tests and fix any failures
• Annotate methods with complexity analysis of running time and space (memory)

Stretch Challenges

• Implement an alternative hash table collision resolution strategy instead of separate chaining (popular variants include linear probing, quadratic probing, and double hashing)
• Write additional test cases to expand the hash table unit tests to ensure your collision resolution strategy is robust