Быстрое, некриптографическое хеширование строк в python

У меня есть потребность в высокопроизводительной функции хеширования строк в Python, которая производит целые числа, по крайней мере, с 34 битами вывода (64 бита имеет смысл, но 32- это слишком мало). Есть несколько других вопросов, таких как этот, о переполнении стека, но из тех, которые я получил, каждый найденный / одобренный ответ попал в одну из нескольких категорий, которые неприменимы (по указанной причине).

  • Используйте встроенный hash() функция. Эта функция, по крайней мере, на машине, для которой я разрабатываю (с Python 2.7 и 64-битным процессором), выдает целое число, которое умещается в пределах 32 бит - недостаточно для моих целей.
  • Используйте hashlib. hashlib предоставляет криптографические процедуры хеширования, которые намного медленнее, чем они должны быть для не криптографических целей. Я нахожу это само собой разумеющимся, но если вам нужны критерии и цитаты, чтобы убедить вас в этом факте, то я могу это предоставить.
  • Использовать string.__hash__() функционировать как прототип, чтобы написать свою собственную функцию. Я подозреваю, что это будет правильный путь, за исключением того, что эффективность этой конкретной функции заключается в использовании функции c_mul, которая оборачивается около 32 бит - опять же, слишком мало для моего использования! Очень расстраивает, это так близко к идеалу!

Идеальное решение будет иметь следующие свойства в относительном, свободном порядке важности.

  1. Имеют выходной диапазон, расширяющий по крайней мере 34 бита, вероятно 64 бита, сохраняя при этом согласованные лавинные свойства для всех битов. (Конкатенация 32-битных хэшей имеет тенденцию нарушать свойства лавины, по крайней мере, с моими тупыми примерами.)
  2. Портативный. Учитывая одну и ту же строку ввода на двух разных машинах, я должен получить один и тот же результат оба раза. Эти значения будут сохранены в файле для последующего повторного использования.
  3. Высокая производительность. Чем быстрее, тем лучше, так как эта функция будет вызываться примерно 20 миллиардов раз во время выполнения программы, которую я запускаю (в данный момент это критичный для производительности код). Ее не нужно писать на C, на самом деле просто нужно превзойти md5 (где-то в области встроенного хеша () для строк).
  4. Примите целое число "возмущение" (какое слово лучше использовать здесь) в качестве входных данных для изменения выходных данных. Я привел пример ниже (правила форматирования списка не позволили бы мне разместить его ближе.) Я полагаю, что это не на 100% необходимо, поскольку его можно смоделировать, возмущая вывод функции вручную, но наличие его в качестве входных данных дает мне приятное теплое чувство.
  5. Написано полностью на Python. Если это абсолютно положительно должно быть написано на C, тогда я думаю, что это можно сделать, но я бы взял на 20% более медленную функцию, написанную на python, по сравнению с более быстрой в C, просто из-за головной боли при координации проекта при использовании двух разных языков., Да, это отговорка, но это список пожеланий здесь.

Пример возмущенного хэша, где значение хеша радикально изменяется маленьким целочисленным значением n

def perturb_hash(key,n):
    return hash((key,n))

Наконец, если вам интересно, что, черт возьми, я делаю, что мне нужна такая специфическая хеш-функция, я делаю полную переписывание модуля pybloom, чтобы значительно повысить его производительность. Мне это удалось (теперь он работает примерно в 4 раза быстрее и занимает около 50% пространства), но я заметил, что иногда, если фильтр становится достаточно большим, он внезапно дает ложноположительные результаты. Я понял, что это потому, что хэш-функция не адресовала достаточно битов. 32 бита могут адресовать только 4 миллиарда бит (учтите, что фильтр адресует биты, а не байты), а некоторые из фильтров, которые я использую для геномных данных, удваивают это или более (следовательно, минимум 34 бита).

Спасибо!

Источник

6 ответов

Решение

Взгляните на 128-битный вариант MurmurHash3. Страница алгоритма содержит некоторые показатели производительности. Должно быть возможно перенести это на Python, чистый или как расширение C. (Обновлен автор рекомендует использовать 128-битный вариант и выбрасывать ненужные вам биты).

Если MurmurHash2 работает для вас 64- битно, в пакете pyfasthash есть реализация Python (расширение C), которая включает в себя несколько других не криптографических хэш-вариантов, хотя некоторые из них предлагают только 32-битный вывод.

Обновление Я сделал быструю оболочку Python для хэш-функции Murmur3. Проект Github уже здесь, и вы также можете найти его в Python Package Index; ему просто нужен компилятор C++ для сборки; Повышение не требуется.

Пример использования и сравнение сроков:

import murmur3
import timeit

# without seed
print murmur3.murmur3_x86_64('samplebias')
# with seed value
print murmur3.murmur3_x86_64('samplebias', 123)

# timing comparison with str __hash__
t = timeit.Timer("murmur3.murmur3_x86_64('hello')", "import murmur3")
print 'murmur3:', t.timeit()

t = timeit.Timer("str.__hash__('hello')")
print 'str.__hash__:', t.timeit()

Выход:

15662901497824584782
7997834649920664675
murmur3: 0.264422178268
str.__hash__: 0.219163894653
Источник

БУДЬТЕ ОСТОРОЖНЫ СО ВСТРОЕННОЙ ФУНКЦИЕЙ ХЭША!

Начиная с Python3, ему каждый раз при запуске интерпретатора загружается другое семя (я не знаю более подробной информации), поэтому он каждый раз генерирует разные значения - но не с собственными числовыми типами.

$ python3 -c 'print(hash("Hello!"), hash(3.14))'
-1756730906053498061 322818021289917443
$ python3 -c 'print(hash("Hello!"), hash(3.14))'
-4556027264747844925 322818021289917443
$ python3 -c 'print(hash("Hello!"), hash(3.14))'
-4403217265550417031 322818021289917443
Источник

Взгляните на xxHash, там также есть пакет pip .

xxHash - это чрезвычайно быстрый алгоритм хеширования, работающий с ограничениями по скорости ОЗУ. Он успешно завершает набор тестов SMHasher, который оценивает коллизию, дисперсию и случайность хэш-функций. Код легко переносится, а хэши идентичны на всех платформах (прямой / большой порядок байтов).

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

Источник

Используйте встроенную функцию hash(). Эта функция, по крайней мере, на машине, для которой я разрабатываю (с Python 2.7 и 64-битным процессором), выдает целое число, которое умещается в пределах 32 бит - недостаточно для моих целей.

Это не правда. Встроенная хеш-функция генерирует 64-битный хеш в 64-битной системе.

Это хеш-функция Python str из Objects/stringobject.c (Python версия 2.7):

static long
string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;      /* Notice the 64-bit hash, at least on a 64-bit system */

    if (a->ob_shash != -1)
    return a->ob_shash;
    len = Py_SIZE(a);
    p = (unsigned char *) a->ob_sval;
    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;
    x ^= Py_SIZE(a);
    if (x == -1)
        x = -2;
    a->ob_shash = x;
    return x;
}
Источник

"strings": я предполагаю, что вы хотите хэшировать Python 2.x str объекты и / или Python3.x bytes и / или bytearray объекты.

Это может нарушить ваше первое ограничение, но: подумайте об использовании чего-то вроде

(zlib.adler32(strg, perturber) << N) ^ hash(strg)

чтобы получить (32+N)-битовый хеш.

Источник

Если вы можете использовать Python 3.2, результат хеширования в 64-битной Windows теперь будет 64-битным значением.

Источник
Другие вопросы по тегам