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.