ObjectHashSet (HPPC-RT v0.7.5 API Documentation)

java.lang.Object
- com.carrotsearch.hppcrt.AbstractObjectCollection<KType>
- - com.carrotsearch.hppcrt.sets.ObjectHashSet<KType>

All Implemented Interfaces:

ObjectCollection<KType>, ObjectContainer<KType>, ObjectLookupContainer<KType>, ObjectSet<KType>, java.lang.Cloneable, java.lang.Iterable<ObjectCursor<KType>>

Direct Known Subclasses:

ObjectIdentityHashSet
```
@Generated(date="2017-07-11T19:16:33+0200",
           value="KTypeHashSet.java")
public class ObjectHashSet<KType>
extends AbstractObjectCollection<KType>
implements ObjectLookupContainer<KType>, ObjectSet<KType>, java.lang.Cloneable
```
A hash set of Objects, implemented using using open addressing with linear probing for collision resolution.
In addition, the hashing strategy can be changed by overriding (equalKeys(Object, Object) and hashKey(Object)) together, which then replaces the usual (equals(Object) and hashCode()) from the keys themselves. This is useful to define the equivalence of keys when the user has no control over the keys implementation.

The internal buffers of this implementation (keys, etc...) are always allocated to the nearest size that is a power of two. When the capacity exceeds the given load factor, the buffer size is doubled.

This implementation supports null keys.

Important note. The implementation uses power-of-two tables and linear probing, which may cause poor performance (many collisions) if hash values are not properly distributed.
Robin-Hood hashing algorithm is also used to minimize variance in insertion and search-related operations, for an all-around smother operation at the cost of smaller peak performance:

- Pedro Celis (1986) for the original Robin-Hood hashing paper,

- MoonPolySoft/Cliff Moon for the initial Robin-hood on HPPC implementation,

- Vincent Sonnier for the present implementation using cached hashes.

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

class ObjectHashSet.EntryIterator
An iterator implementation for iterator().

Nested Classes
Modifier and Type	Class and Description
`class`	`ObjectHashSet.EntryIterator` An iterator implementation for `iterator()`.

Field Summary

Fields
Modifier and Type	Field and Description
`boolean`	`allocatedDefaultKey` True if key = 0/null is in the map.
`protected int`	`assigned` Cached number of assigned slots in `keys`.
`protected IteratorPool<ObjectCursor<KType>,ObjectHashSet.EntryIterator>`	`entryIteratorPool` internal pool of EntryIterator
`protected int[]`	`hash_cache` * Caches the hash value = hash(keys[i]) & mask, if keys[i] !
`java.lang.Object[]`	`keys` Hash-indexed array holding all set entries.
`protected double`	`loadFactor` The load factor for this map (fraction of allocated slots before the buffers must be rehashed or reallocated).

Fields inherited from class com.carrotsearch.hppcrt.AbstractObjectCollection
containsNegateTestPredicate, containsTestPredicate, negatePredicate, testContainer, testPredicate

Constructor Summary

