Advanced Micro Devices, Inc.
HYBRID FIRST-FIT K-CHOICE INSERTIONS FOR HASH TABLES, HASH SETS, APPROXIMATE SET MEMBERSHIP DATA STRUCTURES, AND CACHES

Abstract:

A hybrid mechanism for operating on a data item in connection with an associative structure combines first-fit and K-choice. The hybrid mechanism leverages advantages of both approaches by choosing whether to insert, retrieve, delete, or modify a data item using either first-fit or K-choice. Based on the data item, a function of the data item, and/or other factors such as the load statistics of the associative structure, one of either first-fit or K-choice is used to improve operation on the associative structure across a variety of different load states of the associative structure.