Постоянный хэш для строк?

Question

Другой вопрос о SO поднял возможности на некоторых языках для хеширования строк, чтобы они могли быстро искать их в таблице. Два примера этого - словарь <> в .NET и структура хранения {} в Python. Другие языки, безусловно, поддерживают такой механизм. У C ++ есть своя карта, у LISP есть эквивалент, как и у большинства других современных языков.

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

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

Я вижу некоторые другие страницы, такие как эта (http://www.cse.yorku.ca/~oz/hash.html)), которые отображают некоторые алгоритмы хеширования, но кажется, что каждая из них выполняет итерацию по всей длине строки, чтобы получить свое значение.

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

Даже при такой древовидной структуре, если мы хотим остаться в порядке тета (log (n)), а n - это число элементов в дереве, нам нужен алгоритм хеширования с постоянным временем. В противном случае у нас есть аддитивное наказание итерации по строке. Даже если theta (m) затмевается тэтой (log (n)) для индексов, содержащих много строк, мы не можем игнорировать это, если мы находимся в такой области, что тексты, по которым мы ищем, будут очень большими.

Мне известно, что суффиксные деревья / массивы и Aho-Corasick могут сократить поиск до тета (m) для увеличения затрат в памяти, но я специально спрашиваю, существует ли метод хеширования с постоянным временем для строк произвольных длины, заявленные другим членом SO.

Спасибо.

Answer 1

Хеш-функция не должна (и не может) возвращать уникальное значение для каждой строки.

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

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

Answer 2

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

Рассмотрим строковый хеш, который всегда использует Min (n, 20) символов для вычисления стандартного хеша. Очевидно, это растет как O (1) с размером строки. Будет ли это работать надежно? Это зависит от вашего домена ...

Answer 3

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

Чтобы оно было постоянным, вы не сможете получить доступ ко всем символам в строке. В качестве простого примера, предположим, что мы берем первые 6 символов. Затем приходит кто-то и пытается хэшировать массив URL-адресов. Функция has будет видеть «http: /» для каждой отдельной строки.

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

Answer 4

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

Рассмотрим проблему хэширования бесконечного числа ключей - например, набора всех строк любой длины - с набором чисел в {1,2,…, b}. Случайное хеширование происходит сначала путем случайного выбора хеш-функции h в семействе H-функций.

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

Выберите любую хеш-функцию h: существует по крайней мере одно хеш-значение y такое, что множество A = {s: h (s) = y} бесконечно, то есть у вас бесконечно много сталкивающихся строк. Выберите любую другую хеш-функцию h 'и хешируйте ключи в наборе A. Существует по крайней мере одно хеш-значение y' такое, что множество A '= {s находится в A: h' (s) = y '} бесконечно то есть существует бесконечно много строк, сталкивающихся на двух хеш-функциях. Вы можете повторить этот аргумент любое количество раз. Повторите это H раз. Тогда у вас есть бесконечный набор строк, где все строки сталкиваются во всех ваших H-хэш-функциях. CQFD.

Дополнительная литература : Разумное хеширование строк переменной длины невозможно http://lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/

Answer 5

Конечно, это выполнимо, если вы убедитесь, что все ваши строки «интернированы», прежде чем передать их чему-либо, требующему хеширования. Стажировка - это процесс вставки строки в таблицу строк, так что все интернированные строки с одинаковым значением фактически являются одним и тем же объектом. Затем вы можете просто хешировать (фиксированной длины) указатель на интернированную строку вместо хеширования самой строки.

Answer 6

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

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

Если такое столкновение происходит, алгоритм поиска использует более гибкую подстратегию поиска.

Answer 7

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

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

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