Вероятностное хеширование - есть ли такая вещь?

Question

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

Существует ли такая вещь, как "вероятностное хеширование" или "хеширование с потерями", чтобы увидеть, есть ли IP, вероятно, в наборе, но вас не волнует, есть ли определенный уровень ошибок, когда вы хотите сэкономить ресурсы?

Answer 1

Вы могли бы (ab?) Использовать фильтр Блума для чего-то подобного.

Answer 2

Предполагая адреса IPv4, пространство поиска составляет 2 ³² . Вам нужно не более 1 бита на IP-адрес (0 == нет посещения, 1 == посещение). Без учета накладных расходов на хранение потребуется 512 МБ (2 ²⁹ ) для хранения. Таким образом, упрощенная реализация будет выделять массив размером 512 МБ (или таблицу с 2 ²⁹ строками, каждая из которых хранит байт, или 2 ²⁷ строками, каждая из которых хранит 32-разрядное целое число, или 2 ²⁶ строк, каждая из которых хранит 64-разрядное целое число, или ...)

Вы можете оптимизировать это для разреженного населения, превратив его в дерево.

Определить размер "страницы" в 2 ^x бит. Вы будете выделять хранилище для одной страницы за раз.

Разделите область поиска (2 ³² ) на размер страницы. Это общее количество страниц, необходимое для представления каждого возможного адреса в вашем пространстве поиска.

Затем, чтобы определить, есть ли совпадение в вашем хэше, вы сначала определите, присутствует ли страница, и если да, установлен ли соответствующий бит на странице. Чтобы кэшировать адрес, вы сначала определите, присутствует ли страница; если нет, вы создадите его. Далее вы установите соответствующий бит.

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

Например, для 1024-битного размера страницы (получая максимум 2 ^{22 * ​​1030 * страниц) вы можете структурировать таблицу следующим образом:}

CREATE TABLE VisitedIPs(
    PageIndex int         NOT NULL PRIMARY KEY,
    PageData  binary(128) NOT NULL
)

Чтобы проверить, посещал ли IP-адрес, вы должны использовать код, подобный (псевдокод):

uint ip = address.To32Bit();

string sql =
    "SELECT PageData " +
    "FROM VisitedIPs " +
    "WHERE PageIndex = " + (ip >> 10);

byte[] page = (byte[])GetFromDB(sql);

byte b = page[(ip & 0x3FF) >> 3];

bool hasVisited = (b & (1 << (ip & 7)) != 0;

Настройка посещения IP-адреса аналогична:

uint ip = address.To32Bit();

string sql =
    "SELECT PageData " +
    "FROM VisitedIPs " +
    "WHERE PageIndex = " + (ip >> 10);

byte[] page = (byte[])GetFromDB(sql);

page[(ip & 0x3FF) >> 3] |= (1 << (ip & 7));

sql =
    "UPDATE VisitedIPs " +
    "SET PageData = @pageData " +
    "WHERE PageIndex = " + (ip >> 10);

ExecSQL(sql, new SqlParam("@pageData", page));

Answer 3

Все хеширование происходит с потерями в соответствии с принципом голубиного отверстия . Неизбежно, вы пытаетесь втиснуть N вещей в M слотов (где N >> M). Все, что вам нужно сделать, это просто не обрабатывать случаи коллизий и выбирать достаточно большую хеш-таблицу.

Answer 4

Конечно! Решите, сколько «корзин» вы можете себе позволить (по одному биту), скажем, N; хешировать IP-адрес в строку битов B; принять B по модулю N. Вы можете вычислить вероятность случайных коллизий (с некоторым приближением, например, предположить, что все хешированные IP-адреса образуют одинаково вероятные цепочки битов B) и определить N соответственно, если у вас есть ограничение на максимальную вероятность случайных коллизий, которая является приемлемой для вашего применение.

Answer 5

Запустить усечение битов.

Вероятность коллизии хешей становится 50%, когда у вас есть 2 ^ (n / 2) вещей из возможных 2 ^ n. IP-адрес 2 ^ 32, поэтому вероятность столкновения составляет 50%, когда в контейнере находится 2 ^ 16 элементов.

Уменьшайтесь, когда чувствуете себя комфортно.

Answer 6

Целочисленное (ipv4) или строковое (ipv6) хэширование без обработки коллизий с использованием хеш-значения (размер хеш-таблицы по модулю) в качестве индекса для растрового массива.