Set
- In Turkish
- küme
In short
A Set is a collection that stores each distinct value at most once and can check whether a value is present very quickly, usually in constant time.
What is a set data structure?
A Set is a collection of distinct values: each value appears at most once, and adding a value that is already present changes nothing. Unlike an array or a list, a Set is about membership rather than position, so the main question it answers is whether a given value is in it. The idea is borrowed from mathematics, where a Set is a collection of distinct objects with no particular order.
Most Set implementations are built on a hash table. Adding a value hashes it to pick a bucket, and checking membership hashes it again and looks only in that bucket, so add, remove, and contains all take O(1) time on average, instead of the O(n) scan a list needs. Tree-based versions, such as Java's TreeSet, keep their values in sorted order inside a balanced tree, at O(log n) per operation. Sets also support the classic mathematical operations: union (values in either one), intersection (values in both), and difference (values in the first but not the second).
A guest list at a door is a good picture: the host only cares whether a name is on the list, and writing a name twice doesn't let that guest in twice. Sets are used to remove duplicates, to track visited nodes in graph searches such as BFS and DFS, to check tags and permissions quickly, and to compare two groups, for example to find users who created an account but never logged in. JavaScript's Set and Java's HashSet are typical built-in versions, and [...new Set(items)] is the usual JavaScript idiom for removing duplicates from an array.
A Set is often compared with a list and with a map. A list keeps items in order and allows duplicates, while a hash-based Set rejects duplicates and, in many languages, promises no particular order, although JavaScript's Set keeps insertion order. A map, also called a dictionary or hash table, stores a value for each key, while a Set stores only the keys, which is exactly how many languages implement one internally. Membership also depends on how the language compares values: JavaScript compares objects by identity, so two separate arrays holding [1, 2] count as two different members.
Key takeaways
- A set stores each distinct value only once, so duplicates are ignored.
- Hash-based sets add, remove, and check membership in O(1) time on average.
- Tree-based sets, such as Java's
TreeSet, keep values sorted at O(log n) per operation. - Sets support union, intersection, and difference.
- Python's
set, JavaScript'sSet, and Java'sHashSetare common built-in implementations.
Example
tags = ["python", "web", "python", "api", "web"]
unique = set(tags) # duplicates disappear
print(len(unique)) # 3
print("api" in unique) # True, in O(1) on average instead of scanning a list
signed_up = {"ana", "ben", "cy", "dee"}
logged_in = {"ben", "dee", "eve"}
print(signed_up & logged_in) # intersection: ben and dee
print(signed_up | logged_in) # union: all five names
print(signed_up - logged_in) # difference: ana and cy never logged inReaders ask
What is the difference between a set and a list?
A list keeps items in order and allows duplicates, and checking whether it contains a value takes O(n). A hash-based set stores each value once, usually makes no ordering promise, and checks membership in O(1) on average.
Are sets ordered?
It depends on the language and implementation. Hash-based sets such as Python's set make no ordering guarantee, JavaScript's Set iterates in insertion order, and tree-based sets such as Java's TreeSet keep values sorted.
How do I remove duplicates from an array in JavaScript?
Pass the array to a Set and spread it back into an array: [...new Set(items)]. This keeps the first occurrence of each value and runs in O(n) time.
See also
- Hash TableData Structures, p. 18A hash table is a data structure that stores key-value pairs and uses a hash function to find the value for any key in constant time on average.
- ArrayProgramming Fundamentals, p. 3An array is an ordered collection of values stored under one name, where each item is accessed by its numeric position, called an index, usually starting at 0.
- Bloom FilterData Structures, p. 7A Bloom filter is a compact probabilistic data structure that tells you an item is definitely not in a set or probably is, while using very little memory.
- Balanced TreeData Structures, p. 4A balanced tree is a tree that keeps its height close to log n by rebalancing after changes, so search, insert, and delete stay O(log n) even in the worst case.
- HashingSecurity, p. 14Hashing is the process of turning any input into a fixed-length value with a one-way function, used to verify data integrity and store passwords safely.
- Big O NotationProgramming Fundamentals, p. 6Big O notation describes how an algorithm's running time or memory use grows as its input gets larger, focusing on the growth rate rather than exact speed.
Spotted a mistake or something missing on this page?Suggest an edit