Хеширование строки за время O(log длина)

[arseniiv]

Кажется, такой вопрос ещё не задавался. Нужда в хешировании за время $o(n)$, где $n$ — длина строки, может быть, например, при интернализации строк. Некоторые языки используют её по умолчанию (Lua), так что, видимо, должны использовать и какие-то более-менее хорошие хеши таких строк, которым гигантскими никто быть не запретит (прочитали какой-нибудь корпус для анализа).

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

[slavav]

Если говорить об универсальном хеше, то для любой детерминированной хеш функции со сложностью $o(n)$ можно предъявить большое число строк с одинаковым хешем. Само по себе это не беда. Беда в том что множество этих строк имеет простую структуру. Следовательно, может падать производительность при работе с хеш таблицами.

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

[arseniiv]

Надеялся на универсальный, так как пока спрашивал просто из интереса. Спасибо.

slavav в сообщении #1142250 писал(а):

Беда в том что множество этих строк имеет простую структуру.

А для (универсальной) функции со сложностью $O(n)$ возможно, чтобы это множество было не таким простым?

[slavav]

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

[covax]

А какой-нибудь CRC не сгодится?

[arseniiv]

$O(n)$ же.

[worm2]

Если строки такие огромные, то, наверное, они все разные по длине? Если одинаковые — это ж патология какая-то. Вот длину и взять в качестве хеша Ну, а если вдруг короткие попались, то их целиком шерстить.

[Dmitriy40]

Действительно, если строки все разные по длине, то длину и взять.
Если возможны и одинаковые по длине строки, то добавить в хеш несколько символов из строки, позиции которых брать псевдослучайно (но строго детерминированно и всегда одинаково!). Для обычных сильно не совпадающих строк работать будет быстро (фактически $O(1)$), для хорошо совпадающих - зависит от выбора позиций и тут уж без априорной статистики о самих строках не обойтись (например предъявив все $k^n$ возможных перестановок строк длины $n$ из алфавитап в $k$ символов мы собъём любой возможный хеш).
Взяв не фиксированное количество символов в хеш, а например $\log n$ символов (в позициях с простыми индексами или даже с индексами $2^i, i \le n$) получим время $O(\log n)$. Тут для усложнения можно выбирать разные функции индексов в зависимости от значения $n$, на $O()$ это уже не повлияет.
Саму функцию вычисления хеша взять какую-нибудь хорошо исследованную, с известными параметрами и свойствами.

[slavav]

worm2 в сообщении #1143315 писал(а):

Если строки такие огромные, то, наверное, они все разные по длине? Если одинаковые — это ж патология какая-то. Вот длину и взять в качестве хеша Ну, а если вдруг короткие попались, то их целиком шерстить.

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

-- 11.08.2016, 17:23 --

Dmitriy40 в сообщении #1143374 писал(а):

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

А потом применить к задаче дедупликации данных, на которой ваша функция будет работать очень и очень плохо.

[bondkim137]

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

Неплохо, но на бэкапах может здорово сливать. Там вообще не пробежавшись по массиву все сливать будет.