J'ai besoin de convertir des chaînes en une forme de hachage. Est-ce possible en JavaScript?
Je n'utilise pas de langage côté serveur, je ne peux donc pas le faire de cette façon.
javascript
hash
Freesnöw
la source
la source
Réponses:
Source: http://werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method/
la source
hash << 5 - hash
la même chosehash * 31 + char
mais beaucoup plus rapide. C'est bien parce que c'est tellement rapide, et 31 est un petit nombre premier. Gagner y gagner.(hash * 31) + char
est identique à la sortie produite par le code basé sur le décalage((hash<<5)-hash)+char
, même pour les chaînes très longues (je l'ai testé avec des chaînes contenant plus d'un million de caractères), donc ce n'est pas "inutilisable" en termes de précision. La complexité est O (n) pour les versions basées sur les nombres et sur les équipes, donc elle n'est pas "inutilisable" en termes de complexité.n
, quelle est la plus granden
pour laquelle je ne peux pas avoir de collision?var hashCode = function hashCode (str) {etc...}
? Et puis utiliser commehashCode("mystring")
?ÉDITER
sur la base de mes tests jsperf, la réponse acceptée est en fait plus rapide: http://jsperf.com/hashcodelordvlad
ORIGINAL
si quelqu'un est intéressé, voici une version améliorée (plus rapide), qui échouera sur les navigateurs plus anciens qui n'ont pas la
reduce
fonction tableau.version de fonction flèche à une ligne:
la source
En réponse à cette question Quel algorithme de hachage est le meilleur pour l'unicité et la vitesse? , Ian Boyd a publié une bonne analyse approfondie . En bref (comme je l'interprète), il arrive à la conclusion que Murmur est le meilleur, suivi de FNV-1a.
L'algorithme String.hashCode () de Java proposé par esmiralha semble être une variante de DJB2.
Quelques benchmarks avec de grandes chaînes d'entrée ici: http://jsperf.com/32-bit-hash
Lorsque des chaînes d'entrée courtes sont hachées, les performances de murmure chutent, par rapport à DJ2B et FNV-1a: http://jsperf.com/32- bit-hash / 3
Donc, en général, je recommanderais murmur3.
Voir ici pour une implémentation JavaScript: https://github.com/garycourt/murmurhash-js
Si les chaînes d'entrée sont courtes et que les performances sont plus importantes que la qualité de distribution, utilisez DJB2 (comme proposé par la réponse acceptée par esmiralha).
Si la qualité et la petite taille du code sont plus importantes que la vitesse, j'utilise cette implémentation de FNV-1a (basée sur ce code ).
Améliorez la probabilité de collision
Comme expliqué ici , nous pouvons étendre la taille des bits de hachage en utilisant cette astuce:
Utilisez-le avec soin et n'en attendez pas trop.
la source
("0000000" + (hval >>> 0).toString(16)).substr(-8);
? N'est-ce pas la même chose que(hval >>> 0).toString(16)
?hval
, il(hval >>> 0).toString(16)
peut contenir moins de 8 caractères, vous devez donc le remplir avec des zéros. J'étais juste confus, car(hval >>> 0).toString(16)
il en résultait toujours pour moi une chaîne de 8 caractères exactement.Math.imul
fonction ES6 . Cela en fait à lui seul des références de référence, et finalement un meilleur choix que DJB2 à long terme.Basé sur la réponse acceptée dans ES6. Plus petit, maintenable et fonctionne dans les navigateurs modernes.
EDIT (2019-11-04) :
version de fonction flèche à une ligne:
la source
str += ""
avant le hachage pour éviter les exceptionsstr.split is not a function
levées lorsque des non-chaînes ont été passées en tant que paramètreshash |= 0
pour convertir en un entier 32 bits. Cette implémentation ne fonctionne pas. Est-ce un bug?Avec cela à l'écart, voici quelque chose de mieux - cyrb53 , un hachage 53 bits simple mais de haute qualité. Il est assez rapide, offre une très bonne distribution de hachage et présente des taux de collision nettement inférieurs à ceux de tout hachage 32 bits.
Semblable aux algorithmes MurmurHash / xxHash bien connus, il utilise une combinaison de multiplication et de Xorshift pour générer le hachage, mais pas aussi complètement. En conséquence, c'est plus rapide qu'en JavaScript et beaucoup plus simple à mettre en œuvre.
Il réalise une avalanche (non stricte), ce qui signifie essentiellement que de petits changements dans l'entrée ont de grands changements dans la sortie, ce qui fait que le hachage résultant semble aléatoire:
Vous pouvez également fournir une valeur de départ pour des flux alternatifs de la même entrée:
Techniquement, il s'agit d'un hachage 64 bits (deux hachages 32 bits non corrélés en parallèle), mais JavaScript est limité à des entiers 53 bits. Si nécessaire, la sortie 64 bits complète peut toujours être utilisée en modifiant la ligne de retour pour une chaîne hexadécimale ou un tableau.
Sachez que la construction de chaînes hexadécimales peut considérablement ralentir le traitement par lots dans des situations critiques pour les performances.
Et juste pour le plaisir, voici un hachage 32 bits minimal en 89 caractères avec une qualité supérieure à celle de FNV ou DJB2:
la source
ch
initialisé?'imul'
.Si cela aide quelqu'un, j'ai combiné les deux premières réponses dans une version plus ancienne,
reduce
compatible avec les navigateurs, qui utilise la version rapide si elle est disponible et revient à la solution d'esmiralha si elle ne l'est pas.L'utilisation est comme:
la source
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; }
Il s'agit d'une variante raffinée et plus performante:
Cela correspond à l'implémentation Java de la norme
object.hashCode()
Voici également celui qui ne renvoie que des codes de hachage positifs:
Et voici un correspondant pour Java qui ne renvoie que des codes de hachage positifs:
Prendre plaisir!
la source
Je suis un peu surpris que personne n'ait encore parlé de la nouvelle API SubtleCrypto .
Pour obtenir un hachage à partir d'une chaîne, vous pouvez utiliser la
subtle.digest
méthode:la source
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
n'est pas exactement performante.Grâce à l'exemple de mar10, j'ai trouvé un moyen d'obtenir les mêmes résultats en C # ET Javascript pour un FNV-1a. Si des caractères unicode sont présents, la partie supérieure est supprimée pour des raisons de performances. Je ne sais pas pourquoi il serait utile de les conserver lors du hachage, car je ne hache que les chemins d'URL pour l'instant.
Version C #
Version JavaScript
la source
Math.imul
peut être utilisé pour l'étape de multiplication, ce qui améliore considérablement les performances . Le seul problème est que cela ne fonctionnera pas dans IE11 sans cale .Un rapide et concis qui a été adapté à partir d' ici :
la source
J'avais besoin d'une fonction similaire (mais différente) pour générer un identifiant unique basé sur le nom d'utilisateur et l'heure actuelle. Donc:
Produit:
modifier juin 2015: pour le nouveau code, j'utilise shortid: https://www.npmjs.com/package/shortid
la source
Ma doublure rapide (très longue) basée sur la
Multiply+Xor
méthode FNV :la source
SubtleCrypto.digest
Êtes-vous sûr de ne pas pouvoir procéder de cette façon ?
Avez-vous oublié que vous utilisez Javascript, la langue en constante évolution?
Essayez
SubtleCrypto
. Il prend en charge les fonctions de hachage SHA-1, SHA-128, SHA-256 et SHA-512.la source
Je suis un peu en retard à la fête, mais vous pouvez utiliser ce module: crypto :
Le résultat de cette fonction est toujours une
64
chaîne de caractères; quelque chose comme ça:"aa54e7563b1964037849528e7ba068eb7767b1fab74a8d80fe300828b996714a"
la source
J'ai combiné les deux solutions (utilisateurs esmiralha et lordvlad) pour obtenir une fonction qui devrait être plus rapide pour les navigateurs prenant en charge la fonction js reduction () et toujours compatible avec les anciens navigateurs:
Exemple:
la source
Si vous souhaitez éviter les collisions, vous pouvez utiliser un hachage sécurisé comme SHA-256 . Il existe plusieurs implémentations JavaScript SHA-256.
J'ai écrit des tests pour comparer plusieurs implémentations de hachage, voir https://github.com/brillout/test-javascript-hash-implementations .
Ou accédez à http://brillout.github.io/test-javascript-hash-implementations/ , pour exécuter les tests.
la source
Cela devrait être un hachage un peu plus sécurisé que certaines autres réponses, mais dans une fonction, sans source préchargée
J'ai essentiellement créé une version simplifiée simplifiée de sha1.
Vous prenez les octets de la chaîne et les regroupez par "mots" de 4 à 32 bits.
Ensuite, nous étendons tous les 8 mots à 40 mots (pour un impact plus important sur le résultat).
Cela va à la fonction de hachage (la dernière réduction) où nous faisons quelques calculs avec l'état actuel et l'entrée. Nous obtenons toujours 4 mots.
C'est presque une version à une commande / une ligne utilisant la carte, réduire ... au lieu de boucles, mais c'est toujours assez rapide
nous convertissons également la sortie en hexadécimal pour obtenir une chaîne au lieu d'un tableau de mots.
L'utilisation est simple. par exemple
"a string".hash()
reviendra"88a09e8f9cc6f8c71c4497fbb36f84cd"
Afficher l'extrait de code
la source
J'ai opté pour une simple concaténation des codes de caractères convertis en chaînes hexadécimales. Cela sert un objectif relativement étroit, à savoir avoir juste besoin d'une représentation de hachage d'une chaîne SHORT (par exemple, titres, balises) à échanger avec un côté serveur qui, pour des raisons non pertinentes, ne peut pas facilement implémenter le port Java hashCode accepté. Évidemment aucune application de sécurité ici.
Cela peut être rendu plus concis et tolérant au navigateur avec Underscore. Exemple:
Je suppose que si vous vouliez hacher des chaînes plus grandes de la même manière, vous pourriez simplement réduire les codes de caractères et hexifier la somme résultante plutôt que de concaténer les caractères individuels ensemble:
Naturellement plus de risques de collision avec cette méthode, bien que vous puissiez jouer avec l'arithmétique dans la réduction, mais vous vouliez diversifier et allonger le hachage.
la source
Version légèrement simplifiée de la réponse de @ esmiralha.
Je ne remplace pas String dans cette version, car cela pourrait entraîner un comportement indésirable.
la source
Ajouter cela parce que personne ne l'a encore fait, et cela semble être demandé et implémenté beaucoup avec des hachages, mais c'est toujours très mal fait ...
Cela prend une entrée de chaîne et un nombre maximum que vous souhaitez que le hachage soit égal et produit un nombre unique basé sur l'entrée de chaîne.
Vous pouvez l'utiliser pour produire un index unique dans un tableau d'images (si vous souhaitez renvoyer un avatar spécifique pour un utilisateur, choisi au hasard, mais également choisi en fonction de son nom, il sera donc toujours attribué à quelqu'un avec ce nom ).
Vous pouvez également l'utiliser, bien sûr, pour renvoyer un index dans un tableau de couleurs, comme pour générer des couleurs d'arrière-plan d'avatar uniques en fonction du nom de quelqu'un.
la source
Je ne vois aucune raison d'utiliser ce code cryptographique trop compliqué au lieu de solutions prêtes à l'emploi, comme une bibliothèque de hachage d'objets, etc., compter sur le fournisseur est plus productif, fait gagner du temps et réduit les coûts de maintenance.
Utilisez simplement https://github.com/puleos/object-hash
la source
var crypto = require('crypto');
. Je pense qu'il ajoute ce code de dépendance du fournisseur dans la version minifiée lors d'une build.