map.asc

Map

A map is a data structure to store pairs of data: key and value. In an array, you can only store values. The array’s key is always the position index. However, in a Map the key can be whatever you want.

Important

Map is a data structure that maps keys to values.

Many languages have maps already built-in. JavaScript/Node has Map:

JavaScript Built-in Map Usage

link:../../../src/data-structures/maps/map.js[role=include]

In short, you set key/value pair and then you can get the value using the key.

The attractive part of Maps is that they are very performant usually O(1) or O(log n) depending on the implementation. We can implement the maps using two different underlying data structures:

• HashMap: it’s a map implementation using an array and a hash function. The job of the hash function is to convert the key into an index that maps to the value. Optimized HashMap can have an average runtime of O(1).

• TreeMap: it’s a map implementation that uses a self-balanced Binary Search Tree (like c-avl-tree.asc). The BST nodes store the key, and the value and nodes are sorted by key guaranteeing an O(log n) look up.

hashmap.asc

treemap.asc

HashMap vs TreeMap

A map can be implemented using hash functions or binary search tree:

• HashMap: it’s a map implementation using an array and hash function. The job of the hash function is to convert the key into an index that contains the matching data. Optimized HashMap can have an average runtime of O(1).

• TreeMap: it’s a map implementation that uses a self-balanced Binary Search Tree (red-black tree). The BST nodes store the key, and the value and nodes are sorted by key guaranteeing an O(log n) look up.

When to use a TreeMap vs. HashMap?

• HashMap is more time-efficient. A TreeMap is more space-efficient.

• TreeMap search complexity is O(log n), while an optimized HashMap is O(1) on average.

• HashMap’s keys are in insertion order (or random depending in the implementation). TreeMap’s keys are always sorted.

• TreeMap offers some statistical data for free such as: get minimum, get maximum, median, find ranges of keys. HashMap doesn’t.

• TreeMap has a guarantee always an O(log n), while `HashMap`s has an amortized time of O(1) but in the rare case of a rehash, it would take an O(n).

TreeMap Time complexity vs HashMap

As we discussed so far, there is a trade-off between the implementations.

Table 1. Time complexity for different Maps implementations

Data Structure	Searching By		Insert	Delete	Space Complexity
	Index/Key	Value
Hash Map (naïve)	O(n)	O(n)	O(n)	O(n)	O(n)
Hash Map (optimized)	O(1)*	O(n)	O(1)*	O(1)*	O(1)*
Tree Map (Red-Black Tree)	O(log n)	O(n)	O(log n)	O(log n)	O(log n)

* = Amortized run time. E.g. rehashing might affect run time to O(n).