Packages

c

com.datastax.spark.connector.util

PriorityHashMap

final class PriorityHashMap[K, V] extends AnyRef

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 put is 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 to put.

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.

K

type of keys

V

type of values; values must be comparable

Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. PriorityHashMap
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

  1. new PriorityHashMap(_capacity: Int)(implicit arg0: Ordering[V])

    _capacity

    minimum required capacity of this collection; the actual capacity may be larger than this, because for performance reasons it is rounded up to the nearest power of two

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. def apply(key: K): V

    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).

  5. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  6. val capacity: Int

    The maximum number of items that can be stored at a time in this map.

  7. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... ) @native() @HotSpotIntrinsicCandidate()
  8. def contains(key: K): Boolean

    Returns true if the map contains given key.

  9. def dequeue(): V

    Removes the entry and returns its value

  10. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  11. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  12. def get(key: K): Option[V]

    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).

  13. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  14. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  15. def headKey: K

    Returns the key associated with the largest value.

    Returns the key associated with the largest value. Complexity: O(1).

  16. def headValue: V

    Returns the largest value.

    Returns the largest value. Complexity: O(1).

  17. def isEmpty: Boolean
  18. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  19. def keys: IndexedSeq[K]

    Useful for iterating the map.

  20. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  21. def nonEmpty: Boolean
  22. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  23. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  24. def put(key: K, value: V): Unit

    Adds or updates a map entry.

    Adds or updates a map entry. Complexity: O(log n) average, O(1) optimistic.

  25. def remove(key: K): Boolean

    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.

  26. def size: Int
  27. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  28. def toString(): String
    Definition Classes
    PriorityHashMap → AnyRef → Any
  29. def values: IndexedSeq[V]

    Useful for iterating the map

  30. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  31. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... ) @native()
  32. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Deprecated Value Members

  1. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] ) @Deprecated @deprecated
    Deprecated

    (Since version ) see corresponding Javadoc for more information.

Inherited from AnyRef

Inherited from Any

Ungrouped