METHOD AND APPARATUS FOR IMPROVING HASH SEARCHING THROUGHPUT IN THE EVENT OF HASH COLLISIONS

摘要

A hash table data structure is provided that reduces the number of DMA operations, and if possible, the number of key comparisons, needed to traverse the table entries to find an entry that matches a key, especially with a bucket having several collisions. A new hash table entry called a “cumulative node” is introduced, which stores keys into a “key table” within the entry and includes pointers to metadata associated with the keys. The number of entries stored in the cumulative node depends on the size of the cumulative node, key size, and the size of the pointer type.