Грокаем а Иллюстрированное пособие для программистов и любопытствующих

fc^cebooKoow
vesY
		Y&S 1

Как узнать, обрабатывался ли сайт adit.io? Нужно заглянуть в хеш.
<и;-Ыс> -*y*s
У adit.io имеется свой ключ в хеше, а значит, адрес уже обрабатывался. Среднее время обращения к элементам в хеш-таблице составляет 0(1). Та­ким образом, вы узнали о том, что страница adit.io уже проиндексирована за постоянное время. Неплохо!
Вот только этот хеш получится просто огромным. Google индексирует трил­лионы веб-страниц. Если хеш содержит все URL-адреса, индексируемые Google, он займет слишком много места. У Reddit и bit.ly возникает ана­логичная проблема. Сталкиваясь с такими объемами данных, приходится действовать более изобретательно!
Фильтры Блума
Для решения проблемы можно воспользоваться вероятностными струк­турами данных, которые называются фильтрами Блума. Они дают ответ, который может оказаться ложным, но с большой вероятностью является правильным. Вместо того чтобы обращаться к хешу, вы спрашиваете у фильтра Блума, обрабатывался ли этот URL-адрес ранее. Хеш-таблица даст точный ответ. Фильтр Блума дает ответ, правильный с высокой ве­роятностью:

• 
  возможны ложно-положительные срабатывания. Фильтр скажет: «Этот сайт уже обрабатывался», хотя этого не было;
  
• 
  ложно-отрицательные срабатывания исключены. Если фильтр утверж­дает, что сайт не обрабатывался, вы можете быть в этом уверены.
  

Фильтры Блума хороши тем, что занимают очень мало места. Хеш-таблице пришлось бы хранить все URL-адреса, обрабатываемые Google, а фильтру Блума это не нужно. Фильтры Блума очень удобны тогда, когда не нужно хранить точный ответ (как во всех приведенных примерах). Например, bit.ly может сказать: «Мы полагаем, что сайт может оказаться вредоносным, будьте особенно внимательны».
HyperLogLog
Примерно так же действует другой алгоритм, который называется HyperLogLog. Предположим, Google хочет подсчитать количество уникаль­ных поисков, выполненных пользователями. Или Amazon хочет подсчитать количество уникальных предметов, просмотренных пользователями за сегодняшний день. Для получения ответов на эти вопросы потребуется очень много места! Так, в примере с Google придется вести журнал всех уникальных вариантов поиска. Когда пользователь что-то ищет, вы сначала
проверяете, присутствует ли условие в журнале, и если нет, добавляете его. Даже для одного дня этот журнал получится гигантским.
HyperLogLog аппроксимирует количество уникальных элементов в множе­стве. Как и фильтры Блума, он не дает точного ответа, но выдает достаточно близкий результат с использованием малой части памяти, которую обычно занимает такая задача.
Если вы используете большие объемы данных и вас устраивают прибли­женные ответы — воспользуйтесь вероятностными алгоритмами!
Алгоритмы SHA
Помните процедуру хеширования из главы 5? На всякий случай освежу вашу память: имеется ключ, вы хотите поместить связанное с ним значение в массив.
о 1 г з 1 5 6 ? а а ю и u и и б 16 н ia 13 го г\ гг гз is гь г? га гз зо 31 зг
Э
„_А1Л клю­чи НА ^{чи н}*
БУКВУ
КЛЮЧИ ни


клю- клю­чи НА ЧИ НА БУКВУ ^БУШ


I /


г


БУКВУ «В»


..г \1

лемент, в котором размещается значение, определяется хеш-функцией.
О 1 2 3 4 5 6 7 5 3 10 11 U 13 Н 15 16 1? 16 13 20 21 22 23 225 26 2? 26 23 30 31 32
Значение сохраняется в соответствующей позиции массива.
0