Constructors
Constructor and Description
`ObjectHashSet()` Default constructor: Creates a hash set with the default capacity of `Containers.DEFAULT_EXPECTED_ELEMENTS`, load factor of `HashContainers.DEFAULT_LOAD_FACTOR`.
`ObjectHashSet(int initialCapacity)` Creates a hash set with the given capacity, load factor of `HashContainers.DEFAULT_LOAD_FACTOR`.
`ObjectHashSet(int initialCapacity, double loadFactor)` Creates a hash set with the given capacity and load factor.
`ObjectHashSet(ObjectContainer<KType> container)` Creates a hash set from elements of another container.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`int`	`add(KType... elements)` Vararg-signature method for adding elements to this set.
`boolean`	`add(KType key)` Adds `k` to the set.
`int`	`add(KType e1, KType e2)` Adds two elements to the set.
`int`	`addAll(java.lang.Iterable<? extends ObjectCursor<? extends KType>> iterable)` Adds all elements from a given iterable to this set.
`int`	`addAll(ObjectContainer<? extends KType> container)` Adds all elements from a given container to this set.
`int`	`capacity()` Return the maximum number of elements this container is guaranteed to hold without reallocating.
`void`	`clear()` Removes all elements from this collection.
`ObjectHashSet<KType>`	`clone()`
`boolean`	`contains(KType key)` Lookup a given element in the container.
`protected boolean`	`equalKeys(KType a, KType b)` Override this method together with `hashKey(Object)` to customize the hashing strategy.
`boolean`	`equals(java.lang.Object obj)`
`<T extends ObjectPredicate<? super KType>> T`	`forEach(T predicate)` Applies a `predicate` to container elements, as long as the predicate returns `true`.
`<T extends ObjectProcedure<? super KType>> T`	`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`.
`static <KType> ObjectHashSet<KType>`	`from(ObjectContainer<KType> container)` Create a set from elements of another container.
`int`	`hashCode()`
`protected int`	`hashKey(KType key)` Override this method, together with `equalKeys(Object, Object)` to customize the hashing strategy.
`ObjectHashSet.EntryIterator`	`iterator()` Returns an iterator to a cursor traversing the collection.
`static <KType> ObjectHashSet<KType>`	`newInstance()` Create a new hash set with default parameters (shortcut instead of using a constructor).
`static <KType> ObjectHashSet<KType>`	`newInstance(int initialCapacity, double loadFactor)` Returns a new object of this class with no need to declare generic type (shortcut instead of using a constructor).
`boolean`	`remove(KType key)` Remove all elements of the set matching key.
`int`	`removeAll(KType key)` Removes all occurrences of `e` from this collection.
`int`	`removeAll(ObjectPredicate<? super KType> predicate)` Removes all elements in this collection for which the given predicate returns `true`.
`int`	`size()` Return the current number of elements in this container.
`KType[]`	`toArray(KType[] target)` Default implementation for: Copies all elements of this container to an existing array of the same type.

Methods inherited from class com.carrotsearch.hppcrt.AbstractObjectCollection
isEmpty, removeAll, retainAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface com.carrotsearch.hppcrt.ObjectCollection
removeAll, retainAll, retainAll

Methods inherited from interface com.carrotsearch.hppcrt.ObjectContainer
isEmpty, toArray, toArray

Methods inherited from interface java.lang.Iterable
forEach, spliterator

- Field Detail
  - keys
