Самая быстрая хэш функция

Обновлено: 05.07.2024

Функции хэширования могут использоваться для детерминированного псевдослучайного разбрасывания элементов.

Simhash – это хеш-функция, которая для близких значений возвращает близкий хеш.

halfMD5

Интерпретирует все входные параметры как строки и вычисляет хэш MD5 для каждой из них. Затем объединяет хэши, берет первые 8 байт хэша результирующей строки и интерпретирует их как значение типа UInt64 с big-endian порядком байтов.

Функция относительно медленная (5 миллионов коротких строк в секунду на ядро процессора).
По возможности, используйте функцию sipHash64 вместо неё.

Аргументы

Функция принимает переменное число входных параметров. Аргументы могут быть любого поддерживаемого типа данных.

Возвращаемое значение

Значение хэша с типом данных UInt64.

Пример

Вычисляет MD4 от строки и возвращает полученный набор байт в виде FixedString(16).

sipHash64

Генерирует 64-х битное значение SipHash.

Это криптографическая хэш-функция. Она работает по крайней мере в три раза быстрее, чем функция MD5.

Функция интерпретирует все входные параметры как строки и вычисляет хэш MD5 для каждой из них. Затем комбинирует хэши по следующему алгоритму.

После хэширования всех входных параметров функция получает массив хэшей.
Функция принимает первый и второй элементы и вычисляет хэш для массива из них.
Затем функция принимает хэш-значение, вычисленное на предыдущем шаге, и третий элемент исходного хэш-массива, и вычисляет хэш для массива из них.
Предыдущий шаг повторяется для всех остальных элементов исходного хэш-массива.

Аргументы

Возвращаемое значение

Значение хэша с типом данных UInt64.

Пример

sipHash128

Вычисляет SipHash от строки.
Принимает аргумент типа String. Возвращает FixedString(16).
Отличается от sipHash64 тем, что финальный xor-folding состояния делается только до 128 бит.

cityHash64

Генерирует 64-х битное значение CityHash.

Это не криптографическая хэш-функция. Она использует CityHash алгоритм для строковых параметров и зависящую от реализации быструю некриптографическую хэш-функцию для параметров с другими типами данных. Функция использует комбинатор CityHash для получения конечных результатов.

Аргументы

Возвращаемое значение

Значение хэша с типом данных UInt64.

Примеры

А вот так вы можете вычислить чексумму всей таблицы с точностью до порядка строк:

intHash32

Вычисляет 32-битный хэш-код от целого числа любого типа.
Это сравнительно быстрая не криптографическая хэш-функция среднего качества для чисел.

intHash64

Вычисляет 64-битный хэш-код от целого числа любого типа.
Работает быстрее, чем intHash32. Качество среднее.

SHA1, SHA224, SHA256, SHA512

Вычисляет SHA-1, SHA-224, SHA-256, SHA-512 хеш строки и возвращает полученный набор байт в виде FixedString.

Синтаксис

Функция работает достаточно медленно (SHA-1 — примерно 5 миллионов коротких строк в секунду на одном процессорном ядре, SHA-224 и SHA-256 — примерно 2.2 миллионов).
Рекомендуется использовать эти функции лишь в тех случаях, когда вам нужна конкретная хеш-функция и вы не можете её выбрать.
Даже в этих случаях рекомендуется применять функцию офлайн — заранее вычисляя значения при вставке в таблицу, вместо того чтобы применять её при выполнении SELECT .

Параметры

Возвращаемое значение

Хеш SHA в виде шестнадцатеричной некодированной строки FixedString. SHA-1 хеш как FixedString(20), SHA-224 как FixedString(28), SHA-256 — FixedString(32), SHA-512 — FixedString(64).

Пример

Используйте функцию hex для представления результата в виде строки с шестнадцатеричной кодировкой.

URLHash(url[, N])

farmFingerprint64

farmHash64

Создает 64-битное значение FarmHash, независимое от платформы (архитектуры сервера), что важно, если значения сохраняются или используются для разбиения данных на группы.

Эти функции используют методы Fingerprint64 и Hash64 из всех доступных методов.

Аргументы

Возвращаемое значение

Значение хэша с типом данных UInt64.

Пример

javaHash

