#c_sharp #алгоритм #хеширование
Есть база с огромным количеством строк. Все строки уникальны. Содержат в себе английские,
русские буквы и цифры, могут содержать спецсимволы. В строке от 1 до N слов.
Вопрос: как можно для каждого сделать уникальный хеш?
Использование long возможно, но необходимо вписаться в рамки int.
Описываться алгоритм будет на c#, по идее для ускорения можно использовать asm, но
над этим думаем.
Ответы
Ответ 1
Допустим, у нас есть случайная хеш-функция, M возможных ее значений и N элементов. Тогда вероятность, что хеши элементов будут разными, равна 1 × (1 - 1/M) × (1 - 2/M) × ... × (1 - (N-1)/M) = M! / ((M-N)! × MN). При M = 232 и N = 8 000 000 она будет равна 1,75 × 10-3238. Для сравнения - вероятность падения метеорита завтра вам на голову больше, чем вероятность отсутствия коллизий в таких условиях. Это величина более чем достаточно маленькая чтобы признать перебор хеш-функций в поисках подходящей невозможным. Если строки неизвестны вам заранее - на этом можно закончить. Любая функция, которую бы вы не выбрали, почти наверняка даст коллизии на неизвестном заранее наборе строк. А вот если строки заранее известны - то алгоритм идеального хеширования для них построить можно. Делается это так: Выбираем число бит для "старшей" части хеша. Число бит h даст H=2h разных значений. Берем любую хеш-функцию, и делим в соответствии с ней исходные строки по H корзинам. В среднем получим N1 = N/H строк в корзине. Для каждой корзины подбираем (автоматически, разумеется) отдельную идеальную хеш-функцию для младших бит хеша. Это будет M1 = M/H разных значений. Чтобы шаг 3 длился адекватное время, величина M12 должна быть сравнима с N1. Получаем - M2 / H2 ∽ N / H - то есть надо брать H порядка M2 / N. Получаем H = 16 384 (h = 14), M1 = 288, N1 = 262 144. Итого, алгоритм получения хеш-фукции будет такой: Считаем хеш-функцию 1 по модулю 16 384, запоминаем в переменной h1. Идем в таблицу, посчитанную заранее, по индексу h1. Получаем параметры для хеш-функции 2. Считаем хеш-функцию 2 по модулю 262 144, запоминаем в переменной h2. Считаем (h1 << 18) + h2 - это и есть уникальный хеш. В качестве хеш-функции 2 надо выбрать что-нибудь параметрическое, чтобы было где выбирать случайные параметры. То есть тут неплохо подойдет полиноминальный хеш. В качестве хеш-функции 1 можно выбрать любую хорошую хеш-функцию. Алгоритм получается довольно быстрым (asm не нужен) - но потребует константной таблицы килобайт на 32 или 64.Ответ 2
Обратите внимание на комментарий @Harry!!! Гарантированную уникальность можно обеспечить только лишь словарем Любые хэш-функции - обеспечивают лишь высокую вероятность уникальности Многие спецы непроизвольно путают предметную область использования вероятностных величин. Если мы работаем с вероятностной величиной, то мы должны, несмотря на величину вероятности, обрабатывать два исхода "сработало" vs "не сработало". В противном случае мы должны указать, что создаваемая подсистема на дает 100% гарантии отказа. Простой пример правильного использования вероятностных величин - алгоритмы сжатия по предсказанию. Нашли часто повторяющиеся последовательности - хорошо, не нашли - все равно обработали. Поэтому не нужно "покупаться" на величину, даже столь внушительную, вероятности. Далее шуточный пример ... "Упал на голову кирпич" Небольшое размышление по поводу вероятностей на простом, можно сказать обыденном событии, которое увы, изредка происходит. А история такова. Шел мужик по делам возле строийки. На голову упал кирпич. Нет мужика. Какова была вероятность прожить мужику еще немножко? Постулаты: площадь поверхности нашей планеты 510 072 000 км² 1км² = 1000000м² полщадь суши к площади воды относится примерно 3 к 7 для постройки жилого 12-этажного кирпичного дома требуется 1854288 кирпичей (считал относительно расчетного для одноэтажного, взял 6 квартир на этаже и 12 этажей, плюс внес поправку на 2/3, типа экономия) в году 365*24*60*60 = 31536000 секунд с сутках 24*60*60 = 86400 секунд у обычного человека будет не более 500 жизненных ситуаций, которые побудят его на то или иное действие человек пойдет пешком, если путь его составит не более 2км, иначе воспользуется транспортом человек старше 10 лет пойдет самостоятельно, пусть продолжительность жизни 70 лет, тогда 60 лет = 1892160000 секунд Мужик идет в нужном месте, в нужное время, по нужному делу, срывается нужный кирпич, и в нужный момент совершенно ненужно попадает в голову. Итак, все события совершаются независимо: Теорема умножения вероятностей для независимых событий P(AB) = P(A)*P(B) - вероятность одновременного наступления двух независимых событий равна произведению вероятностей этих событий. Далее расчет на замечательном Ruby: v1 = 510072000000000*3/7 # площадь суши в кв.метрах v2 = 1854288 # количество кирпичей для постройки 12-этажного дома v3 = 31536000 # количество секунд в году v4 = 86400 # количество секунд в сутках v5 = 500 # жизненных ситуаций v6 = 2000 # путь в метрах v7 = 1892160000 # "самостоятельная жизнь в секундах" puts "Сколько было вариантов у мужика выжить: #{v1*v2*v3*v4*v5*v6*v7-1}" Ответ: Сколько вариантов было у мужика выжить: 2089825832201191353090774690693119999999999999999 Ну или примерная вероятность такого вот попадания была: 10⁻⁴⁹ Правда практически нереально? PS. Безусловно все расчеты крайне-крайне приблизителны, цель была осознать порядок малости вероятностной величины.
Комментариев нет:
Отправить комментарий