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 8MB for 10,000 rules.