Вычисляет JavaHash от строки. JavaHash не отличается ни скоростью, ни качеством, поэтому эту функцию следует считать устаревшей. Используйте эту функцию, если вам необходимо получить значение хэша по такому же алгоритму.

Возвращаемое значение

Хэш-значение типа Int32 .

Пример

javaHashUTF16LE

Вычисляет JavaHash от строки, при допущении, что строка представлена в кодировке UTF-16LE .

Синтаксис

Аргументы

Возвращаемое значение

Хэш-значение типа Int32 .

Пример

Верный запрос для строки кодированной в UTF-16LE .

hiveHash

Вычисляет HiveHash от строки.

HiveHash — это результат JavaHash с обнулённым битом знака числа. Функция используется в Apache Hive вплоть до версии 3.0.

Возвращаемое значение

Хэш-значение типа Int32 .

Пример

metroHash64

Генерирует 64-х битное значение MetroHash.

Аргументы

Возвращаемое значение

Значение хэша с типом данных UInt64.

Пример

jumpConsistentHash

Вычисляет JumpConsistentHash от значения типа UInt64.
Имеет два параметра: ключ типа UInt64 и количество бакетов. Возвращает значение типа Int32.
Дополнительные сведения смотрите по ссылке: JumpConsistentHash

murmurHash2_32, murmurHash2_64

Аргументы

Обе функции принимают переменное число входных параметров. Аргументы могут быть любого поддерживаемого типа данных.

Возвращаемое значение

Функция murmurHash2_32 возвращает значение типа UInt32.
Функция murmurHash2_64 возвращает значение типа UInt64.

Пример

gccMurmurHash

Вычисляет 64-битное значение MurmurHash2, используя те же hash seed, что и gcc.

Какой алгоритм хеширования лучше всего подходит для уникальности и скорости? Примеры (хороших) применений включают хеш-словари.

Я знаю, что есть такие вещи, как SHA-256 и тому подобное, но эти алгоритмы предназначены для обеспечения безопасности , что обычно означает, что они медленнее, чем алгоритмы, которые менее уникальны . Я хочу, чтобы алгоритм хеширования был быстрым, но оставался достаточно уникальным, чтобы избежать коллизий.

@ Orbling, для реализации хеш-словаря. Таким образом, столкновения должны быть сведены к минимуму, но это не имеет цели безопасности вообще. Обратите внимание, что вам нужно ожидать, по крайней мере, некоторых коллизий в вашей хэш-таблице, в противном случае таблица должна быть огромной, чтобы можно было обрабатывать даже относительно небольшое количество ключей . @zvrba Зависит от алгоритма. bcrypt разработан, чтобы быть медленным.

Я протестировал несколько разных алгоритмов, измеряя скорость и количество столкновений.

Я использовал три разных набора ключей:

Для каждого корпуса было зафиксировано количество столкновений и среднее время, проведенное за хешированием.

Результаты

Каждый результат содержит среднее время хеширования и количество столкновений.

Примечания :

ужасно

SuperFastHash быстр, с вещами, выглядящими довольно рассеянными; Боже мой, число столкновений. Я надеюсь, что парень, который портировал это, понял что-то не так; это довольно плохо
CRC32 довольно хорош . Медленнее, и таблица поиска 1k

Действительно ли случаются столкновения?

Да. Я начал писать свою тестовую программу, чтобы увидеть, действительно ли случаются коллизии хешей - и это не просто теоретическая конструкция. Они действительно случаются

Столкновения ФНВ-1

Столкновения ФНВ-1а

costarring сталкивается с liquid
declinate сталкивается с macallums
altarage сталкивается с zinke
altarages сталкивается с zinkes

Murmur2 столкновения

cataract сталкивается с periti
roquette сталкивается с skivie
shawl сталкивается с stormbound
dowlases сталкивается с tramontane
cricketings сталкивается с twanger
longans сталкивается с whigs

DJB2 столкновения

hetairas сталкивается с mentioner
heliotropes сталкивается с neurospora
depravement сталкивается с serafins
stylist сталкивается с subgenera
joyful сталкивается с synaphea
redescribed сталкивается с urites
dram сталкивается с vivency

DJB2a столкновения

