Mar 15, 2025

However, using a smaller hash digest for the Cuckoo filter, and associating multiple of these to the conflict list, the efficiency per filter bye is much higher. For example, four one byte filters, each with a sentinel value, allows match of 4 independent conflicts in each conflict stack. Also a small number of distinct values that hash to the same value (1 in 255). This allows capture of slightly more than all values in conflict lists of 1,2,3 and 4 elements. Zero elements doesn’t require a filter. Above 4 elements is very small. This allows us to avoid conflict resolution for all but 1 in 255 single value lists, 2 in 255 for 2 element lists, 3 in 255 for 3, 4 for 4. No exclusion for 5 and above. This gives us a search rate of 1% for a full table, and 1 in almost 200 on average for table population from zero.