Quiero crear un caché donde tengo búsquedas O(1) de su contenido, y busco claves por valor, no por referencia. ¿Qué estructura de datos en JS, si hay alguna, me permitiría lograr esto?
Requisitos:
Lo que he probado :
Estaba pensando en Mapas anidados siguiendo esta estructura:
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.Y esto funcionaría bien para las búsquedas de O(1) por referencia , pero por valor aún necesitaría iterar las claves en cada nivel y hacer una verificación de igualdad profunda.
¿Alguna idea de cómo puedo obtener una búsqueda de O (1) por valor?
parece que las estructuras de datos más adecuadas para su tarea son HashMap y Set (basado en HashMap). El tiempo promedio para insertar y obtener es O(1) https://adrianmejia.com/data-structures-time-complexity-for-beginners-arrays-hashmaps-linked-lists-stacks-queues-tutorial
¿Le gustaría probar la serialización con hash junto con su valor? Quiero decir, algo como:
const cache = { [key1]: { [key2]: { [key3]: { [resultValue]: { a: 5, b: 6 }, [resultHash]: md5(JSON.stringify(val)) } } } }Los navegadores no tienen ninguna API de funciones hash incorporada. Entonces, obténgalo de npmjs.org
ACTUALIZAR:
Puede que haya entendido mal tu pregunta. ¿Qué pasa con esta implementación?
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)]