haggadot сталкивается с loathsomenesses
adorablenesses сталкивается с rentability
playwright сталкивается с snush
playwrighting сталкивается с snushing
treponematoses сталкивается с waterbeds

CRC32 столкновения

codding сталкивается с gnu
exhibiters сталкивается с schlager

SuperFastHash столкновения

dahabiah сталкивается с drapability
encharm сталкивается с enclave
grahams сталкивается с gramary
. отсечь 79 столкновений .
night сталкивается с vigil
nights сталкивается с vigils
finks сталкивается с vinic

Randomnessification

Другая субъективная мера - насколько случайным образом распределены хэши. Отображение полученных HashTables показывает, насколько равномерно распределяются данные. Все хеш-функции показывают хорошее распределение при линейном отображении таблицы:

Кроме случаев , когда хэширования число строк ( "1" , "2" , . "216553" ) (например, почтовые индексы ), где модели начинают появляться в большинстве алгоритмов хэширования:

SDBM :

DJB2a :

FNV-1 :

Все, кроме FNV-1a , которые все еще выглядят довольно случайными для меня:

Фактически, Murmur2, кажется, имеет даже лучшую случайность с Numbers чем FNV-1a :

Когда я смотрю на FNV-1a карту «число», я думаю, что вижу тонкие вертикальные узоры. С Murmur я не вижу никаких закономерностей. Как вы думаете?

Дополнительное значение * в таблице обозначает, насколько плоха случайность. С FNV-1a является лучшим, и DJB2x является худшим:

Первоначально я написал эту программу, чтобы решить, нужно ли мне беспокоиться о столкновениях.

И тогда это превратилось в то, что хэш-функции были достаточно случайными.

Алгоритм FNV-1a

Хэш FNV1 поставляется в вариантах, которые возвращают 32, 64, 128, 256, 512 и 1024-битные хэши.

Где константы FNV_offset_basis и FNV_prime зависят от размера возвращаемого хеша:

Все мои результаты с 32-битным вариантом.

FNV-1 лучше, чем FNV-1a?

FNV-1a лучше вокруг. Было больше столкновений с FNV-1a при использовании английского слова corpus:

Теперь сравните строчные и прописные буквы:

В этом случае FNV-1a не «на 400%» хуже, чем FN-1, только на 20% хуже.

Я думаю, что более важным выводом является то, что существует два класса алгоритмов, когда речь идет о столкновениях:

редкие столкновения : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
Общие коллизии : SuperFastHash, Loselose

И затем, насколько равномерно распределены хэши:

выдающийся дистрибутив: Murmur2, FNV-1a, SuperFastHas
отличное распределение: FNV-1
хорошее распределение: SDBM, DJB2, DJB2a
ужасное распределение: Loselose

Обновить

Ропщите? Конечно почему нет

Обновить

@whatshisname задалась вопросом, как будет работать CRC32 , добавила числа в таблицу.

CRC32 довольно хорош . Мало коллизий, но медленнее, и накладные расходы таблицы поиска 1k.

Отсеки все ошибочные материалы о распространении CRC - мой плохой

До сегодняшнего дня я собирался использовать FNV-1a в качестве своего фактического алгоритма хэширования хеш-таблицы. Но теперь я перехожу на Murmur2:

Быстрее
Лучшая рандомизация всех классов ввода

И я действительно, очень надеюсь, что что-то не так с SuperFastHash алгоритмом, который я нашел ; это слишком плохо, чтобы быть таким же популярным.

(1) - SuperFastHash имеет очень плохие свойства столкновения, которые были задокументированы в другом месте.

Так что, думаю, это не только я.

Обновление: я понял, почему Murmur быстрее, чем другие. MurmurHash2 работает с четырьмя байтами одновременно. Большинство алгоритмов побайтно :

Это означает, что когда ключи становятся длиннее, Murmur получает шанс сиять.

Обновить

GUID разработаны для того, чтобы быть уникальными, а не случайными

Даже алгоритм GUID Версии 4 не гарантированно непредсказуем, поскольку алгоритм не определяет качество генератора случайных чисел. Статья Википедии для GUID содержит первичное исследование, которое предполагает, что будущие и предыдущие GUID могут быть предсказаны на основе знания состояния генератора случайных чисел, поскольку генератор не является криптографически стойким.

