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
Implicitly
  1. by any2stringadd
  2. by any2stringfmt
  3. by any2ArrowAssoc
  4. by any2Ensuring
  1. Hide All
  2. Show all
Learn more about member selection
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: AnyRef): Boolean

    Definition Classes
    AnyRef
  2. final def !=(arg0: Any): Boolean

    Definition Classes
    Any
  3. final def ##(): Int

    Definition Classes
    AnyRef → Any
  4. def +(other: String): String

    Implicit information
    This member is added by an implicit conversion from PriorityHashMap[K, V] to StringAdd performed by method any2stringadd in scala.Predef.
    Definition Classes
    StringAdd
  5. def ->[B](y: B): (PriorityHashMap[K, V], B)

    Implicit information
    This member is added by an implicit conversion from PriorityHashMap[K, V] to ArrowAssoc[PriorityHashMap[K, V]] performed by method any2ArrowAssoc in scala.Predef.
    Definition Classes
    ArrowAssoc
    Annotations
    @inline()
  6. final def ==(arg0: AnyRef): Boolean

    Definition Classes
    AnyRef
  7. final def ==(arg0: Any): Boolean

    Definition Classes
    Any
  8. 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).

  9. final def asInstanceOf[T0]: T0

    Definition Classes
    Any
  10. val capacity: Int

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

  11. def clone(): AnyRef

    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  12. def contains(key: K): Boolean

    Returns true if the map contains given key.

  13. def dequeue(): V

    Removes the entry and returns its value

  14. def ensuring(cond: (PriorityHashMap[K, V]) ⇒ Boolean, msg: ⇒ Any): PriorityHashMap[K, V]

    Implicit information
    This member is added by an implicit conversion from PriorityHashMap[K, V] to Ensuring[PriorityHashMap[K, V]] performed by method any2Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  15. def ensuring(cond: (PriorityHashMap[K, V]) ⇒ Boolean): PriorityHashMap[K, V]

    Implicit information
    This member is added by an implicit conversion from PriorityHashMap[K, V] to Ensuring[PriorityHashMap[K, V]] performed by method any2Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  16. def ensuring(cond: Boolean, msg: ⇒ Any): PriorityHashMap[K, V]

    Implicit information
    This member is added by an implicit conversion from PriorityHashMap[K, V] to Ensuring[PriorityHashMap[K, V]] performed by method any2Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  17. def ensuring(cond: Boolean): PriorityHashMap[K, V]

    Implicit information
    This member is added by an implicit conversion from PriorityHashMap[K, V] to Ensuring[PriorityHashMap[K, V]] performed by method any2Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  18. final def eq(arg0: AnyRef): Boolean

    Definition Classes
    AnyRef
  19. def equals(arg0: Any): Boolean

    Definition Classes
    AnyRef → Any
  20. def finalize(): Unit

    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  21. def formatted(fmtstr: String): String

    Implicit information
    This member is added by an implicit conversion from PriorityHashMap[K, V] to StringFormat performed by method any2stringfmt in scala.Predef.
    Definition Classes
    StringFormat
    Annotations
    @inline()
  22. 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).

  23. final def getClass(): Class[_]

    Definition Classes
    AnyRef → Any
  24. def hashCode(): Int

    Definition Classes
    AnyRef → Any
  25. def headKey: K

    Returns the key associated with the largest value.

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

  26. def headValue: V

    Returns the largest value.

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

  27. def isEmpty: Boolean

  28. final def isInstanceOf[T0]: Boolean

    Definition Classes
    Any
  29. def keys: IndexedSeq[K]

    Useful for iterating the map.

  30. final def ne(arg0: AnyRef): Boolean

    Definition Classes
    AnyRef
  31. def nonEmpty: Boolean

  32. final def notify(): Unit

    Definition Classes
    AnyRef
  33. final def notifyAll(): Unit

    Definition Classes
    AnyRef
  34. 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.

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

  36. def size: Int

  37. final def synchronized[T0](arg0: ⇒ T0): T0

    Definition Classes
    AnyRef
  38. def toString(): String

    Definition Classes
    PriorityHashMap → AnyRef → Any
  39. def values: IndexedSeq[V]

    Useful for iterating the map

  40. final def wait(): Unit

    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  41. final def wait(arg0: Long, arg1: Int): Unit

    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  42. final def wait(arg0: Long): Unit

    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  43. def [B](y: B): (PriorityHashMap[K, V], B)

    Implicit information
    This member is added by an implicit conversion from PriorityHashMap[K, V] to ArrowAssoc[PriorityHashMap[K, V]] performed by method any2ArrowAssoc in scala.Predef.
    Definition Classes
    ArrowAssoc

Shadowed Implicit Value Members

  1. val self: Any

    Implicit information
    This member is added by an implicit conversion from PriorityHashMap[K, V] to StringAdd performed by method any2stringadd in scala.Predef.
    Shadowing
    This implicitly inherited member is ambiguous. One or more implicitly inherited members have similar signatures, so calling this member may produce an ambiguous implicit conversion compiler error.
    To access this member you can use a type ascription:
    (priorityHashMap: StringAdd).self
    Definition Classes
    StringAdd
  2. val self: Any

    Implicit information
    This member is added by an implicit conversion from PriorityHashMap[K, V] to StringFormat performed by method any2stringfmt in scala.Predef.
    Shadowing
    This implicitly inherited member is ambiguous. One or more implicitly inherited members have similar signatures, so calling this member may produce an ambiguous implicit conversion compiler error.
    To access this member you can use a type ascription:
    (priorityHashMap: StringFormat).self
    Definition Classes
    StringFormat

Deprecated Value Members

  1. def x: PriorityHashMap[K, V]

    Implicit information
    This member is added by an implicit conversion from PriorityHashMap[K, V] to ArrowAssoc[PriorityHashMap[K, V]] performed by method any2ArrowAssoc in scala.Predef.
    Shadowing
    This implicitly inherited member is ambiguous. One or more implicitly inherited members have similar signatures, so calling this member may produce an ambiguous implicit conversion compiler error.
    To access this member you can use a type ascription:
    (priorityHashMap: ArrowAssoc[PriorityHashMap[K, V]]).x
    Definition Classes
    ArrowAssoc
    Annotations
    @deprecated
    Deprecated

    (Since version 2.10.0) Use leftOfArrow instead

  2. def x: PriorityHashMap[K, V]

    Implicit information
    This member is added by an implicit conversion from PriorityHashMap[K, V] to Ensuring[PriorityHashMap[K, V]] performed by method any2Ensuring in scala.Predef.
    Shadowing
    This implicitly inherited member is ambiguous. One or more implicitly inherited members have similar signatures, so calling this member may produce an ambiguous implicit conversion compiler error.
    To access this member you can use a type ascription:
    (priorityHashMap: Ensuring[PriorityHashMap[K, V]]).x
    Definition Classes
    Ensuring
    Annotations
    @deprecated
    Deprecated

    (Since version 2.10.0) Use resultOfEnsuring instead

Inherited from AnyRef

Inherited from Any

Inherited by implicit conversion any2stringadd from PriorityHashMap[K, V] to StringAdd

Inherited by implicit conversion any2stringfmt from PriorityHashMap[K, V] to StringFormat

Inherited by implicit conversion any2ArrowAssoc from PriorityHashMap[K, V] to ArrowAssoc[PriorityHashMap[K, V]]

Inherited by implicit conversion any2Ensuring from PriorityHashMap[K, V] to Ensuring[PriorityHashMap[K, V]]

Ungrouped