com.datastax.spark.connector.util
PriorityHashMap
Related Doc:
package util
Returns a value associated with the given key.
Returns a value associated with the given key.
If the key does not exist, throws NoSuchElementException.
If you know the key does exist, this method is preferred over
the get method, because it doesn't allocate an Option object.
Complexity: O(1).
The maximum number of items that can be stored at a time in this map.
Returns true if the map contains given key.
Removes the entry and returns its value
Returns a value associated with the given key.
Returns a value associated with the given key. If the key does not exist, returns None. Complexity: O(1).
Returns the key associated with the largest value.
Returns the key associated with the largest value. Complexity: O(1).
Returns the largest value.
Returns the largest value. Complexity: O(1).
Useful for iterating the map.
Adds or updates a map entry.
Adds or updates a map entry. Complexity: O(log n) average, O(1) optimistic.
Removes a key and reorders remaining items.
Removes a key and reorders remaining items. If the key does not exist, does nothing. Returns true if key existed. Complexity: O(log n) average, O(1) optimistic.
Useful for iterating the map
A HashMap and a PriorityQueue hybrid. Works like a HashMap but offers additional O(1) access to the entry with the highest value. As in a standard HashMap, entries can be looked up by key in O(1) time. Adding, removing and updating items by key is handled in O(log n) time.
Keys must not be changed externally and must implement proper equals and hashCode. It is advised to use immutable classes for keys.
Values must be properly comparable. Values may be externally mutated as long as a proper immediate call to
putis issued to notify the PriorityHashMap that the value associated with the given key has changed, after each value mutation. It is not allowed to externally mutate more than one value at a time or to mutate a value associated with multiple keys. Therefore, it is advised to use immutable classes for values, and updating values only by calls toput.Contrary to standard Java HashMap implementation, PriorityHashMap does not allocate memory on adding / removing / updating items and stores all data in flat, non-resizable arrays instead. Therefore its capacity cannot be modified after construction. It is technically possible to remove this limitation in the future.
PriorityHashMap is mutable and not thread-safe.
Internally, PriorityHashMap is composed of the following data arrays: - an array storing references to keys, forming a heap-based priority queue; - an array storing corresponding references to values, always in the same order as keys; - an array storing indexes into the first two arrays, used as an inline hash-table allowing to quickly locate keys in the heap in constant time; - an array for fast translating indexes in the heap into indexes into hash-table, so after moving a key/value in the heap, the corresponding index in the hash-table can be quickly updated, without hashing.
The indexes hash-table doesn't use overflow lists for dealing with hash collisions. The overflow entries are placed in the main hash-table array in the first not-taken entry to the right from the original position pointed by key hash. On search, if the key is not found immediately at a position pointed by key hash, it is searched to the right, until it is found or an empty array entry is found.
type of keys
type of values; values must be comparable