Skip to content

Latest commit

 

History

History
309 lines (228 loc) · 11.3 KB

Set.md

File metadata and controls

309 lines (228 loc) · 11.3 KB
Raw

Set

Interface Set in Java defines a collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. It inherits from the Collection interface.

The hierarchy of Set classes is

Java HashSet

HashSet Class

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.

Note that this implementation is not synchronized.

  • This class offers constant time performance for the basic operations, including add, remove, contains, isEmpty, and size, assuming the hash function disperses the elements properly among the buckets.

  • Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

HashSet Constructor

// Constructs a new, empty set; the backing HashMap instance has default initial capacity (16) and load factor (0.75).
HashSet set = new HashSet();

// Constructs a new set containing the elements in the specified collection.
HashSet set = new HashSet(Collection<? extends E> c);

// Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and default load factor (0.75).
HashSet set = new HashSet(int initialCapacity);

// Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and the specified load factor.
HashSet set = new HashSet(int initialCapacity, float loadFactor)

load factor = Number of stored elements in the table / Size of the hash table

Methods in HashSet

  • boolean add(E e): adds the specified element to this set if it is not already present.
HashSet<String> hs = new HashSet<>();
for (int i = 0; i < 10; i++)
  hs.add(String.valueOf(i));    // containing [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], no guarantee in order
  • void clear(): removes all of the elements from this set.
HashSet<String> hs = new HashSet<>();
for (int i = 0; i < 10; i++)
  hs.add(String.valueOf(i));
hs.clear();
  • boolean contains(Object o): returns true if this set contains the specified element.
HashSet<String> hs = new HashSet<>();
for (int i = 0; i < 10; i++)
  hs.add(String.valueOf(i));
hs.contains("5");         // returns true
hs.contains("50");        // returns false
  • boolean isEmpty(): returns true if this set contains no elements.
HashSet<String> hs = new HashSet<>();
hs.isEmpty();                      // returns true
for (int i = 0; i < 10; i++)
  hs.add(String.valueOf(i));
hs.isEmpty();                     // returns false
  • boolean remove(Object o): removes the specified element from this set if it is present.
HashSet<String> hs = new HashSet<>();
for (int i = 0; i < 10; i++)
  hs.add(String.valueOf(i));    // containing [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], no guarantee in order
hs.remove("5")                  // containing [0, 1, 2, 3, 4, 6, 7, 8, 9], no guarantee in order
  • int size(): returns the number of elements in this set (its cardinality).
HashSet<String> hs = new HashSet<>();
for (int i = 0; i < 10; i++)
  hs.add(String.valueOf(i));
hs.size();          // returns 10
  • Iterator iterator(): returns an iterator over the elements in this set.
HashSet<String> hs = new HashSet<>();
for (int i = 0; i < 10; i++)
  hs.add(String.valueOf(i));
Iterator<String> it = hs.iterator();
while (it.hasNext())
  System.out.println(it.next());      // [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

SortedSet Interface

A Set (inherits Set interface) that further provides a total ordering on its elements. The elements are ordered using their natural ordering, or by a Comparator typically provided at sorted set creation time. The set's iterator will traverse the set in ascending element order. Several additional operations are provided to take advantage of the ordering.

NavigableSet Interface

A SortedSet extended with navigation methods reporting closest matches for given search targets. Methods lower, floor, ceiling, and higher return elements respectively less than, less than or equal, greater than or equal, and greater than a given element, returning null if there is no such element.

TreeSet Class

A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering or by a Comparator provided at set creation time, depending on which constructor is used.

The inheritance order is SortedSet <- NavigableSet <- TreeSet.

Note that this implementation is not synchronized. To synchronize it,

TreeSet ts = new TreeSet();
Set syncSet = Collections.synchronziedSet(ts);

Some features of TreeSet are:

  • Objects in a TreeSet are stored in a sorted and ascending order.
  • TreeSet does not preserve the insertion order of elements but elements are sorted by keys.
  • TreeSet is basically an implementation of a self-balancing binary search tree like Red-Black Tree. Therefore operations like add, remove and search take O(lgn) time. And operations like printing n elements in sorted order take O(n) time.

Tree Constructor

