请教一个IP地址查找的算法问题，谢谢！

duanjigang

有一个功能模块，上面注册了N个函数，称之为 F1, F2......FN
每个函数FI上面定义了一个IP地址范围的列表，用(网络地址1，掩码1), (网络地址2，掩码2)....(网络地址m，掩码m)的方式表示。
这个功能模块的工作过程是:
拿到一个数据包，如果数据包的目的IP在这个N个函数其中的某个函数的IP地址段列表当中，则调用该函数进行处理，如果有重复，以第一个查找到的函数为基准，其它匹配到
的函数不处理；对于IP地址段，也是只以第一个为基准，如果查找到，后面的就不用管了，直接返回。

不知道功能需求说明白没，如果说明白，继续往下看：:wink:
问题是怎样的处理方法才能使得查找更高效？
我采用大概最笨的方法：来一个报文，遍历每个函数，然后在函数的IP地址段列表中进行匹配，
如果 网络地址N & 掩码N == IP地址 & 掩码N，则认为查找到，调用函数处理报文，返回。
但是有人说这样效率太低，建议采用哈希表方式存储，对于哈希表存储，我几乎没用过，就知道大概的原理，但是对于本文中的问题，不知道怎么组织，希望
比较熟悉hash算法的朋友指点一二，谢谢！

IT王子

同意ｈａｓｈ表方式

贺兰云天

原帖由 IT王子 于 2009-6-29 14:03 发表
同意ｈａｓｈ表方式

具体说说怎么做？算法描述下

IT王子

原帖由 贺兰云天 于 2009-6-29 14:04 发表

具体说说怎么做？算法描述下

HASH函数的功能就是把你的ＩＰ段映射到F1,F2,F3...Fn，不合法的ＩＰ没有映射到任何一个Ｆ函数，合法的ＩＰ就映射到其中一个。。。

yikaikai

数据结构里面有

贺兰云天

原帖由 IT王子 于 2009-6-29 14:10 发表

HASH函数的功能就是把你的ＩＰ段映射到F1,F2,F3...Fn，不合法的ＩＰ没有映射到任何一个Ｆ函数，合法的ＩＰ就映射到其中一个。。。

不是吧，初始化时，每个IP段就已经指向它所属的函数了，问题的关键是怎样把数据包的IP地址映射到它可能所属的IP段，只要IP到IP段的查找实现了。调用函数
是很快的事情，我要的就是这个IP地址查找IP段的方法

贺兰云天

跟数学系的同事讨论了，差不多用IP地址段分组，先定位到组，然后定位到段，我先去试试

yikaikai

其实和hash原理一样的