About: Bitstate hashing

An Entity of Type: software, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

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.

Property Value
dbo:abstract
  • 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, 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. (en)
dbo:wikiPageID
  • 21890341 (xsd:integer)
dbo:wikiPageLength
  • 1554 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1037850047 (xsd:integer)
dbo:wikiPageWikiLink
dcterms:subject
gold:hypernym
rdf:type
rdfs:comment
  • 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. (en)
rdfs:label
  • Bitstate hashing (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License