概率哈希 - 有这样的事吗？

Question

假设您要实现一个点击跟踪器,您只需要从任意IP地址计算一次点击链接,但链接和客户端的数量非常大,您不希望保留每个IP的表格 - 单击.假设您可能需要将此作为针对每次点击运行的内容的一部分,并且不希望针对每次点击对大表进行查找.

是否存在"概率哈希"或"有损哈希"这样的事情,看看IP是否可能在一个集合中但你不关心是否存在某种错误率,因为你想节省资源？

Answer 1

您可能(ab？)使用布隆过滤器来做这样的事情.

Answer 2

假设IPv4地址,则搜索空间为2 ³².每个IP地址不需要超过1位(0 ==无访问,1 ==访问).不考虑存储开销,这将需要512 MB(2 ²⁹)来存储.因此,一个简单的实现将分配一个512 MB的数组(或一个包含2 ²⁹行的表,每个存储一个字节,或2 ²⁷行,每行存储一个32位整数,或2 ²⁶行,每个存储一个64位整数,要么...)

您可以通过将稀疏种群变为树来优化稀疏种群.

定义2 ^x位的"页面"大小.您将一次为一个页面分配存储空间.

按页面大小划分搜索空间(2 ³²).这是表示搜索空间中每个可能地址所需的总页数.

然后,要确定散列中是否存在匹配,您将首先确定该页面是否存在,如果存在,则是否设置了页面中的相应位.要缓存地址,首先要确定页面是否存在; 如果没有,你会创建它.接下来,您将设置适当的位.

这很容易模拟到数据库表.您只需要两列:页面索引和二进制数组.分配页面时,只需在表中存储一行,其中包含正确的页面索引和一个空的二进制数组.

例如,对于1024位页面大小(最多产生2 ^22个页面),您可以像这样构建表:

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）。您需要做的只是不处理冲突情况并选择一个足够大的哈希表。