Muszę przekonwertować ciągi znaków na jakąś formę skrótu. Czy jest to możliwe w JavaScript?
Nie używam języka po stronie serwera, więc nie mogę tego zrobić w ten sposób.
javascript
hash
Freesnöw
źródło
źródło
Odpowiedzi:
Źródło: http://werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method/
źródło
hash << 5 - hash
jest to samo,hash * 31 + char
ale dużo DUŻO. Fajnie, bo jest tak szybki, a 31 to mała liczba pierwsza. Wygraj tam, wygraj.(hash * 31) + char
są identyczne z danymi wyjściowymi wygenerowanymi przez kod oparty na przesunięciu((hash<<5)-hash)+char
, nawet dla bardzo długich ciągów (przetestowałem to z ciągami zawierającymi ponad milion znaków), więc nie jest to „bezużyteczne” pod względem dokładności. Złożoność wynosi O (n) zarówno dla wersji opartych na liczbach, jak i wersji z przesunięciem, więc nie jest „bezużyteczna” pod względem złożoności.n
, to jaki jest największy,n
dla którego nie mogę mieć kolizji?var hashCode = function hashCode (str) {etc...}
? A następnie użyć jakohashCode("mystring")
?EDYTOWAĆ
na podstawie moich testów jsperf, zaakceptowana odpowiedź jest w rzeczywistości szybsza: http://jsperf.com/hashcodelordvlad
ORYGINALNY
jeśli ktoś jest zainteresowany, oto ulepszona (szybsza) wersja, która zawiedzie w starszych przeglądarkach, które nie mają
reduce
funkcji tablicowej.wersja z funkcją strzałki w jednym wierszu:
źródło
W odpowiedzi na to pytanie Który algorytm mieszania jest najlepszy dla wyjątkowości i szybkości? Ian Boyd opublikował dobrą dogłębną analizę . Krótko mówiąc (jak to interpretuję), dochodzi do wniosku, że Murmur jest najlepszy, a następnie FNV-1a.
Algorytm String.hashCode () Javy zaproponowany przez esmiralha wydaje się być wariantem DJB2.
Niektóre testy porównawcze z dużymi ciągami wejściowymi tutaj: http://jsperf.com/32-bit-hash
Po skróceniu krótkich ciągów wejściowych wydajność szmeru spada, w porównaniu do DJ2B i FNV-1a: http://jsperf.com/32- bit-hash / 3
Ogólnie więc polecam murmur3.
Zobacz tutaj implementację JavaScript: https://github.com/garycourt/murmurhash-js
Jeśli ciągi wejściowe są krótkie, a wydajność jest ważniejsza niż jakość dystrybucji, użyj DJB2 (zgodnie z propozycją przyjętą przez esmiralha).
Jeśli jakość i mały rozmiar kodu są ważniejsze niż szybkość, używam tej implementacji FNV-1a (na podstawie tego kodu ).
Popraw prawdopodobieństwo kolizji
Jak wyjaśniono tutaj , możemy zwiększyć rozmiar bitu skrótu za pomocą tej sztuczki:
Używaj go ostrożnie i nie oczekuj jednak zbyt wiele.
źródło
("0000000" + (hval >>> 0).toString(16)).substr(-8);
? Czy to nie to samo co(hval >>> 0).toString(16)
?hval
,(hval >>> 0).toString(16)
może być mniejsza niż 8 znaków, więc pad to zerami. Byłem po prostu zdezorientowany, ponieważ(hval >>> 0).toString(16)
zawsze skutkowało to ciągiem dokładnie 8 znaków.Math.imul
funkcji ES6 . Już samo to czyni go najlepszymi wzorcami, a ostatecznie lepszym wyborem na dłuższą metę niż DJB2.Na podstawie zaakceptowanej odpowiedzi w ES6. Mniejszy, łatwy w utrzymaniu i działa w nowoczesnych przeglądarkach.
EDYCJA (04.11.2019) :
wersja z funkcją strzałki w jednym wierszu:
źródło
str += ""
przed mieszaniem, aby uniknąć wyjątkustr.split is not a function
hash |= 0
do konwersji na 32-bitową liczbę int. Ta implementacja nie. Czy to błąd?Poza tym jest coś lepszego - cyrb53 , prosty, ale wysokiej jakości 53-bitowy skrót. Jest dość szybki, zapewnia bardzo dobrą dystrybucję skrótu i ma znacznie niższe współczynniki kolizji w porównaniu do dowolnego skrótu 32-bitowego.
Podobnie jak w dobrze znanych algorytmach MurmurHash / xxHash, wykorzystuje kombinację mnożenia i Xorshift do generowania skrótu, ale nie jest tak dokładny. W rezultacie jest szybszy niż w JavaScript i znacznie łatwiejszy do wdrożenia.
Osiąga lawinę (nie ścisłą), co w zasadzie oznacza, że małe zmiany na wejściu mają duże zmiany na wyjściu, dzięki czemu powstały skrót jest losowy:
Możesz także podać źródło dla alternatywnych strumieni tego samego wejścia:
Technicznie jest to 64-bitowy skrót (dwa nieskorelowane 32-bitowe skróty równolegle), ale JavaScript jest ograniczony do 53-bitowych liczb całkowitych. W razie potrzeby można nadal korzystać z pełnego 64-bitowego wyjścia, zmieniając wiersz zwrotny dla łańcucha szesnastkowego lub tablicy.
Należy pamiętać, że tworzenie ciągów szesnastkowych może drastycznie spowolnić przetwarzanie wsadowe w sytuacjach krytycznych pod względem wydajności.
I dla zabawy, oto minimalny 32-bitowy skrót w 89 znakach o wyższej jakości niż nawet FNV lub DJB2:
źródło
ch
inicjowany?'imul'
.Jeśli to komukolwiek pomaga, połączyłem dwie pierwsze odpowiedzi w starszą wersję odporną na przeglądarkę, która używa szybkiej wersji, jeśli
reduce
jest dostępna, i wraca do rozwiązania esmiralha, jeśli nie jest.Użycie jest jak:
źródło
String.prototype.hashCode = function(){ var hash = 5381; if (this.length === 0) return hash; for (var i = 0; i < this.length; i++) { var character = this.charCodeAt(i); hash = ((hash<<5)+hash)^character; // Convert to 32bit integer } return hash; }
To jest wyrafinowany i lepiej działający wariant:
Jest to zgodne z implementacją standardu przez Javę
object.hashCode()
Oto także taki, który zwraca tylko pozytywne kody skrótu:
A oto pasujący do Java, który zwraca tylko pozytywne kody skrótu:
Cieszyć się!
źródło
Jestem trochę zaskoczony, że nikt jeszcze nie mówił o nowym API SubtleCrypto .
Aby uzyskać skrót z ciągu, możesz użyć
subtle.digest
metody:źródło
var promise = crypto.subtle.digest({name: "SHA-256"}, Uint8Array.from(data)); promise.then(function(result){ console.log(Array.prototype.map.call(new Uint8Array(result), x => x.toString(16).padStart(2, '0')).join('')); });
crypto
nie jest dokładnie wydajna.Dzięki przykładowi autorstwa mar10 znalazłem sposób na uzyskanie takich samych wyników w C # ORAZ Javascript dla FNV-1a. Jeśli występują znaki Unicode, górna część jest odrzucana ze względu na wydajność. Nie wiem, dlaczego warto utrzymywać je podczas mieszania, ponieważ na razie mam tylko ścieżki adresów URL.
Wersja C #
Wersja JavaScript
źródło
Math.imul
można go użyć do pomnożenia, co znacznie poprawia wydajność . Jedynym problemem jest to, że nie będzie działać w IE11 bez podkładki .Szybki i zwięzły, który został dostosowany stąd :
źródło
Potrzebowałem podobnej (ale innej) funkcji do wygenerowania unikalnego identyfikatora na podstawie nazwy użytkownika i aktualnego czasu. Więc:
Produkuje:
edytuj czerwiec 2015: Do nowego kodu używam shortid: https://www.npmjs.com/package/shortid
źródło
Moja szybka (bardzo długa) jedna wkładka oparta na
Multiply+Xor
metodzie FNV :źródło
SubtleCrypto.digest
Czy na pewno nie możesz tego zrobić w ten sposób ?
Czy zapomniałeś, że używasz Javascript, języka ciągle ewoluującego?
Spróbować
SubtleCrypto
. Obsługuje funkcje skrótu SHA-1, SHA-128, SHA-256 i SHA-512.źródło
Jestem trochę spóźniony na imprezę, ale możesz użyć tego modułu: crypto :
Wynikiem tej funkcji jest zawsze
64
ciąg znaków; coś takiego:"aa54e7563b1964037849528e7ba068eb7767b1fab74a8d80fe300828b996714a"
źródło
Połączyłem oba rozwiązania (użytkownicy esmiralha i lordvlad), aby uzyskać funkcję, która powinna być szybsza w przeglądarkach obsługujących funkcję js redukuj () i nadal kompatybilnych ze starymi przeglądarkami:
Przykład:
źródło
Jeśli chcesz uniknąć kolizji, możesz użyć bezpiecznego skrótu, takiego jak SHA-256 . Istnieje kilka implementacji JavaScript SHA-256.
Napisałem testy, aby porównać kilka implementacji skrótu, patrz https://github.com/brillout/test-javascript-hash-implementations .
Lub przejdź do http://brillout.github.io/test-javascript-hash-implementations/ , aby uruchomić testy.
źródło
Powinien to być nieco bezpieczniejszy skrót niż niektóre inne odpowiedzi, ale w funkcji, bez żadnego wstępnie załadowanego źródła
Stworzyłem w zasadzie zminimalizowaną uproszczoną wersję sha1.
Bierzesz bajty ciągu i grupujesz je według 4 do 32-bitowych „słów”.
Następnie rozszerzamy każde 8 słów do 40 słów (dla większego wpływu na wynik).
To odnosi się do funkcji skrótu (ostatnie zmniejszenie), gdzie robimy matematykę z bieżącym stanem i danymi wejściowymi. Zawsze dostajemy 4 słowa.
Jest to prawie jedna wersja z jednym poleceniem / jedna linia, korzystająca z mapowania, zmniejszania ... zamiast pętli, ale wciąż jest dość szybka
konwertujemy również dane wyjściowe na hex, aby uzyskać ciąg zamiast tablicy słów.
Użycie jest proste. na przykład
"a string".hash()
wróci"88a09e8f9cc6f8c71c4497fbb36f84cd"
Pokaż fragment kodu
źródło
Poszedłem do prostej konkatenacji kodów char przekonwertowanych na ciągi szesnastkowe. Służy to względnie wąskiemu celowi, a mianowicie potrzebie wymiany skrótu w postaci ciągu KRÓTKIEGO (np. Tytułów, znaczników) do wymiany po stronie serwera, który z nieistotnych powodów nie może łatwo wdrożyć zaakceptowanego portu Java hashCode. Oczywiście nie ma tutaj aplikacji zabezpieczającej.
Dzięki Underscore można to uczynić bardziej zwięzłym i bardziej tolerancyjnym dla przeglądarki. Przykład:
Podejrzewam, że jeśli chcesz mieszać większe ciągi w podobny sposób, możesz po prostu zmniejszyć kody znaków i heksyfikować wynikową sumę, zamiast łączyć poszczególne znaki razem:
Naturalnie większe ryzyko kolizji z tą metodą, choć możesz manipulować arytmetyką w redukcji, jednak chciałeś urozmaicić i wydłużyć skrót.
źródło
Nieco uproszczona wersja odpowiedzi @ esmiralha.
W tej wersji nie zastępuję ciągu znaków, ponieważ może to spowodować niepożądane zachowanie.
źródło
Dodanie tego, ponieważ nikt jeszcze tego nie zrobił, i wydaje się, że o to proszono i zaimplementowano wiele z hashami, ale zawsze robi się to bardzo źle ...
To wymaga wprowadzenia ciągu znaków i maksymalnej liczby, która ma być równa wartości skrótu, i tworzy unikalną liczbę na podstawie wejścia ciągu.
Możesz użyć tego do stworzenia unikalnego indeksu w tablicy obrazów (jeśli chcesz zwrócić określony awatar dla użytkownika, wybrany losowo, ale także wybrany na podstawie jego nazwiska, więc zawsze będzie przypisany do osoby o tej nazwie ).
Możesz również użyć tego, oczywiście, aby zwrócić indeks do tablicy kolorów, na przykład do generowania unikalnych kolorów tła awatara na podstawie czyjegoś imienia.
źródło
Nie widzę powodu, aby używać tego skomplikowanego kodu kryptograficznego zamiast gotowych rozwiązań, takich jak biblioteka skrótów obiektowych itp. Poleganie na dostawcy jest bardziej wydajne, oszczędza czas i zmniejsza koszty utrzymania.
Wystarczy użyć https://github.com/puleos/object-hash
źródło
var crypto = require('crypto');
. Myślę, że dodaje ten kod zależności od dostawcy w wersji zminimalizowanej podczas kompilacji.