```
public java.lang.Object[] keys
```
    Hash-indexed array holding all set entries.
    Direct set iteration: iterate {keys[i]} for i in [0; keys.length[ where keys[i] != 0/null, then also {0/null} is in the set if allocatedDefaultKey = true.
  - hash_cache
```
protected int[] hash_cache
```
    * Caches the hash value = hash(keys[i]) & mask, if keys[i] != 0/null, for every index i. * @see #assigned
  - allocatedDefaultKey
```
public boolean allocatedDefaultKey
```
    True if key = 0/null is in the map.
  - assigned
```
protected int assigned
```
    Cached number of assigned slots in keys.
  - loadFactor
```
protected final double loadFactor
```
    The load factor for this map (fraction of allocated slots before the buffers must be rehashed or reallocated).
  - entryIteratorPool
```
protected final IteratorPool<ObjectCursor<KType>,ObjectHashSet.EntryIterator> entryIteratorPool
```
    internal pool of EntryIterator
- Constructor Detail
  - ObjectHashSet
```
public ObjectHashSet()
```
    Default constructor: Creates a hash set with the default capacity of Containers.DEFAULT_EXPECTED_ELEMENTS, load factor of HashContainers.DEFAULT_LOAD_FACTOR.
  - ObjectHashSet
```
public ObjectHashSet(int initialCapacity)
```
    Creates a hash set with the given capacity, load factor of HashContainers.DEFAULT_LOAD_FACTOR.
  - ObjectHashSet
```
public ObjectHashSet(int initialCapacity,
                     double loadFactor)
```
    Creates a hash set with the given capacity and load factor.
  - ObjectHashSet
```
public ObjectHashSet(ObjectContainer<KType> container)
```
    Creates a hash set from elements of another container. Default load factor is used.
- Method Detail
  - hashKey
```
protected int hashKey(KType key)
```
    Override this method, together with equalKeys(Object, Object) to customize the hashing strategy. Note that this method is guaranteed to be called with a non-null key argument. By default, this method calls key.hashCode().
    
    Parameters:
    
    key - Object to be hashed.
    
    Returns:
    
    the hashed value of key, following the same semantic as hashCode();
    
    See Also:
    
    hashCode(), equalKeys(Object, Object)
  - equalKeys
```
protected boolean equalKeys(KType a,
                            KType b)
```
    Override this method together with hashKey(Object) to customize the hashing strategy. Note that this method is guaranteed to be called with both non-null arguments. By default, this method calls a.#equals(b).
    
    Parameters:
    
    a - not-null Object to be compared
    
    b - not-null Object to be compared
    
    Returns:
    
    true if a and b are considered equal, following the same semantic as equals(Object).
    
    See Also:
    
    equals(Object), hashKey(Object)
  - add
```
public boolean add(KType key)
```
    Adds k to the set.
    
    Specified by:
    
    add in interface ObjectSet<KType>
    
    Returns:
    
    Returns true if this element was not part of the set before. Returns false if an equal element is already part of the set, and leaves the set unchanged. .
  - add
```
public int add(KType e1,
               KType e2)
```
    Adds two elements to the set.
  - add
```
public int add(KType... elements)
```
    Vararg-signature method for adding elements to this set.
    This method is handy, but costly if used in tight loops (anonymous array passing)
    
    Returns:
    
    Returns the number of elements that were added to the set (were not present in the set).
  - addAll
```
public int addAll(ObjectContainer<? extends KType> container)
```
    Adds all elements from a given container to this set.
    
    Specified by:
    
    addAll in interface ObjectSet<KType>
    
    Returns:
    
    Returns the number of elements actually added as a result of this call (not previously present in the set).
  - addAll
```
public int addAll(java.lang.Iterable<? extends ObjectCursor<? extends KType>> iterable)
```
    Adds all elements from a given iterable to this set.
    
    Specified by:
    
    addAll in interface ObjectSet<KType>
    
    Returns:
    
    Returns the number of elements actually added as a result of this call (not previously present in the set).
  - removeAll
```
public int removeAll(KType key)
```
    Removes all occurrences of e from this collection.
    
    Specified by:
    
    removeAll in interface ObjectCollection<KType>
    
    Parameters:
    
    key - Element to be removed from this collection, if present.
    
    Returns:
    
    The number of removed elements as a result of this call.
  - remove
```
public boolean remove(KType key)
```
    Remove all elements of the set matching key. Returns true if key was present in the set and has been successfully removed. This is indeed an alias for ObjectCollection.removeAll(key) > 0
    
    Specified by:
    
    remove in interface ObjectSet<KType>
    
    See Also:
    
    ObjectCollection.removeAll(KType)
  - contains
```
public boolean contains(KType key)
```
    Lookup a given element in the container. This operation has no speed guarantees (may be linear with respect to the size of this container).
    
    Specified by:
    
    contains in interface ObjectContainer<KType>
    
    Specified by:
    
    contains in interface ObjectLookupContainer<KType>
    
    Returns:
    
    Returns true if this container has an element equal to e.
  - clear
```
public void clear()
```
    Removes all elements from this collection.
    Does not release internal buffers.
    
    Specified by:
    
    clear in interface ObjectCollection<KType>
  - size
```
public int size()
```
    Return the current number of elements in this container. The time for calculating the container's size may take O(n) time, although implementing classes should try to maintain the current size and return in constant time.
    
    Specified by:
    
    size in interface ObjectContainer<KType>
  - capacity
```
public int capacity()
```
    Return the maximum number of elements this container is guaranteed to hold without reallocating. The time for calculating the container's capacity may take O(n) time.
    
    Specified by:
    
    capacity in interface ObjectContainer<KType>
  - hashCode
```
public int hashCode()
```
    Overrides:
    
    hashCode in class java.lang.Object
  - equals
```
public boolean equals(java.lang.Object obj)
```
    Overrides:
    
    equals in class java.lang.Object
  - iterator
```
public ObjectHashSet.EntryIterator iterator()
```
    Returns an iterator to a cursor traversing the collection. The order of traversal is not defined. More than one cursor may be active at a time. The behavior of iterators is undefined if structural changes are made to the underlying collection.
    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);
 }
 
