A set is a data structure that does not allow duplicate elements; it only stores unique values. A set in mathematics represents a group of unordered and unique elements, and it has wide applications in computer science.
Basic Concepts of Sets
- Uniqueness: Elements in a set are unique and do not allow duplicates
- Unordered: Elements in a set have no specific order
- Determinacy: An element either belongs to the set or does not; there is no ambiguous state
The Set Object in JavaScript
ES6 introduced the built-in Set object, which provides basic set functionality:
const set = new Set();
// Add elements
set.add(1);
set.add(2);
set.add(3);
set.add(2); // Duplicate elements are ignored
console.log(set); // Set(3) {1, 2, 3}
// Check if an element exists
console.log(set.has(2)); // true
console.log(set.has(4)); // false
// Delete an element
set.delete(2);
console.log(set); // Set(2) {1, 3}
// Clear the set
set.clear();
console.log(set.size); // 0
Common Methods of Set
| Method | Description |
|---|---|
add(value) | Add a value to the set |
delete(value) | Delete the specified value from the set |
has(value) | Check if the set contains the specified value |
clear() | Clear the set |
size | Return the number of elements in the set |
Traversal Methods of Set
const set = new Set([1, 2, 3]);
// forEach traversal
set.forEach((value) => {
console.log(value);
});
// Convert to array
const arr = [...set]; // [1, 2, 3]
const arr2 = Array.from(set); // [1, 2, 3]
// for...of loop
for (const value of set) {
console.log(value);
}
Manually Implementing the Set Data Structure
Although JavaScript provides the built-in Set object, understanding its underlying implementation principles is still important.
Array-Based Implementation
class MySet {
constructor() {
this.items = [];
}
// Add element
add(value) {
if (!this.has(value)) {
this.items.push(value);
return true;
}
return false;
}
// Delete element
delete(value) {
const index = this.items.indexOf(value);
if (index !== -1) {
this.items.splice(index, 1);
return true;
}
return false;
}
// Check if element exists
has(value) {
return this.items.includes(value);
}
// Clear the set
clear() {
this.items = [];
}
// Get set size
get size() {
return this.items.length;
}
// Get all values
values() {
return [...this.items];
}
// Union
union(otherSet) {
const unionSet = new MySet();
this.values().forEach(value => unionSet.add(value));
otherSet.values().forEach(value => unionSet.add(value));
return unionSet;
}
// Intersection
intersection(otherSet) {
const intersectionSet = new MySet();
const values = this.values();
for (const value of values) {
if (otherSet.has(value)) {
intersectionSet.add(value);
}
}
return intersectionSet;
}
// Difference
difference(otherSet) {
const differenceSet = new MySet();
this.values().forEach(value => {
if (!otherSet.has(value)) {
differenceSet.add(value);
}
});
return differenceSet;
}
// Subset check
isSubsetOf(otherSet) {
if (this.size > otherSet.size) return false;
let isSubset = true;
this.values().every(value => {
if (!otherSet.has(value)) {
isSubset = false;
return false;
}
return true;
});
return isSubset;
}
}
// Usage example
const mySet = new MySet();
mySet.add(1);
mySet.add(2);
mySet.add(1); // Duplicate, ignored
console.log(mySet.values()); // [1, 2]
console.log(mySet.has(2)); // true
mySet.delete(1);
console.log(mySet.values()); // [2]
Object-Based Implementation
class MySetObject {
constructor() {
this.items = {};
}
add(value) {
if (!this.has(value)) {
this.items[value] = value;
return true;
}
return false;
}
delete(value) {
if (this.has(value)) {
delete this.items[value];
return true;
}
return false;
}
has(value) {
return this.items.hasOwnProperty(value);
}
clear() {
this.items = {};
}
get size() {
return Object.keys(this.items).length;
}
values() {
return Object.values(this.items);
}
// Union, intersection, difference, isSubsetOf methods similar to above
// ...
}
// Note: Object keys are converted to strings, so not suitable for non-string values
Map-Based Implementation
class MySetMap {
constructor() {
this.items = new Map();
}
add(value) {
if (!this.has(value)) {
this.items.set(value, value);
return true;
}
return false;
}
delete(value) {
return this.items.delete(value);
}
has(value) {
return this.items.has(value);
}
clear() {
this.items.clear();
}
get size() {
return this.items.size;
}
values() {
return [...this.items.values()];
}
// Union, intersection, difference, isSubsetOf methods similar to above
// ...
}
// Usage example
const mySetMap = new MySetMap();
mySetMap.add({name: 'Alice'}); // Can store objects
mySetMap.add({name: 'Bob'});
console.log(mySetMap.values()); // [{name: 'Alice'}, {name: 'Bob'}]
Set Operations
Union
function union(setA, setB) {
const unionSet = new Set([...setA, ...setB]);
return unionSet;
}
const setA = new Set([1, 2, 3]);
const setB = new Set([3, 4, 5]);
console.log(union(setA, setB)); // Set(5) {1, 2, 3, 4, 5}
Intersection
function intersection(setA, setB) {
const intersectionSet = new Set([...setA].filter(x => setB.has(x)));
return intersectionSet;
}
console.log(intersection(setA, setB)); // Set(1) {3}
Difference
function difference(setA, setB) {
const differenceSet = new Set([...setA].filter(x => !setB.has(x)));
return differenceSet;
}
console.log(difference(setA, setB)); // Set(2) {1, 2}
Subset Check
function isSubset(setA, setB) {
return [...setA].every(x => setB.has(x));
}
console.log(isSubset(new Set([1, 2]), new Set([1, 2, 3]))); // true
console.log(isSubset(new Set([1, 4]), new Set([1, 2, 3]))); // false
Set Applications
Data Deduplication
function unique(arr) {
return [...new Set(arr)];
}
console.log(unique([1, 2, 2, 3, 3, 4])); // [1, 2, 3, 4]
Membership Detection
const bannedUsers = new Set(['user1', 'user2']);
function isBanned(username) {
return bannedUsers.has(username);
}
console.log(isBanned('user1')); // true
console.log(isBanned('user3')); // false
Set Operations in Arrays
Intersection of Two Arrays
function intersection(arr1, arr2) {
const set1 = new Set(arr1);
const set2 = new Set(arr2);
return [...set1].filter(item => set2.has(item));
}
console.log(intersection([1, 2, 3], [2, 3, 4])); // [2, 3]
Union of Two Arrays
function union(arr1, arr2) {
return [...new Set([...arr1, ...arr2])];
}
console.log(union([1, 2, 3], [3, 4, 5])); // [1, 2, 3, 4, 5]
Difference of Two Arrays
function difference(arr1, arr2) {
const set2 = new Set(arr2);
return arr1.filter(item => !set2.has(item));
}
console.log(difference([1, 2, 3], [2, 3, 4])); // [1]
Subset Check
function isSubset(subset, superset) {
const setSuperset = new Set(superset);
return subset.every(item => setSuperset.has(item));
}
console.log(isSubset([1, 2], [1, 2, 3])); // true
console.log(isSubset([1, 4], [1, 2, 3])); // false
Implementing Union-Find (Disjoint Set)
class DisjointSet {
constructor() {
this.parent = new Map();
this.rank = new Map();
}
// Find root node
find(x) {
if (!this.parent.has(x)) {
this.parent.set(x, x);
this.rank.set(x, 0);
return x;
}
if (this.parent.get(x) !== x) {
this.parent.set(x, this.find(this.parent.get(x))); // Path compression
}
return this.parent.get(x);
}
// Union two sets
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX === rootY) return;
// Union by rank
if (this.rank.get(rootX) < this.rank.get(rootY)) {
this.parent.set(rootX, rootY);
} else if (this.rank.get(rootX) > this.rank.get(rootY)) {
this.parent.set(rootY, rootX);
} else {
this.parent.set(rootY, rootX);
this.rank.set(rootX, this.rank.get(rootX) + 1);
}
}
// Check if two elements are in the same set
isConnected(x, y) {
return this.find(x) === this.find(y);
}
}
// Usage example
const ds = new DisjointSet();
ds.union(1, 2);
ds.union(2, 3);
console.log(ds.isConnected(1, 3)); // true
console.log(ds.isConnected(1, 4)); // false
ds.union(3, 4);
console.log(ds.isConnected(1, 4)); // true
Performance Analysis of Sets
| Operation | Array-Based Set | Object-Based Set | Map-Based Set |
|---|---|---|---|
| add | O(n) (need to check existence) | O(1) | O(1) |
| delete | O(n) | O(1) | O(1) |
| has | O(n) | O(1) | O(1) |
| size | O(1) | O(1) | O(1) |
| values | O(n) | O(n) | O(n) |
Note:
- Array-based implementation is simple but has poor performance, especially for large sets
- Object/Map-based implementations have better performance and are suitable for most scenarios
- ES6’s Set object is highly optimized in modern browsers and usually does not require manual implementation
Relationship Between Sets and Other Data Structures
- With Arrays:
- Arrays can contain duplicate elements, sets cannot
- Arrays have indices, sets do not
- Arrays maintain insertion order (JS’s Set does not guarantee order, but iteration order is consistent with insertion order)
- With Objects/Map:
- Object keys can only be strings/Symbol, Set can store any type
- Map has key-value pairs, Set has only values
- Set focuses more on storing unique values
- With Mathematical Sets:
- JavaScript’s Set implements most mathematical set operations
- But lacks some advanced operations like power set, Cartesian product, etc.
Practical Application Scenarios
- Data Deduplication: Quickly remove duplicates from arrays
- Membership Detection: Efficiently check if a value exists
- Set Operations: Implement union, intersection, difference, etc.
- Graph Algorithms: Used to store vertices or edges in graphs
- Caching Systems: Implement simple key-value storage
- Permission Management: Store user permission sets
- Tag Systems: Store tags for articles or products
Summary
Sets are a very useful data structure, particularly suitable for scenarios requiring storage of unique values. JavaScript’s ES6 Set object provides complete set functionality, but in some special requirements, manually implementing sets still has value. Understanding the underlying principles of sets and different implementation methods helps make more appropriate choices in practical development.
In practical applications, the appropriate set implementation should be selected based on specific needs:
- For most cases, use ES6’s Set directly
- When needing to store any type, use Map-based implementation
- For learning purposes, try manually implementing various set operations
Sets are fundamental content in data structures and algorithm learning, and mastering them is crucial for understanding more complex data structures and algorithms.
