Skip to content

Latest commit

 

History

History
70 lines (53 loc) · 3.27 KB

map.asc

File metadata and controls

70 lines (53 loc) · 3.27 KB

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