# @perma/map

> Immutable hash maps implemented as hash array papped tries

Latest version **1.0.3** (published 2023-06-23) · (Apache-2.0 AND MIT) license · 0 weekly downloads

## Install

```sh
npm install @perma/map
pnpm add @perma/map
yarn add @perma/map
bun add @perma/map
```

## Health

**Score 30/100 (F)** — status: abandoned.

Positive: has types; esm support; no vulnerabilities; high quality score.

Warnings: low downloads.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 1.0.3 |
| Published | 2023-06-23 |
| First published | 2023-03-08 |
| Weekly downloads | 0 |
| License | (Apache-2.0 AND MIT) |
| TypeScript types | bundled |
| Module format | ESM + CommonJS |
| Dependencies | 2 |
| Unpacked size | 100.2 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 6 |
| Maintainers | gozala |
| Keywords | HAMT, CHAMP, immutable, hashmap, map |

## Links

- npm: https://www.npmjs.com/package/@perma/map
- Repository: https://github.com/gozala/perma-map
- Homepage: https://github.com/gozala/perma-map.git
- Issues: https://github.com/gozala/perma-map/issues
- npm.io page: https://npm.io/package/@perma/map

## Dependencies (2)

- [@multiformats/murmur3](https://npm.io/package/@multiformats/murmur3.md) ^2.1.0
- [murmurhash3js-revisited](https://npm.io/package/murmurhash3js-revisited.md) ^3.0.0

## Alternatives

- [@gemini-wallet/core](https://npm.io/package/@gemini-wallet/core.md) — 515.6K weekly downloads
- [utility](https://npm.io/package/utility.md) — 416.6K weekly downloads
- [@primno/dpapi](https://npm.io/package/@primno/dpapi.md) — 7.2K weekly downloads
- [pi-readseek](https://npm.io/package/pi-readseek.md) — 3.7K weekly downloads
- [@emilia-protocol/verify](https://npm.io/package/@emilia-protocol/verify.md) — 1.1K weekly downloads

## Recent versions

- 1.0.3 (latest) — 2023-06-23
- 1.0.2 — 2023-03-08
- 1.0.1 — 2023-03-08

## README

# @perma/map

Hash Array Map Trie (HAMT) implementation based on [CHAMP][] paper and inspired by [Clojure][]. Library provides a builder API inspired by clojure [transient][]s that can be utilized for bulk updates.

## Status

Prototype implements hash-array map tries (HAMT) by synthesizing [CHAMP][]
algorithm with HAMTs used by [IPFS UnixFS][] and [IPLD HAMT][]. [CHAMP][]
algorithm utilized several optimizations that are incompatible with [IPFS UnixFS][] and [IPLD HAMT][], this implementation attempts to utilize those optimizations at
runtime and provide a way to map it to [IPFS UnixFS][] compatible representation.

## Optimizations

[CHAMP][] algorithm exploits branching factor of `32` because it can be manipulated efficiently on 32-bit processors. It also allows storing HAMT bitmaps in a single integer.

In order to support [IPFS UnixFS][] implementation (which uses `256` factor by default) branching factor is configurable, but relevant optimizations only apply when branching factor of `32` is used.

It is also worth noting that even with branching factor of `32` it can store large amount of entries in a relatively shallow tree e.g. tree 6 levels deep could store around `33,554,432` entries.

## Credits

- [Leveling up Clojure’s Hash Maps](https://bendyworks.com/blog/leveling-clojures-hash-maps)
- [Hash Array Mapped Tries](https://worace.works/2016/05/24/hash-array-mapped-tries/)
- [Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections](https://michael.steindorfer.name/publications/oopsla15.pdf)
- [Lean Hash Array Mapped Trie (Lean Map)](https://github.com/bendyworks/lean-map)
- [Ideal hash trees](http://lampwww.epfl.ch/papers/idealhashtrees.pdf)

[ipfs unixfs]: https://github.com/ipfs/specs/blob/main/UNIXFS.md
[champ]: https://michael.steindorfer.name/publications/oopsla15.pdf
[ipld hamt]: https://ipld.io/specs/advanced-data-layouts/hamt/spec/
[clojure]: https://clojure.org/
[transient]: https://clojure.org/reference/transients

---
_Source: https://npm.io/package/@perma/map · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._