EMZETT.HashSet (Hash-Based Set)
In short: A set that internally uses a hash table, to insert, search, and remove elements extremely fast (ideally in nearly constant time).
In more detail: Every element is mapped to a memory location via a hash function — this eliminates the need to search through the entire structure, as would be necessary for a list. The price for this: the order of elements when iterating isn’t predictable and matches neither insertion order nor a sorted order — for that, a TreeSet would be the suitable choice.
In Depth
The basic mechanism: a hash function converts every element into a number (the “hash value”), which serves as an index into an internal array. To check whether an element already exists, a HashSet doesn’t have to compare all existing elements in sequence like a list — it directly computes the hash value of the sought element and immediately looks at the matching spot:
contains("Anna")?
-> compute hash("Anna") -> e.g. 47
-> look directly at position 47 in the internal array
-> (instead of going through all elements from 1 to n)This direct addressing is the reason for the nearly constant access time (O(1) on average) — regardless of whether the set contains 10 or 10 million elements. For comparison: a linear search in an unsorted list needs O(n), so it becomes proportionally slower as the amount of data grows.
An important detail: two different elements can produce the same hash value (“hash collision”) — this is mathematically unavoidable with a limited value range. A good implementation catches this automatically (e.g. by managing several elements in a small internal list at the same position), but for very many collisions, performance degrades towards O(n) — which is why a good, evenly distributing hash function for the contained objects is crucial.
The price for this speed: no predictable order. Because the position of an element depends on the hash value, not the insertion order, the iteration order can even differ between two program runs. Anyone needing a consistent insertion order reaches for LinkedHashMap or the corresponding set variant; anyone needing a sorted order reaches for TreeSet — though there, sorting costs O(log n) instead of O(1) per operation.
See also: Set, TreeSet, LinkedHashMap