org.apache.spark.util.collection
OpenHashSet
Related Doc:
package collection
Add an element to the set.
Add an element to the set. If the set is over capacity after the insertion, grow the set and rehash all elements.
Add an element to the set.
Add an element to the set. This one differs from add in that it doesn't trigger rehashing. The caller is responsible for calling rehashIfNeeded.
Use (retval & POSITION_MASK) to get the actual position, and (retval & NONEXISTENCE_MASK) == 0 for prior existence.
The position where the key is placed, plus the highest order bit is set if the key does not exists previously.
The capacity of the set (i.e.
The capacity of the set (i.e. size of the underlying array).
Return true if this set contains the specified element.
Return the position of the element in the underlying array, or INVALID_POS if it is not found.
Return the value at the specified position.
Return the value at the specified position.
Return the next position with an element stored, starting from the given position inclusively.
Rehash the set if it is overloaded.
Rehash the set if it is overloaded.
A parameter unused in the function, but to force the Scala compiler to specialize this method.
Callback invoked when we are allocating a new, larger array.
Callback invoked when we move the key from one position (in the old data array) to a new position (in the new data array).
Number of elements in the set.
A simple, fast hash set optimized for non-null insertion-only use case, where keys are never removed.
The underlying implementation uses Scala compiler's specialization to generate optimized storage for two primitive types (Long and Int). It is much faster than Java's standard HashSet while incurring much less memory overhead. This can serve as building blocks for higher level data structures such as an optimized HashMap.
This OpenHashSet is designed to serve as building blocks for higher level data structures such as an optimized hash map. Compared with standard hash set implementations, this class provides its various callbacks interfaces (e.g. allocateFunc, moveFunc) and interfaces to retrieve the position of a key in the underlying array.
It uses quadratic probing with a power-of-2 hash table size, which is guaranteed to explore all spaces for each key (see http://en.wikipedia.org/wiki/Quadratic_probing).