Randomess - это не то же самое, что избегать столкновений; вот почему было бы ошибкой пытаться изобрести свой собственный алгоритм «хэширования», взяв некоторое подмножество «случайного» guid:

Примечание : опять же, в кавычки я помещаю «случайный GUID» , потому что это «случайный» вариант GUID. Более точное описание будет Type 4 UUID . Но никто не знает, что типа 4 или 1, 3 и 5. Так что проще назвать их «случайными» GUID.

Было бы действительно интересно посмотреть, как сравнивается SHA, а не потому, что он является хорошим кандидатом для алгоритма хеширования, но было бы очень интересно увидеть, как любой криптографический хэш сравнивается с этим, созданным для алгоритмов скорости. Новый хэш по имени 'xxHash' от Yann Collet недавно делал раунды. Я всегда с подозрением отношусь к новому хешу. Было бы интересно увидеть это в вашем сравнении (если вы не устали от людей, предлагающих добавлять случайные хэши, о которых они слышали . ) Привет Ян, моя реализация SuperFastHash в Delphi верна. При реализации я создал набор тестов в C и Delphi, чтобы сравнить результаты моей реализации и эталонной реализации. Там нет никаких различий. Итак, что вы видите, так это хеш хэш . (Вот почему я также опубликовал реализацию MurmurHash : landman-code.blogspot.nl/2009/02/… ) Знает ли автор, что это не просто потрясающий ответ - это фактический справочный ресурс в мире по этому вопросу? В любое время мне нужно иметь дело с хэшами, это решает мою проблему так быстро и авторитетно, что мне больше ничего не нужно. Это довольно очевидно, но стоит отметить, что для того, чтобы гарантировать отсутствие коллизий, ключи должны быть того же размера, что и значения, если только нет ограничений на значения, на которых алгоритм может извлечь выгоду. @ devios1 Ваше утверждение не имеет смысла. Во-первых, значения в хэш-таблице, совершенные или нет, не зависят от ключей. Во-вторых, идеальная хеш-таблица - это просто линейный массив значений, индексируемый результатом функции, которая была создана таким образом, чтобы все индексы были уникальными. @DavidCary Ничто по вашей ссылке не поддерживает вашу заявку. Возможно, вы перепутали O (1) с «без столкновений», но это совсем не одно и то же. Конечно, идеальное хеширование гарантирует отсутствие коллизий, но для этого необходимо, чтобы все ключи были известны заранее и их было относительно немного. (Но смотрите ссылку на cmph выше.)

Вот список хеш-функций, но короткая версия:

Если вы просто хотите иметь хорошую хеш-функцию и не можете ждать, djb2 это одна из лучших строковых хеш-функций, которую я знаю. Имеет отличное распределение и скорость для множества различных наборов ключей и размеров таблиц.

DJB довольно плох с точки зрения производительности и распространения. Я бы не использовал это сегодня. @ConradMeyer Бьюсь об заклад, DJB может быть ускорен в три раза, как и в этом моем вопросе, и тогда он, вероятно, побьет большинство используемых алгоритмов. По поводу раздачи я согласен. Хеш, создающий коллизии даже для двухбуквенных строк, не может быть действительно хорошим.

CityHash от Google - это алгоритм, который вы ищете. Это не хорошо для криптографии, но хорошо для генерации уникальных хэшей.

Прочитайте блог для получения более подробной информации и код доступен здесь .

CityHash написан на C ++. Там также есть обычный порт C .

Все функции CityHash настроены для 64-битных процессоров. Тем не менее, они будут работать (за исключением новых, которые используют SSE4.2) в 32-битном коде. Они не будут очень быстрыми. Вы можете использовать Murmur или что-то еще в 32-битном коде.

Я составил краткое сравнение скорости различных алгоритмов хэширования при хэшировании файлов.

Отдельные графики лишь незначительно отличаются в методе чтения и могут быть проигнорированы здесь, так как все файлы были сохранены в tmpfs. Поэтому, если вам интересно, тест не был связан с IO.

Алгоритмы включают в себя: SpookyHash, CityHash, Murmur3, MD5, SHA .

