Хэш постоянного времени для строк?

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) затмевается theta(log(n)) для индексов, содержащих много строк, мы не можем игнорировать его, если находимся в такой области, в которой тексты, которые мы ищем, будут очень большими.

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

Спасибо.

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

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

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

Если такое столкновение когда-либо произойдет, алгоритм поиска прибегнет к более гибкой подстратегии поиска.

Answer 6

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

Answer 7

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

Рассмотрим проблему хеширования бесконечного числа ключей (например, набора всех строк любой длины) с набором чисел в {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/