概率散列-有这样的事情吗?

你可能(ab?)使用A bloom filter 像这样的事情。

假设IPv4地址,搜索空间为2 ^三十二 . 每个IP地址不需要超过1位(0=无访问,1=访问)。不考虑存储开销,这需要512 MB(2 ^二十九 )储存。因此,一个简单的实现将分配一个512MB数组(或一个表中有2个 ^二十九 行,每行存储一个字节,或2 ^二十七 行,每个行存储一个32位整数,或2 ^二十六 行,每个行存储一个64位整数,或…)

您可以通过将其转换为树来优化稀疏人口的这一点。

定义“页面”大小为2 ^X 位。您将一次为一个页面分配存储空间。

划分搜索空间(2 ^三十二 )按页面大小。这是表示搜索空间中每个可能地址所需的总页数。

然后,要确定哈希中是否有命中,首先要确定页面是否存在,如果存在,还要确定页面中是否设置了适当的位。要缓存地址,首先要确定页面是否存在;如果不存在,则要创建它。接下来,您将设置适当的位。

这很容易形成数据库表。您只需要两列:页索引和二进制数组。当您分配一个页面时,您只需在表中存储一个具有正确页面索引和空二进制数组的行。

例如,对于1024位的页面大小(生成2 ^二十二 最大页数),您可以这样构造表:

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));

由于 pigeonhole principle .不可避免地,您试图将事物塞进m槽(其中n>>m)。您所需要做的只是不处理冲突情况并选择足够大的哈希表。

当然!决定你能负担多少“箱”(每一位一个),比如n;把IP地址散列成一个位B的字符串;取b模n。你可以计算意外碰撞的概率(用某种近似值,比如假设所有散列的IP地址都是同样可能的位串b),并相应地确定n,如果你对最大访问量有限制。牙科碰撞概率,您的应用可以接受。

开始截断位。

当一个可能的2^n中有2^(n/2)个内容时,哈希冲突的概率将变为50%。IP地址为2^32,因此当容器中有2^16个内容时,冲突的概率为50%。

随感觉舒服而减少。

整数(ipv4)或字符串(ipv6)哈希,不进行冲突处理,使用哈希值(modulo hash table size)作为位图数组的索引。