com.carrotsearch.hppc
Class ObjectOpenHashSet<KType>

java.lang.Object
  extended by com.carrotsearch.hppc.ObjectOpenHashSet<KType>
All Implemented Interfaces:
ObjectCollection<KType>, ObjectContainer<KType>, ObjectLookupContainer<KType>, ObjectSet<KType>, java.lang.Cloneable, java.lang.Iterable<ObjectCursor<KType>>

@Generated(date="2011-11-28T23:36:05+0000",
           value="HPPC generated from: ObjectOpenHashSet.java")
public class ObjectOpenHashSet<KType>
extends java.lang.Object
implements ObjectLookupContainer<KType>, ObjectSet<KType>, java.lang.Cloneable

A hash set of KTypes, implemented using using open addressing with linear probing for collision resolution.

The internal buffers of this implementation (keys), allocated) 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.

A brief comparison of the API against the Java Collections framework:

Java Collections HashSet and HPPC ObjectOpenHashSet, related methods.
java.util.HashSet ObjectOpenHashSet
boolean add(E) boolean add(E)
boolean remove(E) int removeAllOccurrences(E)
size, clear, isEmptysize, clear, isEmpty
contains(E) contains(E), lget()
iterator iterator over set values, pseudo-closures

This implementation supports null keys.

Important node. The implementation uses power-of-two tables and linear probing, which may cause poor performance (many collisions) if hash values are not properly distributed. This implementation uses MurmurHash3 for rehashing keys.

Author:
This code is inspired by the collaboration and implementation in the fastutil project.

Field Summary
 boolean[] allocated
          Information if an entry (slot) in the keys table is allocated or empty.
 int assigned
          Cached number of assigned slots in allocated.
static int DEFAULT_CAPACITY
          Default capacity.
static float DEFAULT_LOAD_FACTOR
          Default load factor.
 KType[] keys
          Hash-indexed array holding all set entries.
 float loadFactor
          The load factor for this set (fraction of allocated or deleted slots before the buffers must be rehashed or reallocated).
static int MIN_CAPACITY
          Minimum capacity for the set.
 
Constructor Summary
ObjectOpenHashSet()
          Creates a hash set with the default capacity of 16, load factor of 0.75f.
ObjectOpenHashSet(int initialCapacity)
          Creates a hash set with the given capacity, load factor of 0.75f.
ObjectOpenHashSet(int initialCapacity, float loadFactor)
          Creates a hash set with the given capacity and load factor.
ObjectOpenHashSet(ObjectContainer<KType> container)
          Creates a hash set from elements of another container.
 
Method Summary
 int add(KType... elements)
          Vararg-signature method for adding elements to this set.
 boolean add(KType e)
          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.
 void clear()
          Removes all elements from this collection.
 ObjectOpenHashSet<KType> clone()
          
 boolean contains(KType key)
          Lookup a given element in the container.
 boolean equals(java.lang.Object obj)
          Compares the specified object with this set for equality.
<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> ObjectOpenHashSet<KType>
from(KType... elements)
          Create a set from a variable number of arguments or an array of KType.
static
<KType> ObjectOpenHashSet<KType>
from(ObjectContainer<KType> container)
          Create a set from elements of another container.
 int hashCode()
          
 boolean isEmpty()
          Shortcut for size() == 0.
 java.util.Iterator<ObjectCursor<KType>> iterator()
          Returns an iterator to a cursor traversing the collection.
 KType lget()
          Returns the last value saved in a call to contains(KType).
static
<KType> ObjectOpenHashSet<KType>
newInstance()
          Returns a new object of this class with no need to declare generic type (shortcut instead of using a constructor).
static
<KType> ObjectOpenHashSet<KType>
newInstanceWithCapacity(int initialCapacity, float loadFactor)
          Returns a new object of this class with no need to declare generic type (shortcut instead of using a constructor).
