基于散列表的快速分組分類算法
2005-04-29 00:44:03李賓劉淑媛劉衍珩
吉林大學學報(理學版) 2005年6期
李 賓 劉淑媛 劉衍珩
摘要：通過分析Internet網絡主干路由器分組分類的關鍵問題和解決方案，提出了基于散列表的快速分組分類算法，該算法時間復雜度為O(1)；通過分析規則表的相關性將規則表分成相關子集和不相關子集，對不相關子集采用哈希法構造散列表．實驗測試表明，所給算法比順序匹配算法的吞吐率提高近10％．進一步分析了規則沖突，并給出了沖突的理論證明和查找算法。
關鍵詞：分組分類；散列表；規則表；相關規則；沖突檢測
中圖分類號：TP393
文獻標識碼：A
文章編號：1671-5489(2005)06-0787-07
