menge-datenstruktur

Set

In short: A data structure that contains every element at most once — a second attempt to insert the same value is simply ignored, unlike a list, which allows duplicates.

In more detail: Sets are suitable for guaranteeing uniqueness (e.g. a list of already-taken usernames) or for quickly checking whether a value already occurs. Depending on the implementation, the order of elements is not guaranteed (HashSet), sorted (TreeSet), or matches the insertion order.

In Depth

The most important practical advantage of a set over a list shows up for the question “does element X already exist?”: for a list, in the worst case you have to go through EVERY element individually and compare it, to determine that. A hash-based set, by contrast, can answer this question almost instantly, regardless of how many elements it already contains — this makes sets the natural choice when you want to exclude duplicates or quickly check for presence:

seen_ids = new Set()
 
for id in incoming_requests:
    if seen_ids.contains(id):
        skip(id)   // duplicate, already processed
    else:
        seen_ids.add(id)
        process(id)

A set also supports the classic mathematical set operations you know from school:

• Union: all elements from both sets combined (each only once)
• Intersection: only the elements that occur in BOTH sets
• Difference: elements of one set that do NOT occur in the other

These operations are usually directly available via built-in methods, instead of rebuilding them yourself with loops — e.g. to find out which permissions two user groups share (intersection) or which one group has exclusively (difference).

Important to note: for a custom object type (e.g. your own Person class) to work correctly in a hash-based set, the language needs to know when two objects count as “equal” — in many languages, you have to define an equality and hash method for your own type yourself for this, otherwise two objects that are identical in content but different instances are wrongly treated as different.

See also: HashSet, TreeSet, Collections