protected  int nextCapacity(int current)
          Return the next possible capacity, counting from the current buffers' size.
 boolean remove(KType key)
          An alias for the (preferred) removeAllOccurrences(KType).
 int removeAll(ObjectLookupContainer<? extends 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 removeAllOccurrences(KType key)
          Removes all occurrences of e from this collection.
 int retainAll(ObjectLookupContainer<? extends 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  int roundCapacity(int requestedCapacity)
          Round the capacity to the next allowed value.
protected  void shiftConflictingKeys(int slotCurr)
          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()
          Copies all elements from this container to an Object array.
 KType[] toArray(java.lang.Class<? super KType> clazz)
          Default implementation of copying to an array.
 java.lang.String toString()
          Convert the contents of this container to a human-friendly string.
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface com.carrotsearch.hppc.ObjectCollection
removeAll, retainAll, retainAll
 
Methods inherited from interface com.carrotsearch.hppc.ObjectContainer
toArray
 

Field Detail

DEFAULT_CAPACITY

public static final int DEFAULT_CAPACITY
Default capacity.

See Also:
Constant Field Values

MIN_CAPACITY

public static final int MIN_CAPACITY
Minimum capacity for the set.

See Also:
Constant Field Values

DEFAULT_LOAD_FACTOR

public static final float DEFAULT_LOAD_FACTOR
Default load factor.

See Also:
Constant Field Values

keys

public KType[] keys
Hash-indexed array holding all set entries.

See Also:
allocated

allocated

public boolean[] allocated
Information if an entry (slot) in the keys table is allocated or empty.

See Also:
assigned

assigned

public int assigned
Cached number of assigned slots in allocated.


loadFactor

public final float loadFactor
The load factor for this set (fraction of allocated or deleted slots before the buffers must be rehashed or reallocated).

Constructor Detail

ObjectOpenHashSet

public ObjectOpenHashSet()
Creates a hash set with the default capacity of 16, load factor of 0.75f. `


ObjectOpenHashSet

public ObjectOpenHashSet(int initialCapacity)
Creates a hash set with the given capacity, load factor of 0.75f.


ObjectOpenHashSet

public ObjectOpenHashSet(int initialCapacity,
                         float loadFactor)
Creates a hash set with the given capacity and load factor.


ObjectOpenHashSet

public ObjectOpenHashSet(ObjectContainer<KType> container)
Creates a hash set from elements of another container. Default load factor is used.

Method Detail

add

public boolean add(KType e)
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 part of the set, and replaces the existing equal element with the argument (if keys are object types).

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 final int addAll(ObjectContainer<? extends KType> container)
Adds all elements from a given container to this set.

Returns:
Returns the number of elements actually added as a result of this call (not previously present in the set).

addAll

public final int addAll(java.lang.Iterable<? extends ObjectCursor<? extends KType>> iterable)
Adds all elements from a given iterable to this set.

Returns:
Returns the number of elements actually added as a result of this call (not previously present in the set).

removeAllOccurrences

public int removeAllOccurrences(KType key)
Removes all occurrences of e from this collection.

Specified by:
removeAllOccurrences 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)
An alias for the (preferred) removeAllOccurrences(KType).


shiftConflictingKeys

protected final void shiftConflictingKeys(int slotCurr)
Shift all the slot-conflicting keys allocated to (and including) slot.


lget

public KType lget()
Returns the last value saved in a call to contains(KType).

See Also:
contains(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).

Saves the associated value for fast access using lget().

 if (map.contains(key))
   value = map.lget(); 
 

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.

roundCapacity

protected int roundCapacity(int requestedCapacity)
Round the capacity to the next allowed value.


nextCapacity

protected int nextCapacity(int current)
Return the next possible capacity, counting from the current buffers' size.


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>

isEmpty

public boolean isEmpty()
Shortcut for size() == 0.

Specified by:
isEmpty in interface ObjectContainer<KType>

hashCode

public int hashCode()

Specified by:
hashCode in interface ObjectSet<KType>
Overrides:
hashCode in class java.lang.Object
Returns:
A hash code of elements stored in the set. The hash code is defined identically to Set.hashCode() (sum of hash codes of elements within the set). Because sum is commutative, this ensures that different order of elements in a set does not affect the hash code.

equals

public boolean equals(java.lang.Object obj)
Compares the specified object with this set for equality. Returns true if and only if the specified object is also a ObjectSet and both objects contains exactly the same objects.

Specified by:
equals in interface ObjectSet<KType>
Overrides:
equals in class java.lang.Object

iterator

public java.util.Iterator<ObjectCursor<KType>> 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<KType> 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 final java.lang.Object[] toArray()
Copies all elements from this container to an Object array. If you need an array of the type identical with this container's generic type, use ObjectContainer.toArray(Class).

Specified by:
toArray in interface ObjectContainer<KType>
See Also:
ObjectContainer.toArray(Class)

clone

public ObjectOpenHashSet<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>

from

public static <KType> ObjectOpenHashSet<KType> from(KType... elements)
Create a set from a variable number of arguments or an array of KType. The elements are copied from the argument to the internal buffer.


from

public static <KType> ObjectOpenHashSet<KType> from(ObjectContainer<KType> container)
Create a set from elements of another container.


newInstance

public static <KType> ObjectOpenHashSet<KType> newInstance()
Returns a new object of this class with no need to declare generic type (shortcut instead of using a constructor).


newInstanceWithCapacity

public static <KType> ObjectOpenHashSet<KType> newInstanceWithCapacity(int initialCapacity,
                                                                       float loadFactor)
Returns a new object of this class with no need to declare generic type (shortcut instead of using a constructor).


removeAll

public int removeAll(ObjectLookupContainer<? extends KType> c)
Default implementation uses a predicate for removal.

Specified by:
removeAll in interface ObjectCollection<KType>
Returns:
Returns the number of removed elements.

retainAll

public int retainAll(ObjectLookupContainer<? extends KType> c)
Default implementation uses a predicate for retaining.

Specified by:
retainAll in interface ObjectCollection<KType>
Returns:
Returns the number of removed elements.

retainAll

public int retainAll(ObjectPredicate<? super KType> predicate)
Default implementation redirects to ObjectCollection.removeAll(ObjectPredicate) and negates the predicate.

Specified by:
retainAll in interface ObjectCollection<KType>

toArray

public KType[] toArray(java.lang.Class<? super KType> clazz)
Default implementation of copying to an array.

Specified by:
toArray in interface ObjectContainer<KType>

toString

public java.lang.String toString()
Convert the contents of this container to a human-friendly string.

Overrides:
toString in class java.lang.Object


Copyright © 2011 Carrot Search s.c.. All Rights Reserved.