```
    Specified by:
    
    iterator in interface ObjectContainer<KType>
    
    Specified by:
    
    iterator in interface java.lang.Iterable<ObjectCursor<KType>>
  - forEach
```
public <T extends ObjectProcedure<? super KType>> T forEach(T procedure)
```
    Applies a 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;
 
```
    Specified by:
    
    forEach in interface ObjectContainer<KType>
  - toArray
```
public KType[] toArray(KType[] target)
```
    Default implementation for: Copies all elements of this container to an existing array of the same type.
    
    Specified by:
    
    toArray in interface ObjectContainer<KType>
    
    Overrides:
    
    toArray in class AbstractObjectCollection<KType>
    
    Parameters:
    
    target - The target array must be large enough to hold all elements, i.e >= ObjectContainer.size().
    
    Returns:
    
    Returns the target argument for chaining.
  - clone
```
public ObjectHashSet<KType> clone()
```
    Overrides:
    
    clone in class java.lang.Object
  - forEach
```
public <T extends ObjectPredicate<? super KType>> T forEach(T predicate)
```
    Applies a predicate to container elements, as long as the predicate returns true. The iteration is interrupted otherwise.
    
    Specified by:
    
    forEach in interface ObjectContainer<KType>
  - removeAll
```
public int removeAll(ObjectPredicate<? super KType> predicate)
```
    Removes all elements in this collection for which the given predicate returns true.
    
    Specified by:
    
    removeAll in interface ObjectCollection<KType>
    
    Returns:
    
    Returns the number of removed elements.
  - from
```
public static <KType> ObjectHashSet<KType> from(KType... elements)
```
    Create a set from a variable number of arguments or an array of Object.
  - from
```
public static <KType> ObjectHashSet<KType> from(ObjectContainer<KType> container)
```
    Create a set from elements of another container.
  - newInstance
```
public static <KType> ObjectHashSet<KType> newInstance()
```
    Create a new hash set with default parameters (shortcut instead of using a constructor).
  - newInstance
```
public static <KType> ObjectHashSet<KType> newInstance(int initialCapacity,
                                                       double loadFactor)
```
    Returns a new object of this class with no need to declare generic type (shortcut instead of using a constructor).

Class ObjectHashSet<KType>

Nested Class Summary

Field Summary

Fields inherited from class com.carrotsearch.hppcrt.AbstractObjectCollection

Constructor Summary

Method Summary

Methods inherited from class com.carrotsearch.hppcrt.AbstractObjectCollection

Methods inherited from class java.lang.Object

Methods inherited from interface com.carrotsearch.hppcrt.ObjectCollection

Methods inherited from interface com.carrotsearch.hppcrt.ObjectContainer

Methods inherited from interface java.lang.Iterable

Field Detail

keys

hash_cache

allocatedDefaultKey

assigned

loadFactor

entryIteratorPool

Constructor Detail

ObjectHashSet

ObjectHashSet

ObjectHashSet

ObjectHashSet

Method Detail

hashKey

equalKeys

add

add

add

addAll

addAll

removeAll

remove

contains

clear

size

capacity

hashCode

equals

iterator

forEach

toArray

clone

forEach

removeAll

from

from

newInstance

newInstance