Пређи на садржај

Bitstate hashing

С Википедије, слободне енциклопедије

Bitstate hashing је hashing метода, коју је измислио Морис[1] 1968. Користи се за state hashing(хеширање стања), где је свако стање приказано/представљено бројем и то одговара неким hash функцијама.

Резултат функције се затим узима као индекс за низ битова(a bit-field), где један претражује 1, ако је већ раније посећен или, у супротном, чува 1.

Уобичајено се користи као да-не техника без потребе чувања свих стања битова. А чак и после повратних вредности свих функција(индекси) указују на поља са садржајем једнаким 1, стање може бити проглашено као посећено, са много већом вероватноћом.

Коришћење

[уреди | уреди извор]
  • Користи се као SPIN модел, где проверавања да ли је стање већ посећено по ДФС(nested-depth-first search) алгоритму претраге или није. Спомиње се уштеда меморије од 98%, у случају коришћења једне хеш функције( 175мб до 3мб) и 92% где се користе две хеш функције (13мб). Покривеност стања је пала на 97% у првом случају.[2]

Референце

[уреди | уреди извор]
  1. ^ Morris, R. (1968). Scatter Storage Techniques
  2. ^ Holzmann, G. J. (2003) Addison Wesley. Spin Model Checker, The: Primer and Reference Manual