Q3: How do Dictionaries and Sets achieve O(1) average lookup times?
Python dictionaries and sets are backed by Hash Tables. Key hashes are computed via hash(key). In Python 3.6+, dictionaries use a compact array layout (an index array + a dense entries array), preserving insertion order while maintaining $O(1)$ key lookup and deletion.
Key Takeaways
- Uses hash tables for $O(1)$ average lookups.
- Python 3.6+ dicts preserve insertion order while reducing memory by ~20-25%.
Knowledge Check
What is the average time complexity for searching an element in a Python Set?