Class CompactHashSet<E>
- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- java.util.AbstractSet<E>
-
- com.google.common.collect.CompactHashSet<E>
-
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Iterable<E>
,java.util.Collection<E>
,java.util.Set<E>
- Direct Known Subclasses:
CompactLinkedHashSet
@GwtIncompatible class CompactHashSet<E> extends java.util.AbstractSet<E> implements java.io.Serializable
CompactHashSet is an implementation of a Set. All optional operations (adding and removing) are supported. The elements can be any objects.contains(x)
,add(x)
andremove(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 actualsize()
, which is optimal, and not the size of the internal hashtable, which could be much larger thansize()
. 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 traverse1.5
references on average, in the marking phase, not5.0
as injava.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.
-
-
Field Summary
Fields Modifier and Type Field Description (package 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.private static float
LOAD_FACTOR
(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.(package private) static int
UNSET
-
Constructor Summary
Constructors Constructor Description CompactHashSet()
Constructs a new empty instance ofCompactHashSet
.CompactHashSet(int expectedSize)
Constructs a new instance ofCompactHashSet
with the specified capacity.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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) void
allocArrays()
Handle lazy allocation of arrays.void
clear()
boolean
contains(java.lang.Object object)
static <E> CompactHashSet<E>
create()
Creates an emptyCompactHashSet
instance.static <E> CompactHashSet<E>
create(E... elements)
Creates a mutableCompactHashSet
instance containing the given elements in unspecified order.static <E> CompactHashSet<E>
create(java.util.Collection<? extends E> collection)
Creates a mutableCompactHashSet
instance containing the elements of the given collection in unspecified order.static <E> CompactHashSet<E>
createWithExpectedSize(int expectedSize)
Creates aCompactHashSet
instance, with a high enough "initial capacity" that it should holdexpectedSize
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)
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
moveLastEntry(int dstIndex)
Moves the last entry in the entry array intodstIndex
, and nulls out its old position.(package private) boolean
needsAllocArrays()
Returns whether arrays need to be allocated.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)
Resizes 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 entryjava.lang.Object[]
toArray()
<T> T[]
toArray(T[] a)
void
trimToSize()
Ensures that thisCompactHashSet
has the smallest representation in memory, given its current size.private void
writeObject(java.io.ObjectOutputStream stream)
-
-
-
Field Detail
-
LOAD_FACTOR
private static final float LOAD_FACTOR
- See Also:
- Constant Field Values
-
NEXT_MASK
private static final long NEXT_MASK
Bitmask that selects the low 32 bits.- See Also:
- Constant Field Values
-
HASH_MASK
private static final long HASH_MASK
Bitmask that selects the high 32 bits.- See Also:
- Constant Field Values
-
DEFAULT_SIZE
static final int DEFAULT_SIZE
- See Also:
- Constant Field Values
-
UNSET
static final int UNSET
- See Also:
- Constant Field Values
-
table
private transient int[] table
The hashtable. Its values are indexes to the elements and entries arrays.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.
-
entries
private transient long[] entries
Contains the logical entries, in the range of [0, size()). The high 32 bits of each long is the smeared hash of the element, whereas the low 32 bits is the "next" pointer (pointing to the next entry in the bucket chain). The pointers in [size(), entries.length) are all "null" (UNSET).
-
elements
transient java.lang.Object[] elements
The elements contained in the set, in the range of [0, size()). The elements in [size(), elements.length) are allnull
.
-
modCount
transient int modCount
Keeps track of modifications of this set, to make it possible to throw ConcurrentModificationException in the iterator. Note that we choose not to make this volatile, so we do less of a "best effort" to track such errors, for better performance.
-
size
private transient int size
The number of elements contained in the set.
-
-
Method Detail
-
create
public static <E> CompactHashSet<E> create()
Creates an emptyCompactHashSet
instance.
-
create
public static <E> CompactHashSet<E> create(java.util.Collection<? extends E> collection)
Creates a mutableCompactHashSet
instance containing the elements of the given collection in unspecified order.- Parameters:
collection
- the elements that the set should contain- Returns:
- a new
CompactHashSet
containing those elements (minus duplicates)
-
create
public static <E> CompactHashSet<E> create(E... elements)
Creates a mutableCompactHashSet
instance containing the given elements in unspecified order.- Parameters:
elements
- the elements that the set should contain- Returns:
- a new
CompactHashSet
containing those elements (minus duplicates)
-
createWithExpectedSize
public static <E> CompactHashSet<E> createWithExpectedSize(int expectedSize)
Creates aCompactHashSet
instance, with a high enough "initial capacity" that it should holdexpectedSize
elements without growth.- Parameters:
expectedSize
- the number of elements you expect to add to the returned set- Returns:
- a new, empty
CompactHashSet
with enough capacity to holdexpectedSize
elements without resizing - Throws:
java.lang.IllegalArgumentException
- ifexpectedSize
is negative
-
init
void init(int expectedSize)
Pseudoconstructor for serialization support.
-
needsAllocArrays
boolean needsAllocArrays()
Returns whether arrays need to be allocated.
-
allocArrays
void allocArrays()
Handle lazy allocation of arrays.
-
newTable
private static int[] newTable(int size)
-
newEntries
private static long[] newEntries(int size)
-
hashTableMask
private int hashTableMask()
-
getHash
private static int getHash(long entry)
-
getNext
private static int getNext(long entry)
Returns the index, or UNSET if the pointer is "null"
-
swapNext
private static long swapNext(long entry, int newNext)
Returns a new entry value by changing the "next" index of an existing entry
-
add
public boolean add(E object)
-
insertEntry
void insertEntry(int entryIndex, E object, int hash)
Creates a fresh entry with the specified object at the specified position in the entry arrays.
-
resizeMeMaybe
private void resizeMeMaybe(int newSize)
Resizes the entries storage if necessary.
-
resizeEntries
void resizeEntries(int newCapacity)
Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.
-
resizeTable
private void resizeTable(int newCapacity)
-
contains
public boolean contains(java.lang.Object object)
-
remove
public boolean remove(java.lang.Object object)
-
remove
private boolean remove(java.lang.Object object, int hash)
-
moveLastEntry
void moveLastEntry(int dstIndex)
Moves the last entry in the entry array intodstIndex
, and nulls out its old position.
-
firstEntryIndex
int firstEntryIndex()
-
getSuccessor
int getSuccessor(int entryIndex)
-
adjustAfterRemove
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.
-
iterator
public java.util.Iterator<E> iterator()
-
spliterator
public java.util.Spliterator<E> spliterator()
-
forEach
public void forEach(java.util.function.Consumer<? super E> action)
- Specified by:
forEach
in interfacejava.lang.Iterable<E>
-
size
public int size()
-
isEmpty
public boolean isEmpty()
-
toArray
public java.lang.Object[] toArray()
-
toArray
public <T> T[] toArray(T[] a)
-
trimToSize
public void trimToSize()
Ensures that thisCompactHashSet
has the smallest representation in memory, given its current size.
-
clear
public void clear()
-
writeObject
private void writeObject(java.io.ObjectOutputStream stream) throws java.io.IOException
- Throws:
java.io.IOException
-
readObject
private void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, java.lang.ClassNotFoundException
- Throws:
java.io.IOException
java.lang.ClassNotFoundException
-
-