Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pl.comp.programming > #34139
| From | Mateusz Viste <mateusz@xyz.invalid> |
|---|---|
| Newsgroups | pl.comp.programming |
| Subject | Re: Hasz dla permutacji |
| Date | 2020-08-24 10:20 +0200 |
| Organization | . . . |
| Message-ID | <20200824102034.5b84b398@mateusz> (permalink) |
| References | <5f43602a$0$525$65785112@news.neostrada.pl> <5f4375ff$0$514$65785112@news.neostrada.pl> |
2020-08-24 o 10:10 +0200, Borneq napisał: > On 8/24/20 8:37 AM, Borneq wrote: > > Mam permutację np. 5 7 1 2 8 ..4 > > chce każdą oznaczyć haszem, chętnie 64 bitowym by uniknąć kolizji > > 32 bitów choć ostatecznie 32 bity to też male prawdopodobieństwo > > kolizji. Ma mieć własności: > > - nie działam na bitach ale na liczbach, np. 1204 999 451 1021... > > nieduże liczby > > > > - prosty hasz z możliwością generowania przyrostowego: > > jak zamieniam liczbę numer 21 z 45 to ze starego generuję nowy > > hasz, najlepiej nie z całej tablicy, tak działa prosty XOR, tylko > > problem: ma być conajmniej 32 bity a nie tyle bitów ile mają > > liczby > > XOR jest nieczuły na kolejność, więc xor wraz z numerem pozycji: > 0 xor tab[0] xor 1 xor tab[1] xor 2 xor tab[2] xor... > wada: dla małych liczb hash będzie mały, nie całe 32/64 bity, więc > byłoby niebezpieczeństwo że dwie permiutacje będą miały ten sam hash. Rób dwie operacje: xor oraz shift jednego bitu... Tak działa BSD sum. Zalety takie, że jeszt bardzo szybki oraz wrażliwy na inwersję wartości. Szerokość takiego hashu sobie możesz dopasować sam, wystarczy użyć innego clampingu. 3 lata temu popełniłem tego implementację: https://sourceforge.net/p/bsum/code/HEAD/tree/trunk/bsum.asm Mateusz
Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Hasz dla permutacji Borneq <borneq@antyspam.hidden.pl> - 2020-08-24 08:37 +0200
Re: Hasz dla permutacji Borneq <borneq@antyspam.hidden.pl> - 2020-08-24 10:10 +0200
Re: Hasz dla permutacji Mateusz Viste <mateusz@xyz.invalid> - 2020-08-24 10:20 +0200
Re: Hasz dla permutacji Borneq <borneq@antyspam.hidden.pl> - 2020-08-24 13:31 +0200
Re: Hasz dla permutacji Mateusz Viste <mateusz@xyz.invalid> - 2020-08-24 13:48 +0200
Re: Hasz dla permutacji Borneq <borneq@antyspam.hidden.pl> - 2020-08-24 13:52 +0200
Re: Hasz dla permutacji Mateusz Viste <mateusz@xyz.invalid> - 2020-08-24 13:57 +0200
Re: Hasz dla permutacji Borneq <borneq@antyspam.hidden.pl> - 2020-08-24 10:46 +0200
csiph-web