Мне нужно преобразовать строки в какую-то форму хэша. Это возможно в JavaScript?
Я не использую серверный язык, поэтому я не могу сделать это таким образом.
javascript
hash
Freesnöw
источник
источник
Ответы:
Источник: http://werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method/
источник
hash << 5 - hash
же самое,hash * 31 + char
но намного быстрее. Это приятно, потому что это так быстро, а 31 - это простое число. Выиграй, выиграй там.(hash * 31) + char
идентичен выводу, сгенерированному кодом на основе сдвига((hash<<5)-hash)+char
, даже для очень длинных строк (я тестировал его со строками, содержащими более миллиона символов), поэтому он не является «непригодным» в терминах точности. Сложность составляет O (n) для версий на основе числа и на основе сдвига, поэтому она не является «непригодной» с точки зрения сложности.n
, что является самым большим,n
для которого я не могу иметь коллизию?var hashCode = function hashCode (str) {etc...}
? А потом использовать какhashCode("mystring")
?РЕДАКТИРОВАТЬ
основываясь на моих тестах jsperf, принятый ответ на самом деле быстрее: http://jsperf.com/hashcodelordvlad
ОРИГИНАЛ
Если кому-то интересно, вот улучшенная (более быстрая) версия, которая выйдет из строя на старых браузерах, в которых отсутствует
reduce
функция массива.версия со стрелкой в одну строку:
источник
В ответ на этот вопрос Какой алгоритм хеширования лучше всего подходит для уникальности и скорости? Ян Бойд опубликовал хороший углубленный анализ . Короче говоря (насколько я понимаю), он приходит к выводу, что Murmur лучше, а затем FNV-1a.
Алгоритм Java String.hashCode (), предложенный Эсмиралхой, кажется вариантом DJB2.
Некоторые тесты с большими входными строками здесь: http://jsperf.com/32-bit-hash
Когда короткие входные строки хэшируются, производительность ропота падает по сравнению с DJ2B и FNV-1a: http://jsperf.com/32- битовой хэш / 3
Так что в целом я бы порекомендовал murmur3.
Смотрите здесь для реализации JavaScript: https://github.com/garycourt/murmurhash-js
Если входные строки короткие и производительность важнее качества распространения, используйте DJB2 (как предложено в принятом ответе esmiralha).
Если качество и небольшой размер кода важнее скорости, я использую эту реализацию FNV-1a (на основе этого кода ).
Улучшить вероятность столкновения
Как объяснено здесь , мы можем расширить размер хеш-бита, используя этот трюк:
Используйте это с осторожностью и не ожидайте слишком многого все же.
источник
("0000000" + (hval >>> 0).toString(16)).substr(-8);
? Разве это не то же самое, что и(hval >>> 0).toString(16)
?hval
,(hval >>> 0).toString(16)
может быть менее 8 символов, поэтому вы дополняете его нулями. Я был просто сбит с толку, потому что(hval >>> 0).toString(16)
всегда приводил к строке из 8 символов.Math.imul
функции ES6 . Это само по себе делает его высшим ориентиром и, в конечном счете, лучшим выбором, чем DJB2 в долгосрочной перспективе.На основании принятого ответа в ES6. Меньше, удобнее в обслуживании и работает в современных браузерах.
РЕДАКТИРОВАТЬ (2019-11-04) :
версия со стрелкой в одну строку:
источник
str += ""
перед хэшированием, чтобы избежать исключения,str.split is not a function
hash |= 0
для преобразования в 32-битное целое число. Эта реализация не делает. Это ошибка?С этим из пути, вот что лучше - cyrb53 , простой, но высококачественный 53-битный хеш. Он довольно быстрый, обеспечивает очень хорошее распределение хешей и имеет значительно более низкую частоту коллизий по сравнению с любыми 32-битными хешами.
Подобно хорошо известным алгоритмам MurmurHash / xxHash, он использует комбинацию умножения и Xorshift для генерации хэша, но не так тщательно. В результате это быстрее, чем в JavaScript, и значительно проще в реализации.
Достигается лавина (не строгая), что в основном означает, что небольшие изменения во входных данных имеют большие изменения в выходных данных, в результате чего результирующий хэш выглядит случайным:
Вы также можете предоставить начальное число для альтернативных потоков с одним и тем же входом:
Технически это 64-битный хэш (два некоррелированных 32-битных хэша параллельно), но JavaScript ограничен 53-битными целыми числами. При необходимости можно использовать полный 64-битный выход , изменив строку возврата для шестнадцатеричной строки или массива.
Имейте в виду, что построение шестнадцатеричных строк может значительно замедлить пакетную обработку в ситуациях, критичных к производительности.
И просто для удовольствия, вот минимальный 32-битный хэш в 89 символов с более высоким качеством, чем даже FNV или DJB2:
источник
ch
инициализируется?'imul'
.Если это кому-нибудь поможет, я объединил два верхних ответа в более старую версию, устойчивую к браузеру, которая использует быструю версию, если
reduce
она доступна, и использует решение esmiralha, если это не так.Использование как:
источник
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; }
Это изысканный и более эффективный вариант:
Это соответствует реализации стандарта Java
object.hashCode()
Вот также тот, который возвращает только положительные хэш-коды:
А вот соответствующий для Java, который возвращает только положительные хеш-коды:
Наслаждайтесь!
источник
Я немного удивлен, что никто не говорил о новом API SubtleCrypto .
Чтобы получить хеш из строки, вы можете использовать
subtle.digest
метод:источник
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
не совсем производительная.Благодаря примеру к 10 марта, я нашел способ получить те же результаты в C # AND Javascript для FNV-1a. Если присутствуют символы Юникода, верхняя часть отбрасывается ради производительности. Не знаю, почему было бы полезно поддерживать их при хешировании, поскольку я пока хэширую только пути URL.
Версия C #
Версия JavaScript
источник
Math.imul
можно использовать для этапа умножения, что значительно повышает производительность . Единственная проблема, это не будет работать в IE11 без прокладки .Быстрый и краткий, который был адаптирован отсюда :
источник
Мне нужна была похожая функция (но другая) для генерации уникального идентификатора на основе имени пользователя и текущего времени. Так:
Производит:
редактировать июнь 2015: для нового кода я использую Shorttid: https://www.npmjs.com/package/shortid
источник
Мой быстрый (очень длинный) лайнер, основанный на
Multiply+Xor
методе FNV :источник
SubtleCrypto.digest
Вы уверены, что не можете сделать это таким образом ?
Вы забыли, что используете Javascript, язык, который постоянно развивается?
Попробуй
SubtleCrypto
. Он поддерживает хэш-функции SHA-1, SHA-128, SHA-256 и SHA-512.источник
Я немного опоздал на вечеринку, но вы можете использовать этот модуль: crypto :
Результатом этой функции всегда является
64
строка символов; что-то вроде этого:"aa54e7563b1964037849528e7ba068eb7767b1fab74a8d80fe300828b996714a"
источник
Я объединил два решения (пользователи esmiralha и lordvlad), чтобы получить функцию, которая должна быть быстрее для браузеров, поддерживающих функцию js lower () и по-прежнему совместимых со старыми браузерами:
Пример:
источник
Если вы хотите избежать коллизий, вы можете использовать безопасный хеш, такой как SHA-256 . Существует несколько реализаций JavaScript SHA-256.
Я написал тесты для сравнения нескольких реализаций хеша, см. Https://github.com/brillout/test-javascript-hash-implementations .
Или перейдите по адресу http://brillout.github.io/test-javascript-hash-implementations/ , чтобы запустить тесты.
источник
Это должно быть немного более безопасным хешем, чем некоторые другие ответы, но в функции, без какого-либо предварительно загруженного источника
Я создал в основном упрощенную версию sha1.
Вы берете байты строки и группируете их по 4–32 битным «словам».
Затем мы расширяем каждые 8 слов до 40 слов (для большего влияния на результат).
Это относится к функции хеширования (последнее уменьшение), где мы выполняем некоторые математические операции с текущим состоянием и входными данными. Мы всегда получаем 4 слова.
Это почти версия для одной команды / одной строки, использующая карту, сокращение ... вместо циклов, но она все еще довольно быстрая
мы также конвертируем вывод в hex, чтобы получить строку вместо массива слов.
Использование простое. для образца
"a string".hash()
вернется"88a09e8f9cc6f8c71c4497fbb36f84cd"
Показать фрагмент кода
источник
Я пошел на простую конкатенацию кодов символов, преобразованных в шестнадцатеричные строки. Это служит для относительно узкой цели, а именно для того, чтобы просто было необходимо обменять хеш-представление строки SHORT (например, заголовки, теги) со стороны сервера, которая по несущественным причинам не может легко реализовать принятый порт Java hashCode. Очевидно, здесь нет приложения для обеспечения безопасности.
Это может быть сделано более кратким и терпимым к браузеру с Underscore. Пример:
Я полагаю, если вы хотите хэшировать более крупные строки аналогичным образом, вы можете просто уменьшить коды символов и шестнадцатеричную результирующую сумму, а не объединять отдельные символы вместе:
Естественно, больше риска столкновения с этим методом, хотя вы могли бы возиться с арифметикой при уменьшении, однако вы хотели диверсифицировать и удлинить хэш.
источник
Немного упрощенная версия ответа @ esmiralha.
Я не переопределяю String в этой версии, так как это может привести к нежелательному поведению.
источник
Добавление этого, потому что никто еще этого не сделал, и, кажется, об этом много говорят и реализуют с помощью хэшей, но это всегда делается очень плохо ...
Он принимает строковый ввод и максимальное число, которое вы хотите, чтобы хеш равнялся, и генерирует уникальное число на основе строкового ввода.
Вы можете использовать это для создания уникального индекса в массиве изображений (если вы хотите вернуть определенный аватар для пользователя, выбранный случайным образом, но также выбранный на основе его имени, поэтому он всегда будет назначен кому-то с таким именем ).
Конечно, вы также можете использовать это для возврата индекса в массив цветов, например, для генерации уникальных фоновых цветов аватара на основе чьего-либо имени.
источник
Я не вижу причин использовать этот слишком сложный криптографический код вместо готовых к использованию решений, таких как библиотека объектных хэшей и т. Д., Полагаясь на поставщика, более продуктивно, экономит время и снижает затраты на обслуживание.
Просто используйте https://github.com/puleos/object-hash
источник
var crypto = require('crypto');
, Я думаю, что он добавляет этот код зависимости от поставщика в минимизированной версии во время сборки.