Research and Implementation of Hardware Hash Table Based on d-left Algorithm
Tan Xing-ye · Jisuanji yingyong yanjiu · 2005
Hash table, with its lower cost and better scalability, is widely used in many routing and packet classification algorithms. This paper presents an approach for obtaining high-performance hardware Hash table based on d-left algorithm and on-chip CAM. The time complexity of insertion and lookup time of Hash table is only by using d-left algorithm. Benefiting from faster on-chip CAM, the failure probability of insert operation decrease to ultra low level, at the same time, the availability ratio of memory is improved dramatically. The results of the experiment and application show that it is practical and efficient.