class CompactHashSet<E>
extends java.util.AbstractSet<E>
implements java.io.Serializable
contains(x)
, add(x)
and remove(x)
, are all (expected and amortized)
constant time operations. Expected in the hashtable sense (depends on the hash function doing a
good job of distributing the elements to the buckets to a distribution not far from uniform), and
amortized since some operations can trigger a hash table resize.
Unlike java.util.HashSet
, iteration is only proportional to the actual size()
,
which is optimal, and not the size of the internal hashtable, which could be much larger
than size()
. Furthermore, this structure only depends on a fixed number of arrays; add(x)
operations do not create objects for the garbage collector to deal with, and for
every element added, the garbage collector will have to traverse 1.5
references on
average, in the marking phase, not 5.0
as in java.util.HashSet
.
If there are no removals, then iteration
order is the same as insertion
order. Any removal invalidates any ordering guarantees.
This class should not be assumed to be universally superior to java.util.HashSet
.
Generally speaking, this class reduces object allocation and memory consumption at the price of
moderately increased constant factors of CPU. Only use this class when there is a specific reason
to prioritize memory over CPU.
Modifier and Type | Field and Description |
---|---|
(package private) java.lang.Object[] |
elements
The elements contained in the set, in the range of [0, size()).
|
private int[] |
entries
Contains the logical entries, in the range of [0, size()).
|
(package private) static double |
HASH_FLOODING_FPP
Maximum allowed false positive probability of detecting a hash flooding attack given random
input.
|
private static int |
MAX_HASH_BUCKET_LENGTH
Maximum allowed length of a hash table bucket before falling back to a j.u.LinkedHashSet based
implementation.
|
private int |
metadata
Keeps track of metadata like the number of hash table bits and modifications of this data
structure (to make it possible to throw ConcurrentModificationException in the iterator).
|
private int |
size
The number of elements contained in the set.
|
private java.lang.Object |
table
The hashtable object.
|
Constructor and Description |
---|
CompactHashSet()
Constructs a new empty instance of
CompactHashSet . |
CompactHashSet(int expectedSize)
Constructs a new instance of
CompactHashSet with the specified capacity. |
Modifier and Type | Method and Description |
---|---|
boolean |
add(E object) |
(package private) int |
adjustAfterRemove(int indexBeforeRemove,
int indexRemoved)
Updates the index an iterator is pointing to after a call to remove: returns the index of the
entry that should be looked at after a removal on indexRemoved, with indexBeforeRemove as the
index that *was* the next entry that would be looked at.
|
(package private) int |
allocArrays()
Handle lazy allocation of arrays.
|
void |
clear() |
boolean |
contains(java.lang.Object object) |
(package private) java.util.Set<E> |
convertToHashFloodingResistantImplementation() |
static <E> CompactHashSet<E> |
create()
Creates an empty
CompactHashSet instance. |
static <E> CompactHashSet<E> |
create(java.util.Collection<? extends E> collection)
Creates a mutable
CompactHashSet instance containing the elements of the given
collection in unspecified order. |
static <E> CompactHashSet<E> |
create(E... elements)
Creates a mutable
CompactHashSet instance containing the given elements in
unspecified order. |
private java.util.Set<E> |
createHashFloodingResistantDelegate(int tableSize) |
static <E> CompactHashSet<E> |
createWithExpectedSize(int expectedSize)
Creates a
CompactHashSet instance, with a high enough "initial capacity" that it
should hold expectedSize elements without growth. |
(package private) java.util.Set<E> |
delegateOrNull() |
private E |
element(int i) |
private int |
entry(int i) |
(package private) int |
firstEntryIndex() |
void |
forEach(java.util.function.Consumer<? super E> action) |
(package private) int |
getSuccessor(int entryIndex) |
private int |
hashTableMask()
Gets the hash table mask using the stored number of hash table bits.
|
(package private) void |
incrementModCount() |
(package private) void |
init(int expectedSize)
Pseudoconstructor for serialization support.
|
(package private) void |
insertEntry(int entryIndex,
E object,
int hash,
int mask)
Creates a fresh entry with the specified object at the specified position in the entry arrays.
|
boolean |
isEmpty() |
(package private) boolean |
isUsingHashFloodingResistance() |
java.util.Iterator<E> |
iterator() |
(package private) void |
moveLastEntry(int dstIndex,
int mask)
Moves the last entry in the entry array into
dstIndex , and nulls out its old position. |
(package private) boolean |
needsAllocArrays()
Returns whether arrays need to be allocated.
|
private void |
readObject(java.io.ObjectInputStream stream) |
boolean |
remove(java.lang.Object object) |
private java.lang.Object[] |
requireElements() |
private int[] |
requireEntries() |
private java.lang.Object |
requireTable() |
(package private) void |
resizeEntries(int newCapacity)
Resizes the internal entries array to the specified capacity, which may be greater or less than
the current capacity.
|
private void |
resizeMeMaybe(int newSize)
Resizes the entries storage if necessary.
|
private int |
resizeTable(int oldMask,
int newCapacity,
int targetHash,
int targetEntryIndex) |
private void |
setElement(int i,
E value) |
private void |
setEntry(int i,
int value) |
private void |
setHashTableMask(int mask)
Stores the hash table mask as the number of bits needed to represent an index.
|
int |
size() |
java.util.Spliterator<E> |
spliterator() |
java.lang.Object[] |
toArray() |
<T> T[] |
toArray(T[] a) |
void |
trimToSize()
Ensures that this
CompactHashSet has the smallest representation in memory, given its
current size. |
private void |
writeObject(java.io.ObjectOutputStream stream) |
static final double HASH_FLOODING_FPP
private static final int MAX_HASH_BUCKET_LENGTH
@CheckForNull private transient java.lang.Object table
@CheckForNull private transient int[] entries
hash = aaaaaaaa mask = 00000fff next = 00000bbb entry = aaaaabbb
The pointers in [size(), entries.length) are all "null" (UNSET).
@CheckForNull transient java.lang.Object[] elements
null
.private transient int metadata
private transient int size
CompactHashSet()
CompactHashSet
.CompactHashSet(int expectedSize)
CompactHashSet
with the specified capacity.expectedSize
- the initial capacity of this CompactHashSet
.public static <E> CompactHashSet<E> create()
CompactHashSet
instance.public static <E> CompactHashSet<E> create(java.util.Collection<? extends E> collection)
CompactHashSet
instance containing the elements of the given
collection in unspecified order.collection
- the elements that the set should containCompactHashSet
containing those elements (minus duplicates)@SafeVarargs public static <E> CompactHashSet<E> create(E... elements)
CompactHashSet
instance containing the given elements in
unspecified order.elements
- the elements that the set should containCompactHashSet
containing those elements (minus duplicates)public static <E> CompactHashSet<E> createWithExpectedSize(int expectedSize)
CompactHashSet
instance, with a high enough "initial capacity" that it
should hold expectedSize
elements without growth.expectedSize
- the number of elements you expect to add to the returned setCompactHashSet
with enough capacity to hold expectedSize
elements without resizingjava.lang.IllegalArgumentException
- if expectedSize
is negativevoid init(int expectedSize)
boolean needsAllocArrays()
int allocArrays()
@CheckForNull java.util.Set<E> delegateOrNull()
private java.util.Set<E> createHashFloodingResistantDelegate(int tableSize)
java.util.Set<E> convertToHashFloodingResistantImplementation()
boolean isUsingHashFloodingResistance()
private void setHashTableMask(int mask)
private int hashTableMask()
void incrementModCount()
public boolean add(E object)
void insertEntry(int entryIndex, E object, int hash, int mask)
private void resizeMeMaybe(int newSize)
void resizeEntries(int newCapacity)
private int resizeTable(int oldMask, int newCapacity, int targetHash, int targetEntryIndex)
public boolean contains(@CheckForNull java.lang.Object object)
public boolean remove(@CheckForNull java.lang.Object object)
void moveLastEntry(int dstIndex, int mask)
dstIndex
, and nulls out its old position.int firstEntryIndex()
int getSuccessor(int entryIndex)
int adjustAfterRemove(int indexBeforeRemove, int indexRemoved)
public java.util.Iterator<E> iterator()
public java.util.Spliterator<E> spliterator()
public void forEach(java.util.function.Consumer<? super E> action)
forEach
in interface java.lang.Iterable<E>
public int size()
public boolean isEmpty()
public java.lang.Object[] toArray()
public <T> T[] toArray(T[] a)
public void trimToSize()
CompactHashSet
has the smallest representation in memory, given its
current size.public void clear()
private void writeObject(java.io.ObjectOutputStream stream) throws java.io.IOException
java.io.IOException
private void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, java.lang.ClassNotFoundException
java.io.IOException
java.lang.ClassNotFoundException
private java.lang.Object requireTable()
private int[] requireEntries()
private java.lang.Object[] requireElements()
private E element(int i)
private int entry(int i)
private void setElement(int i, E value)
private void setEntry(int i, int value)