Class

com.datastax.spark.connector.util

PriorityHashMap

Related Doc: package util

Permalink

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

    Permalink

    _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

    Permalink
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int

    Permalink
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean

    Permalink
    Definition Classes
    AnyRef → Any
  4. def apply(key: K): V

    Permalink

    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

    Permalink
    Definition Classes
    Any
  6. val capacity: Int

    Permalink

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

  7. def clone(): AnyRef

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

    Permalink

    Returns true if the map contains given key.

  9. def dequeue(): V

    Permalink

    Removes the entry and returns its value

  10. final def eq(arg0: AnyRef): Boolean

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

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

    Permalink
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  13. def get(key: K): Option[V]

    Permalink

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

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

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

    Permalink
    Definition Classes
    AnyRef → Any
  16. def headKey: K

    Permalink

    Returns the key associated with the largest value.

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

  17. def headValue: V

    Permalink

    Returns the largest value.

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

  18. def isEmpty: Boolean

    Permalink
  19. final def isInstanceOf[T0]: Boolean

    Permalink
    Definition Classes
    Any
  20. def keys: IndexedSeq[K]

    Permalink

    Useful for iterating the map.

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

    Permalink
    Definition Classes
    AnyRef
  22. def nonEmpty: Boolean

    Permalink
  23. final def notify(): Unit

    Permalink
    Definition Classes
    AnyRef
  24. final def notifyAll(): Unit

    Permalink
    Definition Classes
    AnyRef
  25. def put(key: K, value: V): Unit

    Permalink

    Adds or updates a map entry.

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

  26. def remove(key: K): Boolean

    Permalink

    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.

  27. def size: Int

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

    Permalink
    Definition Classes
    AnyRef
  29. def toString(): String

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

    Permalink

    Useful for iterating the map

  31. final def wait(): Unit

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

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

    Permalink
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Inherited from AnyRef

Inherited from Any

Ungrouped