@thi.ng/associative
Advanced tools
Alternative Map and Set implementations with customizable equality semantics & supporting operations, plain object utilities
[!NOTE] This is one of 189 standalone projects, maintained as part of the @thi.ng/umbrella monorepo and anti-framework.
🚀 Please help me to work full-time on these projects by sponsoring me on GitHub. Thank you! ❤️
Alternative Map and Set implementations with customizable equality semantics & supporting operations, plain object utilities.
ArraySet, Linked List based LLSet,
Skiplist based SortedMap &
SortedSet and customizable EquivMap implement the full ES6 Map/Set APIs
and additional features:
entries(), keys(), values()) (sorted
types only)ICopy, IEmpty & IEquiv implementationsICompare implementation for sorted typesinto(), dissoc()
(maps) and disj() (sets)fromObject() converters (for maps only)TrieMap for string-based keys and MultiTrie for array-like keys and
multiple values per keySparseSet implementations for numeric valuesK => V to V => KPlease see these packages for some example use cases:
The native ES6 implementations use object reference identity to determine key containment, but often it's more practical and useful to use equivalent value semantics for this purpose, especially when keys are structured data (arrays / objects).
Note: It's the user's responsibility to ensure the inserted keys are kept immutable (even if technically they're not).
// first two objects w/ equal values
a = [1, 2];
b = [1, 2];
Using native implementations
set = new Set();
set.add(a);
set.has(b);
// false
map = new Map();
map.set(a, "foo");
map.get(b);
// undefined
Using custom implementations:
import { defArraySet } from "@thi.ng/associative";
set = defArraySet();
set.add(a);
set.add({a: 1});
// ArraySet { [ 1, 2 ], { a: 1 } }
set.has(b);
// true
set.has({a: 1});
// true
import { defLLSet } from "@thi.ng/associative";
set = defLLSet();
set.add(a);
set.add({a: 1});
// LLSet { [ 1, 2 ], { a: 1 } }
set.has(b);
// true
set.has({a: 1});
// true
import { defEquivMap } from "@thi.ng/associative";
// by default EquivMap uses ArraySet for its canonical keys
map = defEquivMap();
// with custom implementation
map = defEquivMap(null, { keys: assoc.ArraySet });
map.set(a, "foo");
// EquivMap { [ 1, 2 ] => 'foo' }
map.get(b);
// "foo"
// Hash map w/ user supplied hash code function
// (here using `hash` function for arrays)
import { defHashMap } from "@thi.ng/associative";
import { hash } from "@thi.ng/vectors"
m = defHashMap([], { hash })
m.set([1, 2], "a");
m.set([3, 4, 5], "b");
m.set([1, 2], "c");
// HashMap { [ 1, 2 ] => 'c', [ 3, 4, 5 ] => 'b' }
import { defSortedSet, defSortedMap } from "@thi.ng/associative";
set = defSortedSet([a, [-1, 2], [-1, -2]]);
// SortedSet { [ -1, -2 ], [ -1, 2 ], [ 1, 2 ] }
set.has(b);
// true
map = defSortedMap([[a, "foo"], [[-1,-2], "bar"]]);
// SortedMap { [ -1, -2 ] => 'bar', [ 1, 2 ] => 'foo' }
map.get(b);
// "foo"
// key lookup w/ default value
map.get([3,4], "n/a");
// "n/a"
STABLE - used in production
Search or submit any issues for this package
yarn add @thi.ng/associative
ESM import:
import * as assoc from "@thi.ng/associative";
Browser ESM import:
<script type="module" src="https://esm.run/@thi.ng/associative"></script>
For Node.js REPL:
const assoc = await import("@thi.ng/associative");
Package sizes (brotli'd, pre-treeshake): ESM: 6.98 KB
Several projects in this repo's /examples directory are using this package:
| Screenshot | Description | Live demo | Source |
|---|---|---|---|
 | Heatmap visualization of this mono-repo's commits | Source | |
 | Augmenting thi.ng/geom shapes for WebGL, using instancing & attribute buffers | Demo | Source |
 | rstream & transducer-based FSM for converting key event sequences into high-level commands | Demo | Source |
 | Responsive image gallery with tag-based Jaccard similarity ranking | Demo | Source |
All Set implementations in this package implement the
IEquivSet
interface, an extension of the native ES6 Set API.
Simple array based Set implementation which by default uses
@thi.ng/equiv
for value equivalence checking.
Similar to ArraySet, but uses
@thi.ng/dcons linked list
as backing storage for values.
This Map implementation uses a native ES6 Map as backing storage for
its key-value pairs and an additional IEquivSet implementation for
canonical keys. By default uses ArraySet for this purpose.
Map implementation w/ standard ES6 Map API, supporting any key type via
hash codes computed via user supplied hash function. Uses Open
Addressing / Linear
Probing to resolve key collisions. Customizable via HashMapOpts
constructor argument. Hash function MUST be given.
Alternative implementation of the ES6 Map API using a Skip list as backing store and support for configurable key equality and sorting semantics. Like with sets, uses @thi.ng/equiv & @thi.ng/compare by default.
William Pugh's (creator of this data structure) description:
"Skip lists are probabilistic data structures that have the same asymptotic expected time bounds as balanced trees, are simpler, faster and use less space."
Data structure description:
import { defSortedMap } from "@thi.ng/associative";
map = defSortedMap([
["c", 3], ["a", 1], ["d", 4], ["b", 2]
]);
// SortedMap { 'a' => 1, 'b' => 2, 'c' => 3, 'd' => 4 }
// all entries
[...map.entries()]
// [ [ 'd', 4 ], [ 'c', 3 ], [ 'b', 2 ], [ 'a', 1 ] ]
// range query w/ given start key
// also works with `keys()` and `values()`
[...map.entries("c")]
// [ [ 'c', 3 ], [ 'd', 4 ] ]
// unknown start keys are ok
[...map.entries("cc")]
// [ [ 'd', 4 ] ]
// range query w/ given MAX key
[...map.entries("c", true)]
// [ [ 'a', 1 ], [ 'b', 2 ], [ 'c', 3 ] ]
Sorted set implementation with standard ES6 Set API, customizable value equality and comparison semantics and additional functionality:
entries, keys, values)into() and disj()Furthermore, this class implements the ICopy, IEmpty, ICompare and
IEquiv interfaces defined by @thi.ng/api. The latter two allow
instances to be used as keys themselves in other data types defined in
this (and other) package(s).
This set uses a SortedMap as backing store.
Sparse sets provide super fast
(approx. 4x faster than the native Set impl) insertion & lookups for
numeric values in the interval [0..n) . The implementation in this
package provides most of the ES6 Set API and internally relies on 2 uint
typed arrays, with the actual backing type dependent on n.
Furthermore, unless (or until) values are being removed from the set, they retain their original insertion order. For some use cases (e.g. deduplication of values), this property can be very useful.
import { defSparseSet } from "@thi.ng/associative";
// create sparse set for value range 0 - 99 (uint8 backed)
const a = defSparseSet(100);
a.into([99, 42, 66, 23, 66, 42]);
// SparseSet8 { 99, 42, 66, 23 }
a.has(66)
// true
// sparse sets are iterable
[...a]
// [ 99, 42, 66, 23 ]
// attempting to add out-of-range values will fail
a.add(100)
// SparseSet8 { 99, 42, 66, 23 }
// create sparse set for 16 bit value range 0 - 0xffff (uint16 backed)
const b = defSparseSet(0x10000);
// SparseSet16 {}
Tries (also called Prefix maps) are useful data structures for search based use cases, auto-complete, text indexing etc. and provide partial key matching (prefixes), suffix iteration for a common prefix, longest matching prefix queries etc.
The implementations here too feature ES6 Map-like API, similar to other types in this package, with some further trie-specific additions.
import { defTrieMap } from "@thi.ng/associative";
const trie = defTrieMap([
["hey", "en"],
["hello", "en"],
["hallo", "de"],
["hallo", "de-at"],
["hola", "es"],
["hold", "en"],
["hej", "se"],
]);
trie.knownPrefix("hole")
// "hol"
[...trie.suffixes("he")]
// [ "j", "llo", "y" ]
// w/ prefix included
[...trie.suffixes("he", true)]
// [ "hej", "hello", "hey" ]
The MultiTrie is similar to TrieMap, but supports array-like keys and
multiple values per key. Values are stored in sets whose implementation can be
configured via ctor options.
import { defMultiTrie } from "@thi.ng/associative";
// init w/ custom value set type (here only for illustration)
const t = defMultiTrie<string[], string>(null, { vals: () => new ArraySet() });
t.add("to be or not to be".split(" "), 1);
t.add("to be or not to be".split(" "), 2);
t.add("to be and to live".split(" "), 3);
t.get("to be or not to be".split(" "))
// Set(2) { 1, 2 }
t.knownPrefix(["to", "be", "not"]);
// [ "to", "be" ]
// auto-complete w/ custom separator between words
[...t.suffixes(["to", "be"], false, "/")]
// [ "and/to/live", "or/not/to/be" ]
If this project contributes to an academic publication, please cite it as:
@misc{thing-associative,
title = "@thi.ng/associative",
author = "Karsten Schmidt",
note = "https://thi.ng/associative",
year = 2017
}
© 2017 - 2024 Karsten Schmidt // Apache License 2.0
FAQs
ES Map/Set-compatible implementations with customizable equality semantics & supporting operations
We found that @thi.ng/associative demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
PyPI confirms no security flaws were exploited in the Ultralytics supply chain attack and highlights improvements for safer package publishing.
Security News
Research
The Socket Research Team breaks down a malicious wrapper package that uses obfuscation to harvest credentials and exfiltrate sensitive data.
Research
Security News
Attackers used a malicious npm package typosquatting a popular ESLint plugin to steal sensitive data, execute commands, and exploit developer systems.