I want to create a cache where I have O(1) lookups to its contents, and I lookup keys by value, not by reference. What data structure in JS, if any, would let me accomplish this?
Requirements:
What I've tried:
I was thinking of nested Maps following this structure:
const resultKey = new Symbol('result'); // Create a unique result key, so we don't accidentally return if a key happens to be called 'result'.
// Cache is nested maps, not objects.
const cache = {
[key1]: {
[key2]: {
[key3]: {
[resultKey]: 1234
}
}
}
}
const foo = function cachedFunc(key1, key2, key3); // If these keys match values in the cache, just return the cache value.
And this would work fine for O(1) lookups by reference, but for value I would still need to iterate the keys at each level, and do a deep equality check.
Any ideas how I can get an O(1) lookup by value?
seems the most suitable data structures for your task are HashMap and Set (based on HashMap). The average time for insert and getting is O(1) https://adrianmejia.com/data-structures-time-complexity-for-beginners-arrays-hashmaps-linked-lists-stacks-queues-tutorial
Would you like to try serialization with hash alongside with your value? I mean, something like:
const cache = {
[key1]: {
[key2]: {
[key3]: {
[resultValue]: { a: 5, b: 6 },
[resultHash]: md5(JSON.stringify(val))
}
}
}
}
Browsers doesn't have any built-in hash functions API. So, get it from npmjs.org
UPDATE:
I may have misunderstood your question. What about this implementation?
const cache = new Map()
const hash = data => btoa(JSON.stringify(data))
const hashKeys = (...keys) => keys.map(key => hash(key)).join('-')
const store = (data, ...keys) => cache[hashKeys(...keys)] = data
const load = (...keys) => cache[hashKeys(...keys)]