HashMap

For “HashMap”, begin by asking which relationship must be preserved: presence, frequency, an index, or a group. Use a set for membership and a map when a value must carry a count, first index, latest index, or accumulated result. State the streaming invariant: after processing position i, the structure summarizes exactly the prefix through i, which lets you test a complement or update a count without rescanning. Do not claim hashing makes every task O(1): operations are expected O(1) with a good hash and resizing, while adversarial collisions can be worse. Be deliberate about mutating counts and deleting zero counts. Test repeated values, negative numbers, empty input, large keys, and strings requiring normalization. Space is O(number of distinct keys), and a single pass is expected O(n).