TreeMap

TreeMap

A TreeMap is a map implementation using BinarySearchTree. Implementing a Map with a tree has a few advantages over a List powered HashMap:

  • Keys are always sorted
  • When working with numbers, obtaining statistical data like median, min/max etc. is trivial.
  • Collisions are not a concern, so even in the worst case complexity is O(log n).
  • No collisions, no rehashing.

The tree used here, BinarySearchTree, is not self balancing. Using a self-balanced tree such as a Red-Black tree or an AVL tree would give better performance.

The data stored in a TreeMap must support comparison operations such as <, >, == in a coherent manner. The behaviour, otherwise, is undefined.

Constructor

new TreeMap()

Source:

Methods

add(key, value) → {TreeMap}

Insert a key/value pair into the map. If the key is already present, overwrite the existing value.

Runtime: O(log n)

Returns the map instance to allow command chaining.

Parameters:
Name Type Description
key any
value any
Source:

delete(key)

Deletes the key-value pair if the key exists and returns the removed value. If key doesn't exist, returns null.

Parameters:
Name Type Description
key any
Source:

get(key) → (nullable) {any}

Returns the value for given key. Runtime: O(log n). If the key doesn't exist, returns null.

Parameters:
Name Type Description
key any
Source:

has(key) → {boolean}

Searchs for the key and returns true if it is found, and false otherwise.

Runtime: O(log n)

Parameters:
Name Type Description
key any
Source:

(generator) keys() → {Iterator}

Get key for each element in the map. Result in ascending order.

Source:

(generator) values() → {Iterator}

Get value for each element in the map. Result in ascending order of the corresponding keys.

Source: