mootable / hashmap

Providing fast at scale HashMap, LinkedHashMap, and Higher Order Functions to any iterable, such as Array, Map or Set. Tested, and Benchmarked, Issues & PRs welcomed.

HashMap & LinkedHashMap

Description

This project provides HashMap and LinkedHashMap classes that works both on Node.js and the browser.

• They are both implementations of a simplified HAMT like hash trie
• It uses a modified Murmer 3 algorithm for generating hashes. This ensures the widest possible spread across all buckets.
• As per spec, the basic Hashmap is not guaranteed to meet order of insertion when iterating over it. If you want guaranteed insertion order when iterating, use LinkedHashMap.
• The keys are truly typed and unique, this means 1 !== "1".

Choose your map wisely.

• When choosing a collection it is worth understanding the problem you are trying to solve.
• Native JS Map for small numbers of entries, will be significantly faster.
• However once the map reaches 1'000 or more the Mootable Hashmap really shows its strengths. It utilizes more memory, to do this.
• The Native JS Map is likely to have improved speed characteristics if repeating operations in a loop, via things such as JIT compilation. It is worth benchmarking to see if Map works better for you in those situations.

Installation

Using npm:

$ npm install @mootable/hashmap

You can download the last stable version from the releases page.

If you like risk, you can download the latest master version, it's usually stable.

To run the tests:

$ npm test

To run the benchmarks: (Ensure you have the memory to run them)

• If you don't you can reduce the memory size (in MB) accordingly --max_old_space_size and remove the last items in MAP_SIZES

  $ node --max_old_space_size=24576 --expose-gc test\benchmark.js

API Documentation

• For Full HTML Documentation with Examples please visit Here
• For Full Markdown Documentation please visit Here

Importing

Node ESModules

 import {HashMap, LinkedHashMap} from '@mootable/hashmap';

Node CommonJS

 const {HashMap, LinkedHashMap} = require('@mootable/hashmap');

Browser

<!-- Or one of the other provided alternates (see dist folder) -->
<script src="pathToFile/hashmap.umd.min.js"></script>
<script type="text/javascript">
    // By Default Mootable is on the global scope.
    const HashMap = Mootable.HashMap;
    const LinkedHashMap = Mootable.LinkedHashMap;
</script>

HashMap constructor

This HashMap is backed by a hashtrie.

• new HashMap() creates an empty hashmap
• new HashMap(copy:Iterable) creates a hashmap which is a copy of the provided iterable.
  1. copy either
  • an object that provides a forEach function with the same signature as Map.forEach, such as Map or this HashMap and LinkedHashMap
  • or a 2 dimensional key-value array, e.g. [['key1','val1'], ['key2','val2']].

LinkedHashMap constructor

LinkedHashMap maintains insertion order of keys, it has a slightly larger memory footprint and is a little slower.

• new LinkedHashMap() creates an empty linked hashmap
• new LinkedHashMap(copy:Iterable) creates a linked hashmap which is a copy of the provided iterable.
  1. copy either
  • an object that provides a forEach function with the same signature as Map.forEach, such as Map or this HashMap and LinkedHashMap
  • or a 2 dimensional key-value array, e.g. [['key1','val1'], ['key2','val2']].

Examples

HashMap and LinkedHashMaps, have the same constructor options, and are created in the same way..

Create an empty HashMap

 const hashmap = new HashMap();
 // hashmap.size === 0;

Create a LinkedHashMap from an array of key value pairs

const arr = [[1,'value1'],[2,'value2'],[3,'value3']];
const hashmap = new LinkedHashMap(arr);
// hashmap.size === 3;

Create HashMap from another map

const map = new Map([[1,'value1'],[2,'value2'],[3,'value3']])
const hashmap = new HashMap(map);
// hashmap.size === 3;

Create LinkedHashMap from another HashMap

const first = new HashMap([[1,'value1'],[2,'value2'],[3,'value3']])
const hashmap = new LinkedHashMap(first);
// hashmap.size === 3;

Create a HashMap from a class with symbol

class MyIterable {
    *[Symbol.iterator] () {
        yield ["key1", "value1"];
        yield ["key2", "value2"];
        yield ["key3", "value3"];
        yield ["key4", "value4"];
    }
}
const iterable = new MyIterable();
const hashmap = new HashMap(iterable);
// hashmap.size === 4;
// it doesn't have to be a generator, an iterator works too.

Create a LinkedHashMap from an object with an entries' generator function

const entriesObj = {
    entries: function* () {
        yield ["key1", "value1"];
        yield ["key2", "value2"];
        yield ["key3", "value3"];
        yield ["key4", "value4"];
    }
}
const hashmap = new LinkedHashMap(entriesObj);
// hashmap.size === 4;
// it doesn't have to be a generator, an iterator works too.

Create HashMap from an object with a forEach function

const forEachObj = {
    forEach: (callback, ctx) => {
        for (let i = 1; i <= 4; i++) {
            callback.call(ctx, 'value' + i, 'key' + i);
        }
    }
};
const hashmap = new HashMap(forEachObj);
// hashmap.size === 4;

Benchmarks

• Current Benchmarks can be found under benchmark_results.
  • The default benchmark does a single set, get and delete against a hashmap of a specific size. It does this thousands of times, and finds an approximate average.
  • If you would like me to include your library for benchmarking, raise an issue in github.
    • It must be in NPM
    • It must have an identical interface to JS Map
    • It must be fully written in JS. (Transpiling is acceptable) So that we can guarantee it works in the browser, not just node.

Benchmarks on version 1.0.7

Background

• This repository is a reimplemented version of the npm hashmap repository. It takes that implementation as a starting point, and moves it closer to the core functionality hashmaps are designed to achieve.
• The tests have remained mostly the same, as has some documentation, everything else has changed. The interfaces have now diverged.

LICENSE

The MIT License (MIT)

Copyright (c) 2021 Jack Moxley

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF

hashmap's Issues

Refactor hashbucket storage mechanism to get to a Hash_array_mapped_trie

Hash_array_mapped_trie

Bring the Iterable Wrappers Back

one for 1.1

Convert to ESModule, and transpile for other varients

We want:
ES Module untranspiled
Common JS for Node, minimaly untranspiled
Support for 99.5% of browsers, heavily transpiled Universal Module (UMD)
Support for browsers < 2 years., partialy transpiled Universal Module (UMD)

ensure convention is followed on method names

Allow set in LinkedHashMap to specify replace at end, rather than replace at beginning.

concat function

Given a map (first),
When I call concat on it with another map (second)
Then I get a new map (third) back with the contents of both.
And if ordered, then the order of third is one and then second following.

Split files into functional areas

To make it easier to unit test and provide some more control on exports

Split tests into sanity and unit

rewrite map setups

if a hashbucket is empty, and we are adding a new node, simply add the item, don't go the full depth.

Overwrite key

use the overrides function to allow us to determine whether a key should also be overwritten, default false.
With push and unshift methods we may want to default this to true. To be thought through and decided.

Provide reverse iterators

Makes most sense for LinkedHashMaps, but will also work against HashMaps as they do have an order, just by hash,

Improve Optional => Option

I prefer the language semantics in Rust for this use case, than the Javaish ones.

Worth adding an iterable.

Provide Architectural Documentation

It wasn't clear, neither from documentation nor from code and neither from automatic tests, what methods of access support the order-preserving iteration.
Consider also the explicit reordering, such as https://docs.rs/indexmap/1.6.1/indexmap/map/struct.IndexMap.html#method.sort_keys and https://docs.rs/indexmap/1.6.1/indexmap/map/struct.IndexMap.html#method.sort_by

The docs mention using HAMT and trie, but I couldn't verify it from a cursory look at the code. IMHO there should be a mapping between the high-level documentation, such as the mention of HAMT, and the relevant code. Imagine going to Google Maps, zooming in and seeing entirely different location. The lack of connection or mapping between the different layers of documentation is similarly disconcerting. In order to be reusable ( https://youtu.be/pW-SOdj4Kkk ) software needs to allow for gradual zooming in and our, from architectural overview to code and back, IMHO.

Add Async Methods, Or potential async Class Varient

Having async access hashmap, with effective readwrite locks, might make it more performant.

90-100% ~Test Coverage.

Test coverage, on original source, and transpiled artifacts.

switch to ecma 6 styles (classes, consts, lets etc)

switch equality to sameValueZero as opposed to string (===)

Map, Set and Array use sameValueEquals and so should we
https://262.ecma-international.org/6.0/#sec-samevaluezero

Remove hash function

Sort function

Sort the map in place

Implement Linked Hash Map

Add more benchmarks, and include benchmarking map

Include support for custom hashcode and equalTo methods, for key objects

Improve iteration

Iterate over Buckets better so that we can support streaming/functional programming, without preloading arrays.

typescript support ?

typescript support ?

remove NaN, null and undefined as valid keys.

improve documentation, include description of how hashmaps work, the type of hashmap this is , and the ideal places to use them.

We are aiming for Hash array mapped trie, although we need a touch of rework to get there.

Add Chained Higher Order Function

I want to call map.filter(someFilterFunc).map(someMappingFunction).reduce(someReducer) etc.