Mar 22, 2025

As we are filtering in the construction of the table, the LF starts at 1 and progresses (e.g. to 1.5) as the table populates. Given the presumption of almost no duplicates ("true positives"), the FP rate indicates the ratio of body searches to inserts while building the table. The FP rate is a non-linear monotonically increasing function of the LF. Basically like any hash function, an increasing load factor increases the search cost from constant toward linear. Given the presumption that nearly all searches will be negative, it follows that each search exhausts a bucket's conflict list - where the LF is the average conflict list length. So search cost (i.e. paging) is the product of the LF and FP rate or x * y on the above graph.