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