Некриптографические хеш-функции, такие как Murmur3, Cityhash и Spooky, довольно близки друг к другу. Следует отметить, что Cityhash может быть быстрее на процессорах с CRC инструкцией SSE 4.2s , которой нет у моего процессора. SpookyHash был в моем случае всегда чуть-чуть до CityHash.
MD5 представляется хорошим компромиссом при использовании криптографических хеш-функций, хотя SHA256 может быть более безопасным для уязвимостей коллизий MD5 и SHA1.
Сложность всех алгоритмов линейна - что на самом деле неудивительно, поскольку они работают блочно. (Я хотел посмотреть, если метод чтения имеет значение, так что вы можете просто сравнить самые правильные значения).
SHA256 был медленнее, чем SHA512.
Я не исследовал случайность хэш-функций. Но вот хорошее сравнение хеш-функций, отсутствующих в ответе Иана Бойдса . Это указывает на то, что у CityHash есть некоторые проблемы в угловых случаях.

Источник, используемый для участков:

Алгоритмы SHA (включая SHA-256) предназначены для быстрой работы .

На самом деле их скорость иногда может быть проблемой. В частности, распространенным методом хранения токена, полученного из пароля, является запуск стандартного алгоритма быстрого хеширования 10 000 раз (сохранение хэша хэша хэша пароля . ).

Конечно, это довольно быстрый алгоритм криптографического хеширования . Но OP просто хочет хранить значения в хеш-таблице, и я не думаю, что криптографическая хеш-функция действительно подходит для этого. Вопрос, поднятый (как ни странно, теперь кажется), был предметом криптографических хеш-функций. Это то, на что я отвечаю. Просто чтобы отвлечь людей от идеи: «В частности, распространенная техника хранения токена, полученного из пароля, - запуск стандартного алгоритма быстрого хеширования 10 000 раз» - хотя это обычное явление, это просто глупо. Для этих сценариев разработаны алгоритмы, например bcrypt . Используйте правильные инструменты. Криптографические хеши разработаны для обеспечения высокой пропускной способности, но это часто означает, что они требуют больших затрат на настройку, демонтаж .rodata и / или состояние. Когда вам нужен алгоритм для хеш-таблицы, у вас обычно есть очень короткие ключи и их много, но вам не нужны дополнительные гарантии криптографического ключа. Я сам использую измененный Дженкинс по отдельности. @ChrisMorgan: вместо использования криптографически безопасного хэша, HashTable DoS может быть решен гораздо более эффективно с помощью рандомизации хэшей, так что каждый запуск программ или даже в каждой хеш-таблице, так что данные не будут сгруппированы в одно и то же ведро каждый раз ,

Я знаю, что есть такие вещи, как SHA-256 и тому подобное, но эти алгоритмы предназначены для обеспечения безопасности , что обычно означает, что они медленнее, чем алгоритмы, которые менее уникальны .

Предположение о том, что криптографические хеш-функции являются более уникальными, неверно, и на самом деле на практике может показаться, что оно часто имеет обратный характер. Поистине:

Криптографические хеш-функции в идеале должны быть неотличимы от случайных ;
Но с некриптографическими хеш-функциями желательно, чтобы они благоприятно взаимодействовали с вероятными входными данными .

Это означает, что некриптографическая хеш-функция может иметь меньше коллизий, чем криптографическая, для «хорошего» набора данных - наборов данных, для которых она была разработана.

На самом деле мы можем продемонстрировать это с помощью данных в ответе Яна Бойда и немного математики: проблема дня рождения . Формула для ожидаемого числа сталкивающихся пар, если вы n случайным образом выбираете целые числа из набора [1, d] : (взято из Википедии):

При n подключении = 216,553 и d = 2 ^ 32 мы получаем около 5,5 ожидаемых коллизий . Тесты Яна в основном показывают результаты в окрестностях, но с одним существенным исключением: большинство функций получили нулевые коллизии в последовательных числовых тестах. Вероятность случайного выбора 216 553 32-битных чисел и получения нулевых коллизий составляет около 0,43%. И это только для одной функции - здесь у нас есть пять различных семейств хэш-функций с нулевыми столкновениями!

