#hashing

3 post(s)

Bloom Filters:Maybe-Yes, Definitely-No, and Why False Positives Are the Point

A Bloom filter is a bit array plus k hashes. It can say definitely not in the set, or maybe yes. False positives are the trade for tiny memory — never a false negative.

Data Structures

Sets:Uniqueness Without Scanning the List

The set ADT is unique membership. HashSet delivers it with a hash table; List.contains is a scan. When TreeSet belongs instead, and what you lose (order).

Data Structures

Hash Tables:Buckets, Collisions, and When `HashMap` Lies About O(1)

How hashing maps a key to a bucket, what chaining and open addressing do with collisions, and why HashMap is expected O(1) — not a law of physics.