一种双哈希ip数据包分类算法研究

本文在无冲突哈希算法和异或哈希算法的基础上，提出了一种双哈希的ip分类算法，该算法的核心有三点：一是基于目的／源端口和协议域构造无冲突哈希，由于该三域的组合数目非常少，避免了空间爆炸；二是在异或哈希算法的基础上，将目的／源ip连成比特串后分为四块后进行异或，为了降低冲突率，将异或后的关键值再与一个随机数进行异或，获得分类索引值，并用此值生成多比特trie树，一般情况下减小了空间和时间复杂度；三是在trie树终点存放最终分类规则的索引值，为了保证查找到的规则的正确性，对每一个索引值的源／目的ip地址均匹配一