Итак, что мы видим здесь, так это то, что проверенные Яном хеши благоприятно взаимодействуют с последовательным набором чисел, т. Е. Они распределяют минимально разные входные данные более широко, чем идеальная криптографическая хеш-функция. (Примечание: это означает, что графическая оценка Яна, что FNV-1a и MurmurHash2 «выглядят случайными» для него в наборе данных номеров, может быть опровергнута из его собственных данных. Нулевые коллизии в наборе данных такого размера для обеих хеш-функций, поразительно неслучайно!)

Это не удивительно, потому что это желательное поведение для многих применений хеш-функций. Например, ключи хеш-таблицы часто очень похожи; В ответе Яна упоминается проблема, с которой MSN когда-то сталкивалась с хеш-таблицами почтового индекса . Это использование, когда предотвращение столкновений на вероятных входах выигрывает у случайного поведения.

Другое поучительное сравнение здесь - это контраст в целях разработки между CRC и криптографическими хеш-функциями:

CRC предназначен для улавливания ошибок, возникающих из-за шумных каналов связи , которые, вероятно, представляют собой небольшое количество битов;
Крипто-хэши предназначены для улавливания модификаций, сделанных злоумышленниками , которым выделены ограниченные вычислительные ресурсы, но произвольно большая хитрость.

Поэтому для CRC опять же хорошо иметь меньше коллизий, чем случайных, при минимально разных входах. С крипто хешами это нет-нет!

Я по существу готовлю фразы, которые нужно поместить в базу данных, они могут быть искажены, поэтому я хочу вместо них сохранить короткий хэш (я буду просто сравнивать, если они существуют или нет, поэтому хэш идеален).

Я предполагаю, что MD5 довольно медленный на 100 000 + запросов, поэтому я хотел знать, что было бы лучшим методом для хэш-фраз, возможно, выкатывание моей собственной хеш-функции или использование hash('md4', '. ' было бы быстрее в конце?

Я знаю, что у MySQL есть MD5(), поэтому это будет дополнять бит скорости в конце запроса, но, возможно, там еще более быстрая хэш-функция в MySQL, о которой я не знаю, будет работать с PHP.

ОТВЕТЫ

Ответ 1

Но вы должны знать, что CRC32 будет иметь больше коллизий, чем MD5 или даже SHA-1 хэшей, просто из-за уменьшенной длины (32 бит по сравнению с 128 бит соответственно 160 бит). Но если вы просто хотите проверить, повреждена ли сохраненная строка, с CRC32 все будет в порядке.

Ответ 2

И код, используемый для его создания, следующий:

Ответ 3

Ранжированный список, в котором каждый цикл использует одно и то же свойство для склеивания, как и все остальные.

Ответ 4

Есть сравнение скорости на сайте xxhash. Скопируйте его здесь:

Итак, кажется, что xxHash на сегодняшний день самый быстрый, в то время как многие другие избили старые хеши, такие как CRC32, MD5 и SHA.

Обратите внимание, что это упорядочение по 32-разрядной компиляции. В 64-битной компиляции порядок производительности, вероятно, очень отличается. Некоторые хэши в значительной степени основаны на 64-битных умножениях и выборках.

Ответ 5

Ответ 6

Поскольку мой компьютер имеет четыре ядра, это означает, что хеширование данных так же быстро, как мой жесткий диск, может обеспечить или получить использование не более 6% доступной вычислительной мощности. Для хеширования требуется особая ситуация, чтобы стать узким местом или даже вызвать заметную стоимость на ПК.

На гораздо меньших архитектурах, где скорость хеширования может стать несколько актуальной, вы можете использовать MD4. MD4 отлично подходит для не криптографических целей (и для криптографических целей вы не должны использовать MD5 в любом случае). Сообщалось, что MD4 даже быстрее, чем CRC32 на платформах на базе ARM.

Ответ 7

Обновление 2019 года: этот ответ является наиболее актуальным. Библиотеки для поддержки ропота в основном доступны для всех языков.

В настоящее время рекомендуется использовать семейство Murmur Hash (см., В частности, варианты murmur2 или murmur3).

Хэши Murmur были разработаны для быстрого хеширования с минимальными коллизиями (намного быстрее, чем CRC, MDx и SHAx). Он идеально подходит для поиска дубликатов и очень подходит для индексов HashTable.

Фактически он используется многими современными базами данных (Redis, ElastisSearch, Cassandra) для вычисления всевозможных хэшей для различных целей. Этот конкретный алгоритм стал основным источником многих улучшений производительности в текущем десятилетии.

Он также используется в реализациях Bloom Filters. Вы должны знать, что если вы ищете "быстрые хэши", вы, вероятно, сталкиваетесь с типичной проблемой, которая решается фильтрами Блума. ;-)

