Class IdentityHashSet<E>

  • Type Parameters:
    E - the element type
    All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.Set<E>

    class IdentityHashSet<E>
    extends java.util.AbstractSet<E>
    implements java.util.Set<E>, java.lang.Cloneable, java.io.Serializable
    An identity based hash set. A number of properties apply to this set. It compares only using object identity, it supports null entries, it allocates little more than a single object array, and it can be copied quickly. If the copy-ctor is passed another IdentityHashSet, or clone is called on this set, the shallow copy can be performed using little more than a single array copy. 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
      67%, just like IdentityHashMap
      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 java.lang.Object[] 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 entry)  
      boolean addAll​(java.util.Collection<? extends E> collection)  
      void clear()  
      IdentityHashSet<E> clone()  
      boolean contains​(java.lang.Object entry)  
      private static int hash​(java.lang.Object o)  
      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 entry)  
      private void readObject​(java.io.ObjectInputStream s)  
      private void relocate​(int start)  
      boolean remove​(java.lang.Object o)  
      private void resize​(int from)  
      int size()  
      E[] toArray​(E[] target, int offs, int len)
      Warning: this will crap out if the set contains a null.
      <T> T[] toScatteredArray​(T[] dummy)
      Advanced method that returns a copy of the internal table.
      private void writeObject​(java.io.ObjectOutputStream s)  
      • Methods inherited from class java.util.AbstractSet

        equals, hashCode, removeAll
      • Methods inherited from class java.util.AbstractCollection

        containsAll, 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

        containsAll, equals, hashCode, 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
        67%, just like IdentityHashMap
        See Also:
        Constant Field Values
      • table

        private transient java.lang.Object[] 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
    • Constructor Detail

      • IdentityHashSet

        public IdentityHashSet​(int initialCapacity,
                               float loadFactor)
      • IdentityHashSet

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

        public IdentityHashSet​(int initialCapacity)
      • IdentityHashSet

        public IdentityHashSet()
    • Method Detail

      • init

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

        private static int hash​(java.lang.Object o)
      • 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 entry)
        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 entry)
        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> collection)
        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 o)
        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 IdentityHashSet<E> clone()
        Overrides:
        clone in class java.lang.Object
      • toScatteredArray

        public <T> T[] toScatteredArray​(T[] dummy)
        Advanced method that returns a copy of the internal table. The resulting array will contain nulls at random places that must be skipped. In addition, it will not operate correctly if a null was inserted into the set. Use at your own risk....
        Parameters:
        dummy - the input array
        Returns:
        an array containing elements in this set along with randomly placed nulls,
      • toArray

        public E[] toArray​(E[] target,
                           int offs,
                           int len)
        Warning: this will crap out if the set contains a null.
        Parameters:
        target - the target to write to
        offs - the offset into the target
        len - the length to write
        Returns:
        the target array
      • 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 entry)
      • writeObject

        private void writeObject​(java.io.ObjectOutputStream s)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • 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>