Я нашел несколько десятков объяснений основной идеи алгоритмов LogLog, но у них не хватает подробностей о как работает разделение результатов хеш-функции? Я имею в виду, что использование одной хэш-функции не является точной при использовании многих функция слишком дорога. Как они преодолевают проблему с помощью одиночной хэш-функции?
Этот ответ является лучшим объяснением, которое я нашел, но до сих пор не имеет смысла для меня:
Они использовали один хэш, но разделили его на две части. Один из них называется ведро (общее количество ведер составляет 2 ^ х), а другое - это в основном так же, как и наш хеш. Мне было трудно получить то, что происходило, поэтому я приведут пример. Предположим, у вас есть два элемента и ваш хэш функция, которая дает значения от 0 до 2 ^ 10, дает 2 значения: 344 и 387. Вы решили иметь 16 ведер. Итак, у вас есть:
0101 011000 bucket 5 will store 1 0110 000011 bucket 6 will store 4
Не могли бы вы объяснить пример выше PLS? У вас должно быть 16 ведер, потому что у вас заголовок длиной 4, верно? Итак, как вы можете иметь 16 ведер с двумя хэшами? Мы оцениваем только ведра, не так ли? Итак, первое ведро имеет размер 1, а второе - размер 4, верно? Как объединить результаты?
