Package org.apache.hadoop.hdfs.util

Class LightWeightHashSet<T>

java.lang.Object
org.apache.hadoop.hdfs.util.LightWeightHashSet<T>
All Implemented Interfaces:
Iterable<T>, Collection<T>
Direct Known Subclasses:
LightWeightLinkedSet
public class LightWeightHashSet<T> extends Object implements Collection<T>
A low memory linked hash set implementation, which uses an array for storing the elements and linked lists for collision resolution. This class does not support null element. This class is not thread safe.

  • Field Details

    • DEFAULT_MAX_LOAD_FACTOR

      protected static final float DEFAULT_MAX_LOAD_FACTOR
      See Also:

    • DEFAUT_MIN_LOAD_FACTOR

      protected static final float DEFAUT_MIN_LOAD_FACTOR
      See Also:

    • MINIMUM_CAPACITY

      protected static final int MINIMUM_CAPACITY
      See Also:

    • entries

      protected org.apache.hadoop.hdfs.util.LightWeightHashSet.LinkedElement<T>[] entries
      An internal array of entries, which are the rows of the hash table. The size must be a power of two.

    • size

      protected int size
      The size of the set (not the entry array).

    • modification

      protected int modification
      Modification version for fail-fast.
      See Also:

  • Constructor Details

    • LightWeightHashSet

      public LightWeightHashSet(int initCapacity, float maxLoadFactor, float minLoadFactor)
      Parameters:
      initCapacity - Recommended size of the internal array.
      maxLoadFactor - used to determine when to expand the internal array
      minLoadFactor - used to determine when to shrink the internal array

    • LightWeightHashSet

      public LightWeightHashSet()

    • LightWeightHashSet

      public LightWeightHashSet(int minCapacity)

  • Method Details

    • isEmpty

      public boolean isEmpty()
      Check if the set is empty.
      Specified by:
      isEmpty in interface Collection<T>
      Returns:
      true is set empty, false otherwise

    • getCapacity

      public int getCapacity()
      Return the current capacity (for testing).

    • size

      public int size()
      Return the number of stored elements.
      Specified by:
      size in interface Collection<T>

    • getIndex

      protected int getIndex(int hashCode)
      Get index in the internal table for a given hash.

    • contains

      public boolean contains(Object key)
      Check if the set contains given element
      Specified by:
      contains in interface Collection<T>
      Returns:
      true if element present, false otherwise.

    • getElement

      public T getElement(T key)
      Return the element in this set which is equal to the given key, if such an element exists. Otherwise returns null.

    • getContainedElem

      protected T getContainedElem(int index, T key, int hashCode)
      Check if the set contains given element at given index. If it does, return that element.
      Returns:
      the element, or null, if no element matches

    • addAll

      public boolean addAll(Collection<? extends T> toAdd)
      All all elements in the collection. Expand if necessary.
      Specified by:
      addAll in interface Collection<T>
      Parameters:
      toAdd - - elements to add.
      Returns:
      true if the set has changed, false otherwise

    • add

      public boolean add(T element)
      Add given element to the hash table. Expand table if necessary.
      Specified by:
      add in interface Collection<T>
      Returns:
      true if the element was not present in the table, false otherwise

    • addElem

      protected boolean addElem(T element)
      Add given element to the hash table
      Returns:
      true if the element was not present in the table, false otherwise

    • remove

      public boolean remove(Object key)
      Remove the element corresponding to the key.
      Specified by:
      remove in interface Collection<T>
      Returns:
      If such element exists, return true. Otherwise, return false.

    • removeElem

      protected org.apache.hadoop.hdfs.util.LightWeightHashSet.LinkedElement<T> removeElem(T key)
      Remove the element corresponding to the key, given key.hashCode() == index.
      Returns:
      If such element exists, return true. Otherwise, return false.

    • pollN

      public List<T> pollN(int n)
      Remove and return n elements from the hashtable. The order in which entries are removed is unspecified, and and may not correspond to the order in which they were inserted.
      Returns:
      first element

    • pollAll

      public List<T> pollAll()
      Remove all elements from the set and return them. Clear the entries.

    • pollToArray

      public T[] pollToArray(T[] array)
      Get array.length elements from the set, and put them into the array.

    • shrinkIfNecessary

      protected void shrinkIfNecessary()
      Checks if we need to shrink, and shrinks if necessary.

    • expandIfNecessary

      protected void expandIfNecessary()
      Checks if we need to expand, and expands if necessary.

    • iterator

      public Iterator<T> iterator()
      Specified by:
      iterator in interface Collection<T>
      Specified by:
      iterator in interface Iterable<T>

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • printDetails

      public void printDetails(PrintStream out)
      Print detailed information of this object.

    • clear

      public void clear()
      Clear the set. Resize it to the original capacity.
      Specified by:
      clear in interface Collection<T>

    • toArray

      public Object[] toArray()
      Specified by:
      toArray in interface Collection<T>

    • toArray

      public <U> U[] toArray(U[] a)
      Specified by:
      toArray in interface Collection<T>

    • containsAll

      public boolean containsAll(Collection<?> c)
      Specified by:
      containsAll in interface Collection<T>

    • removeAll

      public boolean removeAll(Collection<?> c)
      Specified by:
      removeAll in interface Collection<T>

    • retainAll

      public boolean retainAll(Collection<?> c)
      Specified by:
      retainAll in interface Collection<T>