@Generated(date="2015-05-05T11:00:01+0200", value="KTypeHashSet.java") public class ObjectHashSet<KType> extends java.lang.Object implements ObjectLookupContainer<KType>, ObjectSet<KType>, Preallocable, java.lang.Cloneable
Object
s, implemented using using open addressing
with linear probing for collision resolution.
Note: read about important differences between hash and scatter sets.
ObjectScatterSet
,
HPPC interfaces diagramModifier and Type | Class and Description |
---|---|
protected class |
ObjectHashSet.EntryIterator
An iterator implementation for
iterator() . |
Modifier and Type | Field and Description |
---|---|
protected int |
assigned
The number of stored keys (assigned key slots), excluding the special
"empty" key, if any.
|
protected boolean |
hasEmptyKey
Special treatment for the "empty slot" key marker.
|
protected int |
keyMixer
We perturb hash values with a container-unique
seed to avoid problems with nearly-sorted-by-hash
values on iterations.
|
java.lang.Object[] |
keys
The hash array holding keys.
|
protected double |
loadFactor
The load factor for
keys . |
protected int |
mask
Mask for slot scans in
keys . |
protected HashOrderMixingStrategy |
orderMixer
Per-instance hash order mixing strategy.
|
protected int |
resizeAt
|
Constructor and Description |
---|
ObjectHashSet()
New instance with sane defaults.
|
ObjectHashSet(int expectedElements)
New instance with sane defaults.
|
ObjectHashSet(int expectedElements,
double loadFactor)
New instance with sane defaults.
|
ObjectHashSet(int expectedElements,
double loadFactor,
HashOrderMixingStrategy orderMixer)
New instance with the provided defaults.
|
ObjectHashSet(ObjectContainer<? extends KType> container)
New instance copying elements from another
ObjectContainer . |
Modifier and Type | Method and Description |
---|---|
boolean |
add(KType key)
Adds
k to the set. |
int |
addAll(java.lang.Iterable<? extends ObjectCursor<? extends KType>> iterable)
Adds all elements from the given iterable to this set.
|
int |
addAll(KType... elements)
Adds all elements from the given list (vararg) to this set.
|
int |
addAll(ObjectContainer<? extends KType> container)
Adds all elements from the given
ObjectContainer to this set. |
protected void |
allocateBuffers(int arraySize)
Allocate new internal buffers.
|
protected void |
allocateThenInsertThenRehash(int slot,
KType pendingKey)
This method is invoked when there is a new key to be inserted into
the buffer but there is not enough empty slots to do so.
|
void |
clear()
Removes all elements from this collection.
|
ObjectHashSet<KType> |
clone() |
boolean |
contains(KType key)
Lookup a given element in the container.
|
void |
ensureCapacity(int expectedElements)
Ensure this container can hold at least the
given number of elements without resizing its buffers.
|
boolean |
equals(java.lang.Object obj) |
protected boolean |
equals(java.lang.Object v1,
java.lang.Object v2) |
<T extends ObjectPredicate<? super KType>> |
forEach(T predicate)
Applies a
predicate to container elements as long, as the
predicate returns true . |
<T extends ObjectProcedure<? super KType>> |
forEach(T procedure)
Applies a
procedure to all container elements. |
static <KType> ObjectHashSet<KType> |
from(KType... elements)
Create a set from a variable number of arguments or an array of
Object . |
int |
hashCode() |
protected int |
hashKey(KType key)
Returns a hash code for the given key.
|
boolean |
indexExists(int index) |
KType |
indexGet(int index)
Returns the exact value of the existing key.
|
void |
indexInsert(int index,
KType key)
Inserts a key for an index that is not present in the set.
|
int |
indexOf(KType key)
Returns a logical "index" of a given key that can be used to speed up
follow-up logic in certain scenarios (conditional logic).
|
KType |
indexReplace(int index,
KType equivalentKey)
Replaces the existing equivalent key with the given one and returns any previous value
stored for that key.
|
boolean |
isEmpty()
Shortcut for
size() == 0 . |
java.util.Iterator<ObjectCursor<KType>> |
iterator()
Returns an iterator to a cursor traversing the collection.
|
protected void |
rehash(KType[] fromKeys)
Rehash from old buffers to new buffers.
|
void |
release()
Removes all elements from the collection and additionally releases any
internal buffers.
|
boolean |
remove(KType key)
An alias for the (preferred)
removeAll(KType) . |
int |
removeAll(KType key)
Removes all occurrences of
e from this collection. |
int |
removeAll(ObjectLookupContainer<? super KType> c)
Default implementation uses a predicate for removal.
|
int |
removeAll(ObjectPredicate<? super KType> predicate)
Removes all elements in this collection for which the given predicate
returns
true . |
int |
retainAll(ObjectLookupContainer<? super KType> c)
Default implementation uses a predicate for retaining.
|
int |
retainAll(ObjectPredicate<? super KType> predicate)
Default implementation redirects to
ObjectCollection.removeAll(ObjectPredicate) and
negates the predicate. |
protected void |
shiftConflictingKeys(int gapSlot)
Shift all the slot-conflicting keys allocated to (and including)
slot . |
int |
size()
Return the current number of elements in this container.
|
java.lang.Object[] |
toArray()
Default implementation of copying to an array.
|
<T> T[] |
toArray(java.lang.Class<T> componentClass)
Copies all elements of this container to a dynamically created array of the
given component type.
|
java.lang.String |
toString()
Convert the contents of this container to a human-friendly string.
|
protected double |
verifyLoadFactor(double loadFactor)
Validate load factor range and return it.
|
finalize, getClass, notify, notifyAll, wait, wait, wait
removeAll, retainAll, retainAll
toArray
public java.lang.Object[] keys
protected int assigned
size()
,
hasEmptyKey
protected int mask
keys
.protected int keyMixer
hashKey(KType)
,
"http://issues.carrot2.org/browse/HPPC-80",
"http://issues.carrot2.org/browse/HPPC-103"protected int resizeAt
protected boolean hasEmptyKey
protected double loadFactor
keys
.protected HashOrderMixingStrategy orderMixer
keyMixer
public ObjectHashSet()
public ObjectHashSet(int expectedElements)
public ObjectHashSet(int expectedElements, double loadFactor)
public ObjectHashSet(int expectedElements, double loadFactor, HashOrderMixingStrategy orderMixer)
expectedElements
- The expected number of elements guaranteed not to cause a rehash (inclusive).loadFactor
- The load factor for internal buffers. Insane load factors (zero, full capacity)
are rejected by verifyLoadFactor(double)
.orderMixer
- Hash key order mixing strategy. See HashOrderMixing
for predefined
implementations. Use constant mixers only if you understand the potential
consequences.public ObjectHashSet(ObjectContainer<? extends KType> container)
ObjectContainer
.public boolean add(KType key)
k
to the set.@SafeVarargs public final int addAll(KType... elements)
public int addAll(ObjectContainer<? extends KType> container)
ObjectContainer
to this set.public int addAll(java.lang.Iterable<? extends ObjectCursor<? extends KType>> iterable)
public java.lang.Object[] toArray()
toArray
in interface ObjectContainer<KType>
public boolean remove(KType key)
removeAll(KType)
.public int removeAll(KType key)
e
from this collection.removeAll
in interface ObjectCollection<KType>
key
- Element to be removed from this collection, if present.public int removeAll(ObjectPredicate<? super KType> predicate)
true
.removeAll
in interface ObjectCollection<KType>
public boolean contains(KType key)
contains
in interface ObjectContainer<KType>
contains
in interface ObjectLookupContainer<KType>
true
if this container has an element equal to
e
.public void clear()
clear
in interface ObjectCollection<KType>
ObjectCollection.release()
public void release()
ObjectCollection.clear()
should be a better alternative since it'll avoid
reallocation.release
in interface ObjectCollection<KType>
ObjectCollection.clear()
public boolean isEmpty()
size() == 0
.isEmpty
in interface ObjectContainer<KType>
public void ensureCapacity(int expectedElements)
ensureCapacity
in interface Preallocable
expectedElements
- The total number of elements, inclusive.public int size()
O(n)
time, although
implementing classes should try to maintain the current size and return in
constant time.size
in interface ObjectContainer<KType>
public int hashCode()
hashCode
in class java.lang.Object
public boolean equals(java.lang.Object obj)
equals
in class java.lang.Object
public ObjectHashSet<KType> clone()
clone
in class java.lang.Object
public java.util.Iterator<ObjectCursor<KType>> iterator()
The iterator is implemented as a cursor and it returns the same cursor
instance on every call to Iterator.next()
(to avoid boxing of
primitive types). To read the current list's value (or index in the list)
use the cursor's public fields. An example is shown below.
for (ObjectCursor<Object> c : container) { System.out.println("index=" + c.index + " value=" + c.value); }
iterator
in interface ObjectContainer<KType>
iterator
in interface java.lang.Iterable<ObjectCursor<KType>>
public <T extends ObjectProcedure<? super KType>> T forEach(T procedure)
procedure
to all container elements. Returns the
argument (any subclass of ObjectProcedure
. This lets the caller to
call methods of the argument by chaining the call (even if the argument is
an anonymous type) to retrieve computed values, for example (IntContainer):
int count = container.forEach(new IntProcedure() { int count; // this is a field declaration in an anonymous class. public void apply(int value) { count++; } }).count;
forEach
in interface ObjectContainer<KType>
public <T extends ObjectPredicate<? super KType>> T forEach(T predicate)
predicate
to container elements as long, as the
predicate returns true
. The iteration is interrupted
otherwise.forEach
in interface ObjectContainer<KType>
@SafeVarargs public static <KType> ObjectHashSet<KType> from(KType... elements)
Object
. The elements are copied from the argument to the
internal buffer.protected int hashKey(KType key)
keyMixer
to differentiate hash order of keys between hash containers. Helps
alleviate problems resulting from linear conflict resolution in open
addressing.
The output from this function should evenly distribute keys across the
entire integer range.public int indexOf(KType key)
key
- The key to locate in the set.indexExists(int)
,
indexGet(int)
,
indexInsert(int, KType)
,
indexReplace(int, KType)
public boolean indexExists(int index)
index
- The index of a given key, as returned from indexOf(KType)
.true
if the index corresponds to an existing key
or false otherwise. This is equivalent to checking whether the index is
a positive value (existing keys) or a negative value (non-existing keys).indexOf(KType)
public KType indexGet(int index)
index
- The index of an existing key.java.lang.AssertionError
- If assertions are enabled and the index does
not correspond to an existing key.indexOf(KType)
public KType indexReplace(int index, KType equivalentKey)
index
- The index of an existing key.equivalentKey
- The key to put in the set as a replacement. Must be equivalent to
the key currently stored at the provided index.java.lang.AssertionError
- If assertions are enabled and the index does
not correspond to an existing key.indexOf(KType)
public void indexInsert(int index, KType key)
index
- The index of a previously non-existing key, as returned from
indexOf(KType)
.java.lang.AssertionError
- If assertions are enabled and the index does
not correspond to an existing key.indexOf(KType)
protected double verifyLoadFactor(double loadFactor)
protected void rehash(KType[] fromKeys)
protected void allocateBuffers(int arraySize)
protected void allocateThenInsertThenRehash(int slot, KType pendingKey)
protected void shiftConflictingKeys(int gapSlot)
slot
.public int removeAll(ObjectLookupContainer<? super KType> c)
removeAll
in interface ObjectCollection<KType>
public int retainAll(ObjectLookupContainer<? super KType> c)
retainAll
in interface ObjectCollection<KType>
public int retainAll(ObjectPredicate<? super KType> predicate)
ObjectCollection.removeAll(ObjectPredicate)
and
negates the predicate.retainAll
in interface ObjectCollection<KType>
public <T> T[] toArray(java.lang.Class<T> componentClass)
ObjectContainer
toArray
in interface ObjectContainer<KType>
public java.lang.String toString()
toString
in class java.lang.Object
protected boolean equals(java.lang.Object v1, java.lang.Object v2)
Copyright © 2015 Carrot Search s.c.. All Rights Reserved.