@GwtIncompatible 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 |
---|---|
private static float |
DEFAULT_LOAD_FACTOR |
private static int |
DEFAULT_SIZE |
(package private) java.lang.Object[] |
elements
The elements contained in the set, in the range of [0, size()).
|
private long[] |
entries
Contains the logical entries, in the range of [0, size()).
|
private static long |
HASH_MASK
Bitmask that selects the high 32 bits.
|
(package private) float |
loadFactor
The load factor.
|
private static int |
MAXIMUM_CAPACITY |
(package private) int |
modCount
Keeps track of modifications of this set, to make it possible to throw
ConcurrentModificationException in the iterator.
|
private static long |
NEXT_MASK
Bitmask that selects the low 32 bits.
|
private int |
size
The number of elements contained in the set.
|
private int[] |
table
The hashtable.
|
private int |
threshold
When we have this many elements, resize the hashtable.
|
(package private) static int |
UNSET |
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.
|
void |
clear() |
boolean |
contains(java.lang.Object object) |
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. |
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) int |
firstEntryIndex() |
void |
forEach(java.util.function.Consumer<? super E> action) |
private static int |
getHash(long entry) |
private static int |
getNext(long entry)
Returns the index, or UNSET if the pointer is "null"
|
(package private) int |
getSuccessor(int entryIndex) |
private int |
hashTableMask() |
(package private) void |
init(int expectedSize,
float loadFactor)
Pseudoconstructor for serialization support.
|
(package private) void |
insertEntry(int entryIndex,
E object,
int hash)
Creates a fresh entry with the specified object at the specified position in the entry arrays.
|
boolean |
isEmpty() |
java.util.Iterator<E> |
iterator() |
(package private) void |
moveEntry(int dstIndex)
Moves the last entry in the entry array into
dstIndex , and nulls out its old position. |
private static long[] |
newEntries(int size) |
private static int[] |
newTable(int size) |
private void |
readObject(java.io.ObjectInputStream stream) |
boolean |
remove(java.lang.Object object) |
private boolean |
remove(java.lang.Object object,
int hash) |
(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)
Returns currentSize + 1, after resizing the entries storage if necessary.
|
private void |
resizeTable(int newCapacity) |
int |
size() |
java.util.Spliterator<E> |
spliterator() |
private static long |
swapNext(long entry,
int newNext)
Returns a new entry value by changing the "next" index of an existing entry
|
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)
The serial form currently mimics Android's java.util.HashSet version, e.g.
|
private static final int MAXIMUM_CAPACITY
private static final float DEFAULT_LOAD_FACTOR
private static final long NEXT_MASK
private static final long HASH_MASK
private static final int DEFAULT_SIZE
static final int UNSET
private transient int[] table
Currently, the UNSET value means "null pointer", and any non negative value x is the actual index.
Its size must be a power of two.
private transient long[] entries
transient java.lang.Object[] elements
transient float loadFactor
transient int modCount
private transient int threshold
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)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, float loadFactor)
private static int[] newTable(int size)
private static long[] newEntries(int size)
private static int getHash(long entry)
private static int getNext(long entry)
private static long swapNext(long entry, int newNext)
private int hashTableMask()
public boolean add(E object)
void insertEntry(int entryIndex, E object, int hash)
private void resizeMeMaybe(int newSize)
void resizeEntries(int newCapacity)
private void resizeTable(int newCapacity)
public boolean contains(java.lang.Object object)
public boolean remove(java.lang.Object object)
private boolean remove(java.lang.Object object, int hash)
void moveEntry(int dstIndex)
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