Abstract
A Set is an Abstract Data Type (ADT) that stores unique elements without duplicates, modeling the mathematical concept of Set Theory. It is designed for high-speed membership testing (
contains), uniqueness enforcement, and collection operations like union and intersection.
- Category: Unique Associative ADT
- Core Requirement: Duplicate insertions are rejected or ignored.
- Primary Benchmark: Fast or membership verification.
Core Architectural Properties
- Uniqueness Invariant: Duplicate elements are prohibited; adding an existing value produces no change.
- Unordered vs. Ordered: Base sets do not guarantee insertion order, though specialized variants (e.g.,
TreeSet) maintain sorted ordering. - Membership Optimization: Optimized to determine whether an element exists far faster than linear searches.
Common Operations & Complexity
| Operation | Description | Hash Set Complexity | Tree Set Complexity |
|---|---|---|---|
add(x) | Inserts element x into the set. | avg | |
remove(x) | Deletes element x from the set. | avg | |
contains(x) | Checks if x exists in the set. | avg | |
size() | Returns total active element count. | ||
clear() | Erases all elements from the set. | ||
union(B) | Merges elements from set and set . | ||
intersection(B) | Extracts elements shared by both sets. | ||
difference(B) | Extracts elements in that are not in . |
Set Implementation Classifications
- Hash Set: Backed by a Hash Table. Delivers average-case operations; order is arbitrary.
- Tree Set: Backed by a self-balancing search tree (e.g., Red-Black Tree). Maintains elements in sorted order with bounds.
- Linked Hash Set: Backed by a hash table with an embedded doubly linked list to preserve insertion order.
- Multiset (Bag): Relaxes uniqueness rules to permit duplicate entries while retaining set operations.