быстрое, некриптографическое хеширование строк в Python большой ширины

Question

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

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

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

1. Имеет выходной диапазон, расширяющийсядлина не менее 34 бит, вероятно 64 бит, при этом сохраняются согласованные лавинные свойства более всех бит.(Конкатенация 32-битных хэшей имеет тенденцию нарушать свойства лавины, по крайней мере, с моими тупыми примерами.)
2. Portable.Учитывая одну и ту же строку ввода на двух разных машинах, я должен получить один и тот же результат оба раза.Эти значения будут сохранены в файле для последующего повторного использования.
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 бита).

Спасибо!

Answer 1

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

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

Обновление Я сделал быструю оболочку Python для хэш-функции Murmur3. Проект Github находится здесь , и вы можете найти его также в Указатель пакетов Python * ; ему просто нужен компилятор 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

Answer 2

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

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

Это хеширующая функция Python из 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;
}

Answer 3

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

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

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

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

Answer 4

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