Hash sets: fast membership without an order promise

Last updated: 5 Oct 20269 min read

tutorial

A hash set stores unique keys and answers membership queries in expected O(1) time. It uses hashing and equality like a hash map but does not attach an application value to each key. A set does not promise a stable sorted order, so a caller that needs a repeatable display order should sort the final keys or track order separately. Deduplication needs a deliberate identity key: two events with the same shipment ID may represent distinct scans, while two copies of the same event ID are duplicates. Choosing the wrong key can silently erase valid data.

Operational case

A scanner exports event IDs E-47, E-52, E-47, and E-61. The second E-47 is a repeated upload, so the service counts three unique events. It still keeps the raw log for audit and uses a set only for the deduplicated view. Sorting the set gives a repeatable report, but that O(n log n) presentation step is separate from expected constant-time membership. If the IDs belonged to different depots, the key should include depot scope just as a hash map does.

Working Python program

raw_event_ids = ["E-47", "E-52", "E-47", "E-61"]
unique_event_ids = set(raw_event_ids)
print(len(unique_event_ids))
print(sorted(unique_event_ids))
print("E-52" in unique_event_ids)

Output

3
['E-47', 'E-52', 'E-61']
True

Time, space, and tradeoff

Building the set from n IDs takes expected O(n) time and O(u) space for u unique IDs. Sorting u IDs costs O(u log u) time and O(u) output storage. Worst-case collision behavior is not a guarantee of constant time. When memory is tight and the input is already sorted, adjacent duplicate removal may avoid the hash table; when the raw order matters, preserve it separately rather than expecting the set to remember it.

Common Mistakes

Do not assume set iteration is a stable report order.
Do not deduplicate by a field that is not unique for the intended event.
Do not discard the original log when audit requires raw records.

Connected lessons

data structures

hash-tables