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
- Alphabetic
- By Inheritance
- PriorityHashMap
- AnyRef
- Any
- Hide All
- Show All
- Public
- All
Instance Constructors
-
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
-
final
def
!=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
final
def
##(): Int
- Definition Classes
- AnyRef → Any
-
final
def
==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
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). -
final
def
asInstanceOf[T0]: T0
- Definition Classes
- Any
-
val
capacity: Int
The maximum number of items that can be stored at a time in this map.
-
def
clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( ... ) @native()
-
def
contains(key: K): Boolean
Returns true if the map contains given key.
-
def
dequeue(): V
Removes the entry and returns its value
-
final
def
eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
-
def
equals(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
def
finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( classOf[java.lang.Throwable] )
-
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).
-
final
def
getClass(): Class[_]
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
-
def
hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
-
def
headKey: K
Returns the key associated with the largest value.
Returns the key associated with the largest value. Complexity: O(1).
-
def
headValue: V
Returns the largest value.
Returns the largest value. Complexity: O(1).
- def isEmpty: Boolean
-
final
def
isInstanceOf[T0]: Boolean
- Definition Classes
- Any
-
def
keys: IndexedSeq[K]
Useful for iterating the map.
-
final
def
ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def nonEmpty: Boolean
-
final
def
notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
final
def
notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
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.
-
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.
- def size: Int
-
final
def
synchronized[T0](arg0: ⇒ T0): T0
- Definition Classes
- AnyRef
-
def
toString(): String
- Definition Classes
- PriorityHashMap → AnyRef → Any
-
def
values: IndexedSeq[V]
Useful for iterating the map
-
final
def
wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... ) @native()