Class FastCopyHashSet<E>

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.Set<E>

    class FastCopyHashSet<E>
    extends java.util.AbstractSet<E>
    implements java.util.Set<E>, java.lang.Cloneable, java.io.Serializable
    A HashSet that is optimized for fast shallow copies. If the copy-ctor is passed another FastCopyHashSet, or clone is called on this set, the shallow copy can be performed using little more than a single array copy. In order to accomplish this, immutable objects must be used internally, so update operations result in slightly more object churn than HashSet.

    Note: It is very important to use a smaller load factor than you normally would for HashSet, since the implementation is open-addressed with linear probing. With a 50% load-factor a get is expected to return in only 2 probes. However, a 90% load-factor is expected to return in around 50 probes.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static int DEFAULT_CAPACITY
      Same default as HashMap, must be a power of 2
      private static float DEFAULT_LOAD_FACTOR
      50%
      private int hashCode
      Accumulated hash code
      private float loadFactor
      The user defined load factor which defines when to resize
      private static int MAXIMUM_CAPACITY
      MAX_INT - 1
      private int modCount
      Counter used to detect changes made outside of an iterator
      private static long serialVersionUID
      Serialization ID
      private int size
      The current number of key-value pairs
      private E[] table
      The open-addressed table
      private int threshold
      The next resize
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(E key)  
      boolean addAll​(java.util.Collection<? extends E> set)  
      void clear()  
      FastCopyHashSet<E> clone()  
      boolean contains​(java.lang.Object key)  
      boolean containsAll​(java.util.Collection<?> c)  
      boolean equals​(java.lang.Object o)  
      java.lang.Object[] getRawArray()  
      int hashCode()  
      private static int index​(int hashCode, int length)  
      private void init​(int initialCapacity, float loadFactor)  
      boolean isEmpty()  
      java.util.Iterator<E> iterator()  
      private int nextIndex​(int index, int length)  
      void printDebugStats()  
      private void putForCreate​(E key)  
      private void readObject​(java.io.ObjectInputStream s)  
      private void relocate​(int start)  
      boolean remove​(java.lang.Object key)  
      private void resize​(int from)  
      int size()  
      private void writeObject​(java.io.ObjectOutputStream s)  
      • Methods inherited from class java.util.AbstractSet

        removeAll
      • Methods inherited from class java.util.AbstractCollection

        retainAll, toArray, toArray, toString
      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.util.Collection

        parallelStream, removeIf, stream, toArray
      • Methods inherited from interface java.lang.Iterable

        forEach
      • Methods inherited from interface java.util.Set

        removeAll, retainAll, spliterator, toArray, toArray
    • Field Detail

      • serialVersionUID

        private static final long serialVersionUID
        Serialization ID
        See Also:
        Constant Field Values
      • DEFAULT_CAPACITY

        private static final int DEFAULT_CAPACITY
        Same default as HashMap, must be a power of 2
        See Also:
        Constant Field Values
      • MAXIMUM_CAPACITY

        private static final int MAXIMUM_CAPACITY
        MAX_INT - 1
        See Also:
        Constant Field Values
      • DEFAULT_LOAD_FACTOR

        private static final float DEFAULT_LOAD_FACTOR
        50%
        See Also:
        Constant Field Values
      • table

        private transient E[] table
        The open-addressed table
      • size

        private transient int size
        The current number of key-value pairs
      • threshold

        private transient int threshold
        The next resize
      • loadFactor

        private final float loadFactor
        The user defined load factor which defines when to resize
      • modCount

        private transient int modCount
        Counter used to detect changes made outside of an iterator
      • hashCode

        private transient int hashCode
        Accumulated hash code
    • Constructor Detail

      • FastCopyHashSet

        FastCopyHashSet​(int initialCapacity,
                        float loadFactor)
      • FastCopyHashSet

        FastCopyHashSet​(java.util.Set<? extends E> set)
      • FastCopyHashSet

        FastCopyHashSet​(int initialCapacity)
      • FastCopyHashSet

        FastCopyHashSet()
    • Method Detail

      • init

        private void init​(int initialCapacity,
                          float loadFactor)
      • nextIndex

        private int nextIndex​(int index,
                              int length)
      • index

        private static int index​(int hashCode,
                                 int length)
      • size

        public int size()
        Specified by:
        size in interface java.util.Collection<E>
        Specified by:
        size in interface java.util.Set<E>
        Specified by:
        size in class java.util.AbstractCollection<E>
      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Collection<E>
        Specified by:
        isEmpty in interface java.util.Set<E>
        Overrides:
        isEmpty in class java.util.AbstractCollection<E>
      • contains

        public boolean contains​(java.lang.Object key)
        Specified by:
        contains in interface java.util.Collection<E>
        Specified by:
        contains in interface java.util.Set<E>
        Overrides:
        contains in class java.util.AbstractCollection<E>
      • add

        public boolean add​(E key)
        Specified by:
        add in interface java.util.Collection<E>
        Specified by:
        add in interface java.util.Set<E>
        Overrides:
        add in class java.util.AbstractCollection<E>
      • resize

        private void resize​(int from)
      • addAll

        public boolean addAll​(java.util.Collection<? extends E> set)
        Specified by:
        addAll in interface java.util.Collection<E>
        Specified by:
        addAll in interface java.util.Set<E>
        Overrides:
        addAll in class java.util.AbstractCollection<E>
      • remove

        public boolean remove​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Collection<E>
        Specified by:
        remove in interface java.util.Set<E>
        Overrides:
        remove in class java.util.AbstractCollection<E>
      • relocate

        private void relocate​(int start)
      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Collection<E>
        Specified by:
        clear in interface java.util.Set<E>
        Overrides:
        clear in class java.util.AbstractCollection<E>
      • clone

        public FastCopyHashSet<E> clone()
        Overrides:
        clone in class java.lang.Object
      • iterator

        public java.util.Iterator<E> iterator()
        Specified by:
        iterator in interface java.util.Collection<E>
        Specified by:
        iterator in interface java.lang.Iterable<E>
        Specified by:
        iterator in interface java.util.Set<E>
        Specified by:
        iterator in class java.util.AbstractCollection<E>
      • printDebugStats

        public void printDebugStats()
      • readObject

        private void readObject​(java.io.ObjectInputStream s)
                         throws java.io.IOException,
                                java.lang.ClassNotFoundException
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException
      • putForCreate

        private void putForCreate​(E key)
      • writeObject

        private void writeObject​(java.io.ObjectOutputStream s)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • containsAll

        public boolean containsAll​(java.util.Collection<?> c)
        Specified by:
        containsAll in interface java.util.Collection<E>
        Specified by:
        containsAll in interface java.util.Set<E>
        Overrides:
        containsAll in class java.util.AbstractCollection<E>
      • equals

        public boolean equals​(java.lang.Object o)
        Specified by:
        equals in interface java.util.Collection<E>
        Specified by:
        equals in interface java.util.Set<E>
        Overrides:
        equals in class java.util.AbstractSet<E>
      • hashCode

        public int hashCode()
        Specified by:
        hashCode in interface java.util.Collection<E>
        Specified by:
        hashCode in interface java.util.Set<E>
        Overrides:
        hashCode in class java.util.AbstractSet<E>
      • getRawArray

        public java.lang.Object[] getRawArray()