org.apache.flink.table.runtime.util.collections

Class OptimizableHashSet

java.lang.Object

org.apache.flink.table.runtime.util.collections.OptimizableHashSet

Direct Known Subclasses:

DoubleHashSet, FloatHashSet, IntHashSet, LongHashSet, ObjectHashSet, ShortHashSet

public abstract class OptimizableHashSet
extends Object

A type-specific hash set with with a fast, small-footprint implementation. Refer to the implementation of fastutil.

Instances of this class use a hash table to represent a set. The table is enlarged as needed by doubling its size when new entries are created.

The difference with fastutil is that if the range of the maximum and minimum values is small or the data is dense, a Dense array will be used to greatly improve the access speed.

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	containsNull Is this set has a null key.
protected boolean	containsZero Is this set has a zero key.
static int	DEFAULT_INITIAL_SIZE The initial default size of a hash table.
static float	DEFAULT_LOAD_FACTOR The default load factor of a hash table.
static int	DENSE_THRESHOLD Decide whether to convert to dense mode if it does not require more memory or could fit within L1 cache.
protected float	f The acceptable load factor.
protected boolean	isDense Is now dense mode.
protected int	mask The mask for wrapping a position counter.
protected int	maxFill Threshold after which we rehash.
protected int	n The current table size.
protected int	size Number of entries in the set.
protected boolean[]	used Used array for dense mode.

Constructor Summary

Constructors

Constructor and Description
OptimizableHashSet(int expected, float f)

Method Summary

Modifier and Type	Method and Description
void	addNull() Add a null key.
static int	arraySize(int expected, float f) Returns the least power of two smaller than or equal to 230 and larger than or equal to Math.ceil( expected / f ).
boolean	containsNull() Is there a null key.
static int	maxFill(int n, float f) Returns the maximum number of entries that can be filled before rehashing.
static long	nextPowerOfTwo(long x) Return the least power of two greater than or equal to the specified value.
abstract void	optimize() Decide whether to convert to dense mode.
protected int	realSize()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEFAULT_INITIAL_SIZE

public static final int DEFAULT_INITIAL_SIZE

The initial default size of a hash table.

See Also:

Constant Field Values

DEFAULT_LOAD_FACTOR

public static final float DEFAULT_LOAD_FACTOR

The default load factor of a hash table.

See Also:

Constant Field Values

DENSE_THRESHOLD

public static final int DENSE_THRESHOLD

Decide whether to convert to dense mode if it does not require more memory or could fit within L1 cache.

See Also:

Constant Field Values

f

protected final float f

The acceptable load factor.

mask

protected int mask

The mask for wrapping a position counter.

n

protected int n

The current table size.

maxFill

protected int maxFill

Threshold after which we rehash. It must be the table size times f.

containsNull

protected boolean containsNull

Is this set has a null key.

containsZero

protected boolean containsZero

Is this set has a zero key.

size

protected int size

Number of entries in the set.

isDense

protected boolean isDense

Is now dense mode.

used

protected boolean[] used

Used array for dense mode.

Constructor Detail

OptimizableHashSet

public OptimizableHashSet(int expected,
                          float f)

Method Detail

addNull

public void addNull()

Add a null key.

containsNull

public boolean containsNull()

Is there a null key.

realSize

protected int realSize()

optimize

public abstract void optimize()

Decide whether to convert to dense mode.

nextPowerOfTwo

public static long nextPowerOfTwo(long x)

Return the least power of two greater than or equal to the specified value.

Note that this function will return 1 when the argument is 0.

Parameters:

x - a long integer smaller than or equal to 2⁶².

Returns:

the least power of two greater than or equal to the specified value.

maxFill

public static int maxFill(int n,
                          float f)

Returns the maximum number of entries that can be filled before rehashing.

Parameters:

n - the size of the backing array.

f - the load factor.

Returns:

the maximum number of entries before rehashing.

arraySize

public static int arraySize(int expected,
                            float f)

Returns the least power of two smaller than or equal to 2³⁰ and larger than or equal to Math.ceil( expected / f ).

Parameters:

expected - the expected number of elements in a hash table.

f - the load factor.

Returns:

the minimum possible size for a backing array.

Throws:

IllegalArgumentException - if the necessary size is larger than 2³⁰.