¿Cuál es el mejor método para determinar si una identificación está en un conjunto sin almacenar el conjunto completo?
Tengo una aplicación limitada de almacenamiento en la que se debe verificar si un ID está en un conjunto o no. Se espera que el conjunto total de IDs sea de 1k a 10k, lo cual es engorroso de almacenar y creará demasiado tráfico aguas arriba para verificar los IDs individualmente con la base de datos principal.
Sin tener acceso al conjunto completo, ¿existe un algoritmo que permita a la aplicación verificar si un ID está en el conjunto? Es factible realizar cálculos más exhaustivos de forma remota antes de almacenar los datos en el hardware de la aplicación si eso ayuda a reducir el almacenamiento necesario.
Tengo experiencia limitada en algoritmos de datos, pero estoy imaginando alguna función donde nuestro dominio de IDs aprobados tenga un único valor (o un rango limitado de valores) de salida que podamos almacenar en el hardware de la aplicación. Por otro lado, los IDs que no estén en los IDs aprobados no se superpondrán con este rango de salida, al menos con una certeza razonable. La función debería funcionar con valores de ID arbitrarios, ya que es posible que necesiten ser activados/desactivados en el futuro.
¿Es posible algo así? ¿Existe algún algoritmo de datos que pueda ser útil para este caso?
davy.ai
Una posible solución a este problema es utilizando una función hash. Una función hash puede tomar una entrada (en este caso, un ID) y generar un valor hash de longitud fija. Este valor hash luego puede ser almacenado en el hardware de la aplicación, ocupando un espacio de almacenamiento mínimo.
Al verificar si un ID está en el conjunto, la aplicación simplemente puede generar el hash del ID y compararlo con los valores hash almacenados. Si los valores hash coinciden, entonces el ID está en el conjunto. Si los valores hash no coinciden, entonces el ID no está en el conjunto.
Es importante tener en cuenta que debido a la naturaleza de las funciones hash, existe la posibilidad de colisiones de hash donde dos valores de entrada diferentes pueden producir el mismo valor hash de salida. Sin embargo, esto se puede mitigar utilizando una buena función hash y verificando las colisiones para garantizar la precisión.
En general, el uso de una función hash puede reducir significativamente los requisitos de almacenamiento y el tráfico hacia arriba, al mismo tiempo que permite a la aplicación verificar eficientemente si un ID está en el conjunto.