// Constructs a new, empty tree set, sorted according to the natural ordering of its elements.
TreeSet ts = new TreeSet();
// Constructs a new tree set containing the elements in the specified collection, sorted according to the natural ordering of its elements.
TreeSet ts = new TreeSet(Collection<? extends E> c);
// Constructs a new, empty tree set, sorted according to the specified comparator.
TreeSet ts = new TreeSet(Comparator<? super E> comparator);
// Constructs a new tree set containing the same elements and using the same ordering as the specified sorted set.
TreeSet ts = new TreeSet(SortedSet<E> s);

Special Methods in TreeSet

  • E ceiling(E e): Returns the least element in this set greater than or equal to the given element, or null if there is no such element.
TreeSet<String> ts = new TreeSet<>();
for (int i = 0; i < 10; i++)
  ts.add(String.valueOf(i*10));
ts.ceiling("24");                // return 30
  • E floor(E e): Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
TreeSet<String> ts = new TreeSet<>();
for (int i = 0; i < 10; i++)
  ts.add(String.valueOf(i*10));
ts.floor("24");                // return 20
  • Iterator descendingIterator(): Returns an iterator over the elements in this set in descending order.
TreeSet<String> ts = new TreeSet<>();
for (int i = 0; i < 10; i++)
  ts.add(String.valueOf(i));
Iterator<String> it = ts.descendingIterator();
while (it.hasNext())
  System.out.println(it.next());
  • E higher(E e): Returns the least element in this set strictly greater than the given element, or null if there is no such element.
TreeSet<String> ts = new TreeSet<>();
for (int i = 0; i < 10; i++)
  ts.add(String.valueOf(i));
ts.higher("5");                // return 6
  • E last(): Returns the last (highest) element currently in this set.
TreeSet<String> ts = new TreeSet<>();
for (int i = 0; i < 10; i++)
  ts.add(String.valueOf(i));
ts.last();                // return 9
  • E lower(E e): Returns the greatest element in this set strictly less than the given element, or null if there is no such element.
TreeSet<String> ts = new TreeSet<>();
for (int i = 0; i < 10; i++)
  ts.add(String.valueOf(i));
ts.lower("5");                // return 4
  • E pollFirst() and E pollLast(): Retrieves and removes the first (lowest) / the last (highest) element, or returns null if this set is empty.
TreeSet<String> ts = new TreeSet<>();
for (int i = 0; i < 10; i++)
  ts.add(String.valueOf(i));
ts.pollFirst();                // return 0
ts.pollLast();                 // return 9
  • SortedSet subSet(E fromElement, E toElement): Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.
TreeSet<String> ts = new TreeSet<>();
for (int i = 0; i < 10; i++)
  ts.add(String.valueOf(i));
ts.subSet("2", "8");           // return [2, 3, 4, 5, 6, 7]
  • SortedSet headSet(E toElement) and SortedSet headSet(E toElement, boolean inclusive): Returns a view of the portion of this set whose elements are strictly less than toElement.
TreeSet<String> ts = new TreeSet<>();
for (int i = 0; i < 10; i++)
  ts.add(String.valueOf(i));
ts.headSet("8");           // return [0, 1, 2, 3, 4, 5, 6, 7]
  • SortedSet tailSet(E fromElement) and NavigableSet tailSet(E fromElement, boolean inclusive): Returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement.
TreeSet<String> ts = new TreeSet<>();
for (int i = 0; i < 10; i++)
  ts.add(String.valueOf(i));
ts.tailSet("5");           // return [5, 6, 7, 8, 9]

Union Find (Disjoint Set)

Disjoint Set

Union–find data structure (also called a disjoint-set data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations to add new sets, merge existing sets, and determine whether elements are in the same set.

Operations

MakeSet

public UnionFind(int n) {
    parent = new int[n];
    for (int i = 0; i < n; i++)
        parent[i] = i;
}

Find

public int find(int p) {
    if (parent[p] == p)
        return p;
    else
        return find(parent[p]);
}

Union

public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    parent[rootQ] = rootP;
}

The implementation of UnionFind class is here

Techniques in an Interview

HashSet is usually used to store processed values, like the Two-Sum question, and visited nodes in a graph for BFS.

Reference