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

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

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

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

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

"Возмущенный" хэш-пример, где значение хеша изменяется кардинально маленьким целочисленным значением n

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

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

Спасибо!

Ответ 1

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

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

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

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

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

Ответ 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;
}

Ответ 3

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

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

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

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

Ответ 4

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