org.apache.flink.streaming.runtime.operators.windowing

Class KeyMap<K,V>

java.lang.Object

org.apache.flink.streaming.runtime.operators.windowing.KeyMap<K,V>

All Implemented Interfaces:

Iterable<KeyMap.Entry<K,V>>

@Internal
public class KeyMap<K,V>
extends Object
implements Iterable<KeyMap.Entry<K,V>>

A special Hash Map implementation that can be traversed efficiently in sync with other hash maps.

The differences between this hash map and Java's "java.util.HashMap" are:

• A different hashing scheme. This implementation uses extensible hashing, meaning that each hash table growth takes one more lower hash code bit into account, and values that where formerly in the same bucket will afterwards be in the two adjacent buckets.
• This allows an efficient traversal of multiple hash maps together, even though the maps are of different sizes.
• The map offers functions such as "putIfAbsent()" and "putOrAggregate()"
• The map supports no removal/shrinking.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	KeyMap.Entry<K,V> An entry in the hash table.
static interface	KeyMap.LazyFactory<V> A factory for lazy/on-demand instantiation of values.
static interface	KeyMap.TraversalEvaluator<K,V> A visitor for a traversal over the union of multiple hash maps.

Constructor Summary

Constructors

Constructor and Description
KeyMap() Creates a new hash table with the default initial capacity.
KeyMap(int expectedNumberOfElements) Creates a new table with a capacity tailored to the given expected number of elements.

Method Summary

Modifier and Type	Method and Description
V	get(K key) Looks up the value mapped under the given key.
int	getCurrentTableCapacity() Gets the current table capacity, i.e., the number of slots in the hash table, without and overflow chaining.
int	getLog2TableCapacity() Gets the base-2 logarithm of the hash table capacity, as returned by getCurrentTableCapacity().
int	getRehashThreshold()
int	getShift()
boolean	isEmpty() Checks whether the map is empty.
Iterator<KeyMap.Entry<K,V>>	iterator() Creates an iterator over the entries of this map.
V	put(K key, V value) Inserts the given value, mapped under the given key.
V	putIfAbsent(K key, KeyMap.LazyFactory<V> factory) Inserts a value for the given key, if no value is yet contained for that key.
V	putOrAggregate(K key, V value, ReduceFunction<V> aggregator) Inserts or aggregates a value into the hash map.
int	size() Gets the number of elements currently in the map.
static <K,V> void	traverseMaps(KeyMap<K,V>[] maps, KeyMap.TraversalEvaluator<K,V> visitor, long touchedTag) Performs a traversal about logical the multi-map that results from the union of the given maps.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

KeyMap

public KeyMap()

Creates a new hash table with the default initial capacity.

KeyMap

public KeyMap(int expectedNumberOfElements)

Creates a new table with a capacity tailored to the given expected number of elements.

Parameters:

expectedNumberOfElements - The number of elements to tailor the capacity to.

Method Detail

put

public final V put(K key,
                   V value)

Inserts the given value, mapped under the given key. If the table already contains a value for the key, the value is replaced and returned. If no value is contained, yet, the function returns null.

Parameters:

key - The key to insert.

value - The value to insert.

Returns:

The previously mapped value for the key, or null, if no value was mapped for the key.

Throws:

NullPointerException - Thrown, if the key is null.

putIfAbsent

public final V putIfAbsent(K key,
                           KeyMap.LazyFactory<V> factory)

Inserts a value for the given key, if no value is yet contained for that key. Otherwise, returns the value currently contained for the key.

The value that is inserted in case that the key is not contained, yet, is lazily created using the given factory.

Parameters:

key - The key to insert.

factory - The factory that produces the value, if no value is contained, yet, for the key.

Returns:

The value in the map after this operation (either the previously contained value, or the newly created value).

Throws:

NullPointerException - Thrown, if the key is null.

putOrAggregate

public final V putOrAggregate(K key,
                              V value,
                              ReduceFunction<V> aggregator)
                       throws Exception

Inserts or aggregates a value into the hash map. If the hash map does not yet contain the key, this method inserts the value. If the table already contains the key (and a value) this method will use the given ReduceFunction function to combine the existing value and the given value to a new value, and store that value for the key.

Parameters:

key - The key to map the value.

value - The new value to insert, or aggregate with the existing value.

aggregator - The aggregator to use if a value is already contained.

Returns:

The value in the map after this operation: Either the given value, or the aggregated value.

Throws:

NullPointerException - Thrown, if the key is null.

Exception - The method forwards exceptions from the aggregation function.

get

public V get(K key)

Looks up the value mapped under the given key. Returns null if no value is mapped under this key.

Parameters:

key - The key to look up.

Returns:

The value associated with the key, or null, if no value is found for the key.

Throws:

NullPointerException - Thrown, if the key is null.

iterator

public Iterator<KeyMap.Entry<K,V>> iterator()

Creates an iterator over the entries of this map.

Specified by:

iterator in interface Iterable<KeyMap.Entry<K,V>>

Returns:

An iterator over the entries of this map.

size

public int size()

Gets the number of elements currently in the map.

Returns:

The number of elements currently in the map.

isEmpty

public boolean isEmpty()

Checks whether the map is empty.

Returns:

True, if the map is empty, false otherwise.

getCurrentTableCapacity

public int getCurrentTableCapacity()

Gets the current table capacity, i.e., the number of slots in the hash table, without and overflow chaining.

Returns:

The number of slots in the hash table.

getLog2TableCapacity

public int getLog2TableCapacity()

Gets the base-2 logarithm of the hash table capacity, as returned by getCurrentTableCapacity().

Returns:

The base-2 logarithm of the hash table capacity.

getRehashThreshold

public int getRehashThreshold()

getShift

public int getShift()

traverseMaps

public static <K,V> void traverseMaps(KeyMap<K,V>[] maps,
                                      KeyMap.TraversalEvaluator<K,V> visitor,
                                      long touchedTag)
                               throws Exception

Performs a traversal about logical the multi-map that results from the union of the given maps. This method does not actually build a union of the map, but traverses the hash maps together.

Type Parameters:

K - The type of the map's key.

V - The type of the map's value.

Parameters:

maps - The array uf maps whose union should be traversed.

visitor - The visitor that is called for each key and all values.

touchedTag - A tag that is used to mark elements that have been touched in this specific traversal. Each successive traversal should supply a larger value for this tag than the previous one.

Throws:

Exception