Постоянно-разовый хеш для строк?
Будет некоторая потеря времени при установке системы и instuct другие разработчики - особенно, если они не знакомы с versioncontrol (или подрывная деятельность в определенном).
, Но преимущества способности откатывать к предыдущей (рабочей) версии и возможности сделать легкую разность зарегистрированных файлы будут более, чем стоить того.
самая большая проблема состоит в том, что вознаграждения - как большинство вещей - поступают после 'тяжелой работы'.:)
Примечание, различным, но более легким решением может быть enabeling 'Теневая копия' в Windows, если это - Ваш сервер OS (хотя я предполагаю, что это не будет). Плюс этого то, что Вы не будете беспокоить своих co-разработчиков изучением подрывной деятельности, но Вы будете в состоянии вернуться к более старой версии при необходимости...
6 ответов
В общем, я считаю, что любой полный хэш строки должен использовать каждый символ строки и, следовательно, должен увеличиваться как O (n) для n символов. Однако я думаю, что для практических хешей строк вы можете использовать приблизительные хеши, которые легко могут быть O (1).
Рассмотрим строковый хэш, в котором всегда используются символы Min (n, 20) для вычисления стандартного хеша. Очевидно, это возрастает как O (1) с размером строки. Будет ли работать надежно? Это зависит от вашего домена ...
Хеш-функция не обязана (и не может) возвращать уникальное значение для каждой строки.
Вы можете использовать первые 10 символов для инициализации генератора случайных чисел, а затем используйте это, чтобы вытащить 100 случайных символов из строки и хешировать это. Это будет постоянное время.
Вы также можете просто вернуть постоянное значение 1. Строго говоря, это все еще хэш-функция, хотя и не очень полезная.
Вы не можете легко достичь общего алгоритма хеширования с постоянным временем для строк, не рискуя серьезными случаями хеш-коллизий.
Чтобы это было постоянное время, вы не сможете получить доступ к каждому символу в строка. В качестве простого примера предположим, что мы берем первые 6 символов. Затем кто-то приходит и пытается хешировать массив URL-адресов. Функция has будет видеть "http: /" для каждой отдельной строки.
Подобные сценарии могут возникать и для других схем выбора символов. Вы можете выбрать символы псевдослучайно на основе значения предыдущего символа, но вы все равно рискуете потерпеть неудачу, если строки по какой-то причине имеют «неправильный» шаблон и многие из них имеют одинаковое значение хеш-функции.
Хотя я не могу представить себе хэш-функцию с фиксированным временем для строк неограниченной длины, на самом деле в этом нет необходимости.
Идея использования хеш-функции заключается в генерации распределения хеш-значения, из-за которых маловероятно, что многие строки могут столкнуться - для рассматриваемого домена. Этот ключ позволит получить прямой доступ к хранилищу данных. В совокупности эти два результата приводят к поиску с постоянным временем - в среднем .
Если когда-либо возникает такое столкновение, алгоритм поиска возвращается к более гибкой подстратегии поиска.
Конечно, это выполнимо, если вы убедитесь, что все ваши строки «интернированы», прежде чем передавать их чему-то, что требует хеширования. Интернирование - это процесс вставки строки в таблицу строк, так что все интернированные строки с одинаковым значением фактически являются одним и тем же объектом. Затем вы можете просто хешировать указатель (фиксированной длины) на интернированную строку вместо хеширования самой строки.
Вы можете надеяться на асимптотически меньшее время хеширования, чем линейное, если вы используете веревки вместо строк и имеете совместное использование, которое позволяет вам пропустить некоторые вычисления. Но очевидно, что хеш-функция не может разделять входные данные, которые она не считала, поэтому я бы не стал слишком серьезно относиться к «все может быть хешировано за постоянное время».
Все возможно в компромиссе между качеством хеш-функции и объем вычислений, который требуется, и хеш-функция для длинных строк в любом случае должна иметь коллизии.
Вы должны определить, будут ли строки, которые могут возникнуть в вашем алгоритме, слишком часто конфликтовать, если хеш-функция только смотрит на префикс.