Skip to content

Sets

Quote

“Smart data structures and dumb code works a lot better than the other way around.” — Eric S. Raymond

Operation HashSet LinkedHashSet EnumSet TreeSet CopyOnWriteArraySet ConcurrentSkipListSet
Add \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\)
Remove \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\)
Contains \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\)
Next \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(h / n)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Size \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\) \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)
Operation set
x in s \(\color{white} \fcolorbox{limegreen}{forestgreen} {Θ(1)}\) → \(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)
Union s|t \(\color{black} \fcolorbox{gold}{yellow} {Θ(len(s) + len(t))}\)
Intersection s&t \(\color{black} \fcolorbox{gold}{yellow} {Θ(min(len(s), len(t)))}\) → \(\color{black} \fcolorbox{darkorange}{sandybrown} {O(len(s) . len(t))}\)
Multiple intersection s1&s2&...&sn \(\color{black} \fcolorbox{darkorange}{sandybrown} {(n - 1) . O(l)}\)
\(\small{\textsf{where} l = \mathtt{max}(\mathtt{len}(s1), \ldots, \mathtt{len}(sn))}\)
Difference s-t \(\color{black} \fcolorbox{gold}{yellow} {Θ(len(s))}\)
s.difference_update(t) \(\color{black} \fcolorbox{gold}{yellow} {Θ(len(t))}\)
Symmetric Difference s^t \(\color{black} \fcolorbox{gold}{yellow} {Θ(len(s))}\) → \(\color{black} \fcolorbox{darkorange}{sandybrown} {O(len(s) . len(t))}\)
s.symmetric_difference_update(t) \(\color{black} \fcolorbox{gold}{yellow} {Θ(len(t))}\) → \(\color{black} \fcolorbox{darkorange}{sandybrown} {O(len(s) . len(t))}\)

Sets are a collection of unique elements.

var empty = Collections.emptySet()
Set<Integer> set = [1, 2, 3]
var unmodifiableSet = Collections.unmodifiableSet(set)

Set<Integer> empty = Collections.emptySet();
Set<Integer> set = new HashSet<>();
Set<Integer> unmodifiableSet = Collections.unmodifiableSet(set);

const set = new Set([1, 2, 3]);

val empty = emptySet<Int>()
val set = mutableSetOf(1, 2, 3)
val unmodifiableSet = setOf(1, 2, 3)

s = set(1, 2, 3)
unmodifiable_set = frozenset([1, 2, 3])

const set = new Set<number>([1, 2, 3]);

block-beta
  columns 2
  block:indices
    columns 1
    space:3 current("current")
  end
  block:nums
    columns 1
    v1["3"] v2["6"] v3["5"] v4["8"]
  end

  current --> v4

style indices fill:transparent

Which one to use?

  • HashSet is the fastest to iterate.
  • Use LinkedHashSet when the insertion order matters.
  • Use TreeSet when the natural order matters.