Bitstate hashing
 | Ovaj članak je započet ili proširen kroz projekat seminarskih radova. Potrebno je proveriti prevod, pravopis i viki-sintaksu. Kada završite sa proverom, dopišete da nakon |provereno=. |
Bitstate hashing je hashing metoda, koju je izmislio Moris[1] 1968. Koristi se za state hashing(heširanje stanja), gde je svako стање prikazano/predstavljeno brojem i to odgovara nekim hash funkcijama.
Rezultat funkcije se zatim uzima kao indeks za niz bitova(a bit-field), gde jedan pretražuje 1, ako je već ranije posećen ili, u suprotnom, čuva 1.
Uobičajeno se koristi kao da-ne tehnika bez potrebe čuvanja svih stanja bitova. A čak i posle povratnih vrednosti svih funkcija(indeksi) ukazuju na polja sa sadržajem jednakim 1, stanje može biti proglašeno kao posećeno, sa mnogo većom verovatnoćom.
Korišćenje
[uredi | uredi izvor]- Koristi se kao SPIN model, gde proveravanja da li je stanje već posećeno po DFS(nested-depth-first search) algoritmu pretrage ili nije. Spominje se ušteda memorije od 98%, u slučaju korišćenja jedne heš funkcije( 175mb do 3mb) i 92% gde se koriste dve heš funkcije (13mb). Pokrivenost stanja je pala na 97% u prvom slučaju.[2]