Szybka niska kolizja nie krypto-mieszania w JavaScript dla plików

Question

Poszukuję szybkiego skrótu z niskimi kolizjami zaimplementowanymi w JavaScript. Nie musi to być skrót kryptograficzny. Zasadniczo używam go jako sposobu sprawdzenia, czy dany plik został już załadowany (lub częściowo przesłany) na konto użytkownika, aby zaoszczędzić trochę czasu na przesyłaniu dużych plików (wideo).

Używam nowego interfejsu API pliku HTML5 do czytania w plasterkach pliku. Następnie przekazuję to do SparkMD5, aby podać mi skrót pliku. Podoba mi się fakt, że SparkMD5 pozwala mi tworzyć przyrostowe hash, więc nie muszę czytać całej rzeczy w pamięci.

Ogólnie rzecz biorąc, SparkMD5 działa na moje potrzeby, ale w przypadku dużych plików może zająć trochę czasu, aby uzyskać mój skrót (około 30 sekund dla pliku 300 MB). Idealnie chciałbym to zmniejszyć. Nie mam takiej wiedzy na temat funkcji mieszania, więc nie zamierzam przenosić czegoś i szukam idealnej biblioteki.

Answer 1

I benchmarked różne algorytmy mieszania i oto najszybsze opcje znalazłem:

• Jeśli potrzebujesz tylko 32 bitowe digest, użyj iMurmurHash. Zwróć uwagę, że spowoduje to kolizje po około 2 ** 14 (16 000) skrótów.

• Użyj SparkMD5, jeśli potrzebujesz więcej niż 32-bitów. Nie znalazłem szybkiej 64- lub 128-bitowej implementacji Murmur, ale SparkMD5 był zaskakująco szybki (75 MB/s).

  • Jeśli potrzebujesz przyrostowych aktualizacji, rozważyć dołączenie sznurki w większe kawałki przed wprowadzeniem ich do SparkMD5, jak przyrostowe mieszania SparkMD5 wydaje się cierpieć z jakimś umiarkowanym obciążeniu.

Te zalecenia dotyczą wyłącznie JavaScript. Porównywałem je za pomocą łańcuchów, ale SparkMD5 także bierze ArrayBuffers.

---

Jeśli chcesz szybkich modułów hashowania w węźle, swoje najlepsze opcje są nieco inne:

• Jeśli mieszania Bufory: Za pomocą wbudowanego modułu crypto z algorytmem MD5.

  • Wyjątkiem od tej zasady jest: Jeśli nie trzeba przyrostową hashowania, i trzeba więcej niż 500 MB przepustowość/s, i jesteś OK z native uzależnienia npm, należy murmurhash-native dla dodatkowej wydajności. Nie przetestowałem rozmiarów trawienia poniżej 128 bitów, ponieważ nawet przy 128 bitach mieszanie jest tak szybkie, że prawdopodobnie nie będzie wąskim gardłem.

    (Zauważ, że murmurhash-rodzimy technicznie obsługuje przyrostowe hashowania, ale wolniej niż Węzeł wbudowanego algorytmu MD5 w tym trybie.)

• Jeśli mieszania pojedynczy łańcuch non-stopniowo, konwertować do bufora i zobacz poprzedni punkt.

• Jeśli mieszania stopniowo ciągi:

  • Jeśli potrzebujesz tylko 32 bity, użyj iMurmurHash. Zwróć uwagę, że spowoduje to kolizje po około 2 ** 14 (16 000) skrótów.

  • Jeśli potrzebujesz więcej niż 32 bity: Użyj wbudowanego modułu kryptograficznego z algorytmem MD5.

    • Polecam również, że eksperymentowanie z łączenia ciągów razem w większe kawałki, ponieważ ciągi są niejawnie konwertowane do buforów kiedy przekazać je do modułu kryptograficznego, a każde stworzenie bufora jest dość powolna. Wydajność będzie na ogół wąska w stosunku do tworzenia bufora i łączenia ciągów, ponieważ funkcja natywnego mieszania jest bardzo szybka w porównaniu.