An absolute non-collision hash algorithm

In order to classify packet, a novel IP classification is proposed based the non-collision hash and jumping table trie-tree (NHJTTT) algorithm, which is based on non-collision hash trie-tree algorithm and grid of tries algorithm. The core of algorithm has three parts: one is the structure of hash function, which is constructed mainly based on destination/source port and protocol type field so that the hash function can avoid space explosion problem; two is that we transform grid of tries for the true trie-tree and jumping table in order to reduce space complexity; lastly we introduce the source port number (or source port range) bitmap chunk algorithm. After expanding normally, it doesn´t increase the time complex of algorithm because we introduce the jumping table. Space complexity consumed and space requirement of this algorithm are less than those of non-collision hash and grid of tries. The test results show that the classification rate of NHJTTT algorithm is up to 1 million packets per second and the maximum memory consumed is 8 MB for 10,000 rules.