Saya perlu mengubah string ke beberapa bentuk hash. Apakah ini mungkin dalam JavaScript?
Saya tidak menggunakan bahasa sisi server jadi saya tidak bisa melakukannya dengan cara itu.
javascript
hash
Freesnöw
sumber
sumber
Jawaban:
Sumber: http://werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method/
sumber
hash << 5 - hash
samahash * 31 + char
tapi BANYAK lebih cepat. Itu bagus karena sangat cepat, dan 31 adalah prime kecil. Menang menang di sana.(hash * 31) + char
identik dengan output yang dihasilkan oleh kode berbasis shift((hash<<5)-hash)+char
, bahkan untuk string yang sangat panjang (saya sudah mengujinya dengan string yang berisi lebih dari satu juta karakter), jadi itu tidak "tidak dapat digunakan" dalam hal akurasi. Kompleksitasnya adalah O (n) untuk versi berbasis nomor dan berbasis shift, sehingga tidak "tidak dapat digunakan" dalam hal kompleksitas.n
, apa yang terbesarn
yang saya tidak mungkin memiliki tabrakan?var hashCode = function hashCode (str) {etc...}
? Dan kemudian gunakan sebagaihashCode("mystring")
?EDIT
berdasarkan tes jsperf saya, jawaban yang diterima sebenarnya lebih cepat: http://jsperf.com/hashcodelordvlad
ASLI
jika ada yang tertarik, ini versi yang lebih baik (lebih cepat), yang akan gagal pada peramban lama yang tidak memiliki
reduce
fungsi array.versi fungsi panah satu-liner:
sumber
Dalam jawaban atas pertanyaan ini Algoritma hashing mana yang paling baik untuk keunikan dan kecepatan? , Ian Boyd memposting analisis mendalam yang baik . Singkatnya (seperti yang saya tafsirkan), ia sampai pada kesimpulan bahwa Murmur adalah yang terbaik, diikuti oleh FNV-1a.
Algoritma String.hashCode () Java yang diusulkan esmiralha tampaknya merupakan varian dari DJB2.
Beberapa tolok ukur dengan string input besar di sini: http://jsperf.com/32-bit-hash
Ketika string input pendek di -hash, kinerja murmur turun, relatif terhadap DJ2B dan FNV-1a: http://jsperf.com/32- bit-hash / 3
Jadi secara umum saya akan merekomendasikan murmur3.
Lihat di sini untuk implementasi JavaScript: https://github.com/garycourt/murmurhash-js
Jika string input pendek dan kinerja lebih penting daripada kualitas distribusi, gunakan DJB2 (seperti yang diusulkan oleh jawaban yang diterima oleh esmiralha).
Jika kualitas dan ukuran kode kecil lebih penting daripada kecepatan, saya menggunakan implementasi FNV-1a ini (berdasarkan kode ini ).
Meningkatkan Probabilitas Tabrakan
Seperti yang dijelaskan di sini , kita dapat memperluas ukuran bit hash menggunakan trik ini:
Gunakan dengan hati-hati dan jangan berharap terlalu banyak.
sumber
("0000000" + (hval >>> 0).toString(16)).substr(-8);
? Bukankah itu sama dengan(hval >>> 0).toString(16)
?hval
,(hval >>> 0).toString(16)
mungkin kurang dari 8 karakter, jadi Anda membalutnya dengan nol. Saya hanya bingung karena(hval >>> 0).toString(16)
selalu menghasilkan string karakter 8 persis untuk saya.Math.imul
fungsi ES6 . Itu saja membuatnya menjadi tolok ukur teratas, dan akhirnya menjadi pilihan yang lebih baik daripada DJB2 dalam jangka panjang.Berdasarkan jawaban yang diterima di ES6. Lebih kecil, dapat dikelola, dan berfungsi di browser modern.
EDIT (2019-11-04) :
versi fungsi panah satu-liner:
sumber
str += ""
sebelum hashing untuk menghindari pengecualian yangstr.split is not a function
dilemparkan ketika non-string dilewatkan sebagai parameterhash |= 0
untuk mengonversi ke int 32 bit. Implementasi ini tidak. Apakah ini bug?Dengan itu, ada sesuatu yang lebih baik— cyrb53 , hash 53-bit sederhana namun berkualitas tinggi. Ini cukup cepat, menyediakan distribusi hash yang sangat baik, dan memiliki tingkat tabrakan lebih rendah secara signifikan dibandingkan dengan setiap 32-bit hash.
Mirip dengan algoritma MurmurHash / xxHash yang terkenal, ia menggunakan kombinasi multiplikasi dan Xorshift untuk menghasilkan hash, tetapi tidak . Akibatnya lebih cepat daripada dalam JavaScript dan secara signifikan lebih mudah untuk diterapkan.
Ini mencapai longsoran salju (tidak ketat), yang pada dasarnya berarti perubahan kecil pada input memiliki perubahan besar dalam output, membuat hash yang dihasilkan tampak acak:
Anda juga dapat menyediakan seed untuk stream alternatif dari input yang sama:
Secara teknis ini adalah hash 64-bit (dua hash 32-bit yang tidak berkorelasi secara paralel), tetapi JavaScript terbatas pada bilangan bulat 53-bit. Jika diperlukan, output 64-bit penuh masih dapat digunakan dengan mengubah garis balik untuk string hex atau array.
Ketahuilah bahwa membangun string hex dapat secara drastis memperlambat pemrosesan batch dalam situasi yang kritis terhadap kinerja.
Dan hanya untuk bersenang-senang, inilah hash minimal 32-bit dalam 89 karakter dengan kualitas lebih tinggi daripada FNV atau DJB2:
sumber
ch
diinisialisasi?'imul'
.Jika itu membantu siapa pun, saya menggabungkan dua jawaban teratas ke dalam versi yang lebih lama dengan browser-toleran, yang menggunakan versi cepat jika
reduce
tersedia dan kembali ke solusi esmiralha jika tidak.Penggunaannya seperti:
sumber
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; }
Ini adalah varian yang disempurnakan dan berkinerja lebih baik:
Ini sesuai dengan implementasi standar Java
object.hashCode()
Ini juga salah satu yang hanya mengembalikan kode hash positif:
Dan di sini ada pencocokan untuk Java yang hanya mengembalikan kode hash positif:
Nikmati!
sumber
Saya agak terkejut tidak ada yang berbicara tentang API SubtleCrypto baru .
Untuk mendapatkan hash dari string, Anda dapat menggunakan
subtle.digest
metode ini:sumber
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
tidak benar-benar performant.Berkat contoh oleh mar10, saya menemukan cara untuk mendapatkan hasil yang sama dalam C # DAN Javascript untuk FNV-1a. Jika ada unicode chars, bagian atas dibuang untuk kinerja. Tidak tahu mengapa mempertahankannya saat hashing, karena saya hanya mem-path path url untuk saat ini.
Versi C #
Versi JavaScript
sumber
Math.imul
dapat digunakan untuk langkah multiplikasi, yang sangat meningkatkan kinerja . Satu-satunya masalah adalah, itu tidak akan berfungsi di IE11 tanpa shim .Yang cepat dan ringkas yang diadaptasi dari sini :
sumber
Saya membutuhkan fungsi serupa (tetapi berbeda) untuk menghasilkan ID unik-ish berdasarkan nama pengguna dan waktu saat ini. Begitu:
Menghasilkan:
sunting Jun 2015: Untuk kode baru saya menggunakan shortid: https://www.npmjs.com/package/shortid
sumber
Satu liner cepat (sangat panjang) saya berdasarkan
Multiply+Xor
metode FNV :sumber
SubtleCrypto.digest
Apakah Anda yakin tidak bisa melakukannya dengan cara itu ?
Apakah Anda lupa Anda menggunakan Javascript, bahasa yang terus berkembang?
Coba
SubtleCrypto
. Ini mendukung fungsi hash SHA-1, SHA-128, SHA-256, dan SHA-512.sumber
Saya agak terlambat ke pesta, tetapi Anda dapat menggunakan modul ini: crypto :
Hasil dari fungsi ini selalu adalah
64
karakter string; sesuatu seperti ini:"aa54e7563b1964037849528e7ba068eb7767b1fab74a8d80fe300828b996714a"
sumber
Saya telah menggabungkan dua solusi (pengguna esmiralha dan lordvlad) untuk mendapatkan fungsi yang seharusnya lebih cepat untuk browser yang mendukung pengurangan fungsi js () dan masih kompatibel dengan browser lama:
Contoh:
sumber
Jika Anda ingin menghindari tabrakan, Anda mungkin ingin menggunakan hash yang aman seperti SHA-256 . Ada beberapa implementasi JavaScript SHA-256.
Saya menulis tes untuk membandingkan beberapa implementasi hash, lihat https://github.com/brillout/test-javascript-hash-implementations .
Atau buka http://brillout.github.io/test-javascript-hash-implementations/ , untuk menjalankan tes.
sumber
Ini harus sedikit lebih aman daripada beberapa jawaban lain, tetapi dalam suatu fungsi, tanpa sumber yang dimuat sebelumnya
Saya pada dasarnya membuat versi sederhana sha1 yang diperkecil.
Anda mengambil byte dari string dan mengelompokkannya dengan "kata-kata" 4 sampai 32bit
Kemudian kami memperluas setiap 8 kata menjadi 40 kata (untuk dampak yang lebih besar pada hasilnya).
Ini pergi ke fungsi hashing (pengurangan terakhir) di mana kita melakukan beberapa matematika dengan keadaan saat ini dan input. Kami selalu mengeluarkan 4 kata.
Ini hampir versi satu-perintah / satu-baris menggunakan peta, kurangi ... bukan loop, tapi masih cukup cepat
kami juga mengonversi output menjadi hex untuk mendapatkan string, bukan array kata.
Penggunaannya sederhana. untuk expample
"a string".hash()
akan kembali"88a09e8f9cc6f8c71c4497fbb36f84cd"
Tampilkan cuplikan kode
sumber
Aku pergi untuk rangkaian kode char sederhana dikonversi ke string hex. Ini melayani tujuan yang relatif sempit, yaitu hanya membutuhkan representasi hash dari string PENDEK (misalnya judul, tag) untuk dipertukarkan dengan sisi server yang karena alasan yang tidak relevan tidak dapat dengan mudah mengimplementasikan hashCode Java port yang diterima. Jelas tidak ada aplikasi keamanan di sini.
Ini dapat dibuat lebih singkat dan toleran terhadap browser dengan Underscore. Contoh:
Saya kira jika Anda ingin memiliki string yang lebih besar dengan cara yang sama Anda bisa mengurangi kode char dan hexify jumlah yang dihasilkan daripada menggabungkan karakter individu bersama-sama:
Tentu saja lebih banyak risiko tabrakan dengan metode ini, meskipun Anda bisa bermain-main dengan aritmatika dalam pengurangan namun Anda ingin melakukan diversifikasi dan memperpanjang hash.
sumber
Jawaban @ esmiralha versi sedikit disederhanakan.
Saya tidak mengganti String dalam versi ini, karena itu bisa mengakibatkan beberapa perilaku yang tidak diinginkan.
sumber
Menambahkan ini karena belum ada yang melakukannya, dan ini sepertinya banyak diminta dan diimplementasikan dengan hash, tetapi selalu dilakukan dengan sangat buruk ...
Ini membutuhkan input string, dan jumlah maksimum yang Anda inginkan sama dengan hash, dan menghasilkan angka unik berdasarkan input string.
Anda dapat menggunakan ini untuk menghasilkan indeks unik ke dalam array gambar (Jika Anda ingin mengembalikan avatar tertentu untuk pengguna, yang dipilih secara acak, tetapi juga dipilih berdasarkan namanya, maka itu akan selalu diberikan kepada seseorang dengan nama itu. ).
Anda juga dapat menggunakan ini, tentu saja, untuk mengembalikan indeks ke berbagai warna, seperti untuk menghasilkan warna latar belakang avatar unik berdasarkan nama seseorang.
sumber
Saya tidak melihat alasan untuk menggunakan kode kripto yang terlalu rumit ini alih-alih solusi siap pakai, seperti pustaka objek-hash, atau lain-lain yang mengandalkan vendor lebih produktif, menghemat waktu dan mengurangi biaya perawatan.
Gunakan saja https://github.com/puleos/object-hash
sumber
var crypto = require('crypto');
. Saya pikir itu menambahkan kode dependensi ini dari vendor dalam versi yang diperkecil saat membangun.