Hashing

Hash sets and hash maps

• A hash table is a collection of key-value pairs. Each pair is an entry, and each storage location is a bucket.
• Hash sets / maps do not maintain order and do not hold duplicate keys (like a BST or TreeMap, but unordered).
• Average time complexity for insert, remove, and search is $O(1)$; get and put are $O(1)$ assuming the hash function distributes keys uniformly among the buckets. The worst case is $O(n)$.
• Keys must implement hashing and equality: hashcode() is used when inserting a key and equals() when retrieving one (in Python, __hash__ and __eq__).
• Collisions: a common resolution is chaining, turning each bucket into a linked list. The alternative is open addressing (probing for the next free slot).
• Resizing: when the table gets about half full its size is doubled, and every element must be rehashed into its correct new position. This makes insertion $O(1)$ amortized.

When to use

• Counting frequencies (for example counting names in a list).
• Checking membership or duplicates in $O(1)$.
• Looking up the complement of a value (Two Sum) while scanning once.
• Caches such as LRU, usually combined with a doubly linked list.

Hash maps in sliding window problems

• Track frequencies in the window; delete the key when its count reaches 0 so the map size reflects distinct elements.
• Operation order matters when keeping a match counter:
  • Adding: increment the frequency, then check whether it equals the target.
  • Removing: check whether it equals the target, then decrement the frequency.
• See the sliding window notes in Arrays and Strings.

Templates

• Hash Usage: using the built-in hash set and hash map (counting, membership).
• Hash Map Implementation: building a hash map from scratch with buckets, collision handling, and resizing.

Problems