基于散列表的快速分组分类算法

李　宾　刘淑媛　刘衍珩

摘要：通过分析Internet网络主干路由器分组分类的关键问题和解决方案，提出了基于散列表的快速分组分类算法，该算法时间复杂度为O(1)；通过分析规则表的相关性将规则表分成相关子集和不相关子集，对不相关子集采用哈希法构造散列表．实验测试表明，所给算法比顺序匹配算法的吞吐率提高近10％．进一步分析了规则冲突，并给出了冲突的理论证明和查找算法。

关键词：分组分类；散列表；规则表；相关规则；冲突检测

中图分类号：TP393

文献标识码：A

文章编号：1671-5489(2005)06-0787-07