Research and Implementation of Hardware Hash Table Based on d-left Algorithm
基于d-left算法的硬件哈希表研究与实现

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 onchip 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.