Bitstate hashing

Bitstate hashing is a hashing method invented in 1968 by Morris. It is used for state hashing, where each state (e.g. of an automaton) is represented by a number and it is passed to some hash function.

The result of the function is then taken as the index to an array of bits (a bit-field), where one looks for 1 if the state was already seen before or stores 1 by itself if not.

It usually serves as a yes–no technique without a need of storing whole state bit representation.

A shortcoming of this framework is losing precision like in other hashing techniques. Hence some tools use this technique with more than one hash function so that the bit-field gets widened by the number of used functions.

Use

• It is utilized in SPIN model checker for decision whether a state was already visited by nested-depth-first search searching algorithm or not.