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 automaton) is represented by a number and it is passed to some hash function.

The result of the function is then taken as 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 yes-no technique without need of storing whole state bit representation.

Shortcoming of this framework is loosing precision like in other hashing techniques. Hence some tools using this technique with more then one hash function so that the bit-field gets widened by the number of used functions.

Usage

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