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

Question

我有像这样的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;
}

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

更新:

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

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

Answer 1

当涉及到它时,我只需要知道IP是否存在于任何5M范围内.

我会考虑一个n-ary树,其中n = 256,并使用虚线地址而不是转换后的整数.

顶级是256个对象的数组.一个null条目意味着"否"没有包含地址的范围,因此假设您的示例192.168.1.0/24数组[192]将包含一个对象,但是数组[100]可能为空,因为没有为任何100.xxx/n定义范围

存储的对象包含(引用)另一个数组[256]和范围说明符,只有两个中的一个被设置,因此192.0.0.0/8最终会有一个范围说明符,指示该范围内的所有地址都要被过滤.这将允许像192.255.0.0/10地址的前10位重要的地方1100 0000 11xx xxxx- 否则你需要检查第二级数组中的下一个八位字节.

最初合并重叠的范围,如果有的话,到更大的范围内......如3 .. 10和7 .. 16成为3 .. 16......允许这一点,因为你不需要与给定的IP相关联,其范围定义它.

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

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

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