gpt4 book ai didi

java - Java中IP地址过滤器内存数据结构的最佳选择

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:16:23 25 4
gpt4 key购买 nike

我有这样的 CIDR 格式的文件 192.168.1.0/24,它被转换成这种两列结构

3232236030 3232235777

每个字符串 IP 地址转换都发生在这段代码中:

String subnet = "192.168.1.0/24";
SubnetUtils utils = new SubnetUtils(subnet);

Inet4Address a = (Inet4Address) InetAddress.getByName(utils.getInfo().getHighAddress());
long high = bytesToLong(a.getAddress());
Inet4Address b = (Inet4Address) InetAddress.getByName(utils.getInfo().getLowAddress());
long low = bytesToLong(b.getAddress());

private static long bytesToLong(byte[] address) {
long ipnum = 0;
for (int i = 0; i < 4; ++i) {
long y = address[i];
if (y < 0) {
y += 256;
}
ipnum += y << ((3 - i) * 8);
}
return ipnum;
}

考虑到 (low high : 3232236030 3232235777) 有超过 500 万个条目。
还会有交叉点,因此 IP 可以来自多个范围。只要第一个就够了。
数据是只读的。
找到 ipToBefiltered 所属范围的最快方法是什么?该结构将完全在内存中,因此无需数据库查找。

更新:

我找到了这个 Peerblock项目(它有超过百万的下载量所以我认为它必须有一些快速算法): http://code.google.com/p/peerblock/source/browse/trunk/src/pbfilter/filter_wfp.c

有谁知道该项目使用什么技术来创建范围列表而不是搜索它们?

最佳答案

When it comes down to it I just need to know if the IP is present in any of the 5M ranges.

我会考虑一棵 n 元 树,其中 n=256,并从点分地址而不是转换后的整数开始工作。

顶层是一个包含 256 个对象的数组。 null entry 表示“否”没有包含地址的范围,所以给你的例子192.168.1.0/24 array[192] 将包含一个对象,但 array[100] 可能为空,因为没有为任何 100.x.x.x/n 定义范围

存储的对象包含一个(对)另一个数组[256] 和一个范围说明符,只有两者之一会被设置,所以192.0.0.0/8将以范围说明符结尾,指示该范围内的所有地址都将被过滤。这将允许像 192.255.0.0/10 这样的事情地址的前 10 位是有效的 1100 0000 11xx xxxx -- 否则您需要检查第二级数组中的下一个八位位组。

最初将重叠范围(如果有)合并为更大的范围...例如3 .. 107 .. 16变成 3 .. 16 ...允许这样做,因为您不需要将给定的 IP 与定义它的 范围相关联。

这应该需要不超过 8 次比较。每个八位字节最初直接用作索引,然后是空值比较,终端节点比较(它是一个范围还是指向下一个树级别的指针)

最坏情况下的内存消耗理论上是 4 GB (256 ^ 4)如果每个 IP 地址都在过滤范围内,但当然会合并为一个范围,因此实际上只有 1 个范围对象。更现实的最坏情况可能更像是 (256 ^ 3)或 16.7 MB。现实世界的使用可能会使每个级别的大多数数组 [256] 节点为空。

这本质上类似于霍夫曼/前缀编码。一旦找到答案(一个范围),最短的不同前缀就可以终止,所以通常你会得到 < 4 的平均值。比较。

关于java - Java中IP地址过滤器内存数据结构的最佳选择,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8316260/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com