Hash Tables

Hash tables are the most practically useful data structure in interviews — they convert O(n) linear scans into O(1) lookups. The core mental model: 'instead of searching, remember.' Any time you find yourself in a nested loop looking for a complement, match, or previously seen value, a hash map converts it to one pass. The key patterns are: frequency counting, complement lookup (two-sum), set membership testing, and prefix-sum with map. Understanding Hash Tables A hash table maps keys to values using a hash function. It provides average O(1) lookups, insertions, and deletions — making it the go-to data structure for optimization. How it works: Hash function converts key → integer index Store value at that index in an array (bucket) Handle collisions: chaining (linked list per bucket) or open addressing (probe for next empty) Why hash tables are everywhere in interviews: They convert O(n) search to O(1) lookup "Have we seen this before?" → HashSet "How many times?" → HashMap with count "Find complement" → Store what you need, check if exists Key patterns: Frequency counting: count occurrences of each element Two Sum pattern: store complement → index mapping Group by key: anagrams (sorted string as key), isomorphic strings Sliding window hash: substring problems Hash Tables Hash tables provide O(1) average-case lookup, insertion, and deletion. The most frequently used data structure in interviews. Implementation Frequency Counting Pattern Two Sum (THE classic) Key Problems #1 Two Sum, #49 Group Anagrams, #347 Top K Frequent #128 Longest Consecutive Sequence, #146 LRU Cache Interview Tip "When I need O(1) lookup or need to count frequencies, hash map is my first choice. The trade-off is O(n) space." Java Implementation