Hashing de estado de bits

El hash de estado de bits es un método de hash inventado en 1968 por Morris. ^{[ 1 ]} Se utiliza para el hash de estado, donde cada estado (por ejemplo, de un autómata) está representado por un número y se pasa a alguna función hash .

El resultado de la función se toma entonces como índice de una matriz de bits (un campo de bits ), donde se busca el valor 1 si el estado ya se ha visto antes o se almacena el valor 1 por sí mismo si no es así.

Generalmente sirve como una técnica de sí/no sin necesidad de almacenar la representación completa del estado en bits.

Una desventaja de este marco es la pérdida de precisión, similar a la de otras técnicas de hash. Por ello, algunas herramientas utilizan esta técnica con más de una función hash, de modo que el campo de bits se amplía con el número de funciones utilizadas, cada una con su propia fila. Incluso después de que todos los valores de retorno de las funciones (los índices) apunten a campos con contenido igual a 1, el estado puede considerarse visitado con mucha mayor probabilidad.

El hash de estado de bits, aunque se propuso con anterioridad, es una aplicación de los filtros de Bloom . ^{[ 2 ]}

• El hash de estado de bits se utiliza en el verificador de modelos SPIN para determinar si un estado ya ha sido visitado por un algoritmo de búsqueda en profundidad anidada . Esto supuestamente generó un ahorro de memoria del 98 % al usar una función hash (de 175 MB a 3 MB) y del 92 % al usar dos funciones hash (13 MB). La cobertura de estados se redujo al 97 % en el primer caso. ^{[ 3 ]}