Mnemonist

SparseMap


A SparseMap is a very time-efficient map structure used to associate arbitrary values to a range of unsigned integers. Note however that this structure can consume a lot of memory (it relies on two byte arrays having a length equal to the maximum integer you need to store).

Contrary to the BitSet, the SparseMap is very efficient if you need to iterate over the stored value or if you often need to clear the map.

If you don’t need to associate values to your numbers, take a look to SparseSet instead.

var SparseMap = require('mnemonist/sparse-map');

Constructor

The SparseMap takes a maximum length to store as well as, optionally, a constructor for the array that will store the map’s values. This can be useful when storing, say, small positive integers and you want to save memory.

var map = new SparseMap(length);

// If you know your values type:
var map = new SparseMap(Uint8Array, length);

Members

Methods

Mutation

Read

Iteration

#.length

Length of the map, that is to say the maximum number one can expect to store in this set minus one.

var map = new SparseMap(4);

map.length;
>>> 4

#.size

Number of items currently in the map.

var map = new SparseMap(4);

map.size;
>>> 0

map.add(2);

map.size;
>>> 1

#.set

Associates a value to the given number in the map.

O(1)

var map = new SparseMap(4);

map.set(2, 34);
map.get(2);
>>> 34

#.delete

Deletes the given number from the map.

O(1)

var map = new SparseMap(4);

map.set(2, 34);
map.delete(2);
map.has(2);
>>> false

#.clear

Resets every number stored by the map.

var map = new SparseMap(4);

map.set(1);
map.set(3);

map.clear();
map.size
>>> 0

#.has

Returns whether the given number exists in the map.

O(1)

var map = new SparseMap(4);

map.has(3);
>>> false

map.set(3, 34);
map.has(3);
>>> true

#.get

Returns the value currently associated to the given number in the map.

var map = new SparseMap(4);

map.get(3);
>>> undefined

map.set(3, 34);
map.get(3);
>>> 34

#.forEach

Iterates over the map’s entries.

var map = new SparseMap(4);

map.set(1, 23);

map.forEach(function(value, key) {
  console.log(key, value);
});

#.keys

Returns an iterator over the map’s keys.

var map = new SparseMap(4);

map.set(2, 15);

var iterator = map.keys();

iteraror.next().value
>>> 2

#.values

Returns an iterator over the set’s values.

var map = new SparseMap(4);

map.set(2, 15);

var iterator = map.values();

iteraror.next().value
>>> 15

#.entries

Returns an iterator over the set’s entries.

var map = new SparseMap(4);

map.set(2, 15);

var iterator = map.entries();

iteraror.next().value
>>> [2, 15]

Iterable

Alternatively, you can iterate over a map’s entries using ES2015 for...of protocol:

var map = new SparseMap(4);

for (var [key, value] of map) {
  console.log(key, value);
}