-
Data: 2020-08-24 10:20:34
Temat: Re: Hasz dla permutacji
Od: Mateusz Viste <m...@x...invalid> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 24.08.20 10:46 Borneq
- 24.08.20 13:31 Borneq
- 24.08.20 13:48 Mateusz Viste
- 24.08.20 13:52 Borneq
- 24.08.20 13:57 Mateusz Viste
Najnowsze wątki z tej grupy
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
- Ideologia Polskiego Programisty wer.3
Najnowsze wątki
- 2024-05-03 Warszawa => Mid/Senior QA Engineer <=
- 2024-05-03 Warszawa => Mid/Senior QA Engineer <=
- 2024-05-03 Warszawa => Senior PHP Developer (Symfony) <=
- 2024-05-03 Rzeszów => UX/UI Designer <=
- 2024-05-03 Giertych przetarł szlak: byli członkowie zarządu Orlenu śledztwa prokuratorskie obserwują z zagranicy
- 2024-05-03 Warszawa => Senior Rust Software Engineer <=
- 2024-05-03 Kraków => UX/UI Designer <=
- 2024-05-03 Warszawa => International freight forwarder <=
- 2024-05-02 Silnik Stirlinga - energia mechaniczna wytwarzana z ciepła bez dostarczania paliwa!
- 2024-05-02 Kraków => Senior .Net Programmer <=
- 2024-05-02 Sprowadzenie pożaru zagrażającego mieniu w wielkich rozmiarch
- 2024-05-02 Zielona Góra => Spedytor międzynarodowy <=
- 2024-05-02 Katowice => Performance Analyst <=
- 2024-05-02 Gdańsk => Full Stack web developer (obszar .Net Core, Angular6+) <=
- 2024-05-02 Gdańsk => Business Development Manager - obszar bezpieczeństwa IT <=