Bitstate hashing is a
hashing
Hash, hashes, hash mark, or hashing may refer to:
Substances
* Hash (food), a coarse mixture of ingredients
* Hash, a nickname for hashish, a cannabis product
Hash mark
* Hash mark (sports), a marking on hockey rinks and gridiron football fiel ...
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
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually u ...
.
The result of the function is then taken as the index to an array of bits (a
bit-field
A bit field is a data structure that consists of one or more adjacent bits which have been allocated for specific purposes, so that any single bit or group of bits within the structure can be set or inspected. A bit field is most commonly used to ...
), 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, each having its own row. And even after all functions return values (the indices) point to fields with contents equal to 1, the state may be uttered as visited with much higher probability.
Use
* Bitstate hashing is utilized in the
SPIN
Spin or spinning most often refers to:
* Spinning (textiles), the creation of yarn or thread by twisting fibers together, traditionally by hand spinning
* Spin, the rotation of an object around a central axis
* Spin (propaganda), an intentionally b ...
model checker for deciding whether a state was already visited by a nested-
depth-first search
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alon ...
algorithm or not. This purportedly led to memory savings of 98% in the case of using one hash function (175 MB to 3 MB) and 92% when two hash functions are used (13 MB). The state coverage dropped to 97% in the former case.
[Holzmann, G. J. (2003) Addison Wesley. ''Spin Model Checker, The: Primer and Reference Manual'']
References
Hash functions