Примечание: шум - это хэш общего назначения, означающий НЕ криптографический. Это не мешает найти исходный "текст", сгенерировавший хеш. НЕ подходит для хэширования паролей.

Ответ 8

Я предлагаю urlencode() или base64_encode() по следующим причинам:

Вам не нужна криптография
Вы хотите скорость
Вы хотите, чтобы идентифицировать уникальные строки при очистке строк "неправильных".

Ответ 9

Adler32 лучше всего работает на моей машине. И md5() оказался быстрее, чем crc32() .

Ответ 10

Ответ 11

Шаг первый: установите libsodium (или убедитесь, что вы используете PHP 7. 2+)

Шаг второй: используйте одно из следующего:

sodium_crypto_generichash() , который является BLAKE2b, хеш-функция более безопасна, чем MD5, но быстрее, чем SHA256. (Ссылка имеет ориентиры и т.д.)
sodium_crypto_shorthash() , то есть SipHash-2-4, который подходит для хеш-таблиц, но не следует полагаться на устойчивость к столкновениям.

_shorthash примерно в 3 раза быстрее _generichash , но вам нужен ключ, и у вас небольшой, но реалистичный риск столкновения. С _generichash вам, вероятно, не нужно беспокоиться о столкновениях, и вам не нужно использовать ключ (но может понадобиться в любом случае).

Ответ 12

CRC32 работает быстрее, но менее безопасен, чем MD5 и SHA1. Между MD5 и SHA1 не так много разницы в скорости.

Ответ 13

Реализация для внутреннего хеша md5 немного быстрее, чем md5(). Таким образом, это может быть вариант или какой-либо другой, пожалуйста, попробуйте:

Сделал доклад. Получилось неожиданно больше мыслей, чем можно донести за отведенные 45 минут. Не буду пересказывать (организаторы выложат слайды и видео). Доклад был в основном посвящен именно написанию быстрого кода вообще, чем конкретно очень быстрым хеш-таблицам, которые были использованы в качестве примера и по которым, к сожалению, пришлось пробегаться уже скомкано в конце. Однако, я открою интригу из своей предыдущей заметки.

Про хеш-таблицы очень хорошо написано в третьем томе "Искусство программирования" Дональда Кнута. Секрет в том, что читая сравнения производительности различных методов надо обращать внимание на сравнения в случае реализации хеш-таблиц на внешней памяти, ибо память это новый диск. Все три самых быстрых реализации из протестированных мной (high-scale-lib, Trove, HPPC) не только работают с примитивным типом long , но и реализуют алгоритм хеш-таблиц с открытой адресацией. Он наиболее компактный по памяти. Однако, обогнать их всех не сложно, отказавшись от отдельного хранения ключа, а храня только массив объектов Order. Таким образом, я радикально снижаю потребление памяти, по сравнению со всеми остальными реализациями. Тем самым открывается путь к максимальной скорости с правильным алгоритмом.

Дальше стоит выбор между линейным исследованием и двойным хешированием (см. Кнута). Так как память работает блоками, то линейное исследование, когда исследуются соседние ячейки при коллизии, должно работать быстрей в случае коллизий. Его я и реализовал в первую очередь, благо оно проще в реализации. Однако ему нужна хорошо размазывающая по памяти хэш-функция, которую я реализовал через умножение: умножаю идентификатор на магическое число и беру нужное число старших битов (а размер таблицы будет всегда степенью двойки). Получаю очень простую реализацию класса FastCache с вот таким методом чтения элемента:

Результаты сравнения производительности (а заодно и объем занимаемой памяти, как бонус), указаны в таблице ниже:

Неубедительный отрыв по скорости, несмотря на значительное преимущество по потребляемой памяти. Почему так и что с этим делать — я рассказал на конференции. Читателями моего блога я подробней расскажу об этом отдельно.

UPDATE: Более подробно про тонкости со скоростью работы я написал в следующей заметке.

Читайте также: