基于散列表的快速分組分類算法

李　賓　劉淑媛　劉衍珩

摘要：通過分析Internet網(wǎng)絡(luò)主干路由器分組分類的關(guān)鍵問題和解決方案，提出了基于散列表的快速分組分類算法，該算法時(shí)間復(fù)雜度為O(1)；通過分析規(guī)則表的相關(guān)性將規(guī)則表分成相關(guān)子集和不相關(guān)子集，對不相關(guān)子集采用哈希法構(gòu)造散列表．實(shí)驗(yàn)測試表明，所給算法比順序匹配算法的吞吐率提高近10％．進(jìn)一步分析了規(guī)則沖突，并給出了沖突的理論證明和查找算法。

關(guān)鍵詞：分組分類；散列表；規(guī)則表；相關(guān)規(guī)則；沖突檢測

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：A

文章編號：1671-5489(2005)06-0787-07