## 5 Performance Evaluation
For the functional Bloom filter, the average and the worst-case number of accesses are the same as the number of memory accesses is always equal to \(k\). Figures 5 and 6 show the average and the worst-case number of memory accesses during search procedure, respectively. Unlike insertion performance, the cuckoo hash table practically has the same performance as the multi-hash table because two hash functions for each element are used, and therefore each of the search procedure is completed within two accesses. In case of the \(d\)-left hash table, as the number of hash functions \(d\) is equal to \(k\), the search procedure is completed within \(k\) accesses. The search performance of the functional Bloom filter is also \(k\) accesses as the same as insertion performance. Figure 7 shows the comparison on search failure rates between theoretical and simulation results as the load factor increases. It is shown that the theoretical and simulation results become similar as the load factor increases. For the theoretical results of hash tables, Labels (16), (21), and (25) are used for \(\alpha\leq 1\), and Labels (18), (23), and (27) are used for \(\alpha>1\). In cases of the multi-hash table and the cuckoo hash table, parameters determining the performance of a data structure, such as the number of buckets and the number of hash functions, are the same, and therefore these tables have almost the same theoretical upper bounds. In evaluating the performance of data structures, the worst-case performance is the most critical, and thus the upper bound is important. It is shown that simulation results are less than the upper bound, as the worst case was assumed in calculating the upper bounds for these structures. Because a cuckoo hash table can access more buckets in inserting an element than a multi-hashing table, it has a better search failure rate when the load factor is 0.6, but no meaningful difference when the load factor is larger than 0.6. Figure 3: Average number of accesses in inserting an element: (a) 8k; (b) 32k; (c) 130k. In cases of the \(d\)-left hash table and the functional Bloom filter, simulation results show very similar patterns to their theoretical results. As shown in Figure 7, the functional Bloom filter shows the best search failure rate when \(\alpha\) increases. More specifically, in terms of the simulation result for 130k at \(\alpha=1\) shown in Figure (c)c, the search failure rate of the Multi-HT is 5%, and it is ten times larger than that of the FBF, which is 0.5%. Note that the search failure rate of the FBF decreases slightly as the number of elements increases, as \(\frac{m}{n}\) for the FBF increases as the number of elements increases. Therefore, the functional Bloom filter is the most efficient structure which can replace hash  
Figure 4: Worst-case number of accesses in inserting an element: (a) 8k; (b) 32k; (c) 130k. Figure 5: Average number of accesses in a search: (a) 8k; (b) 32k; (c) 130k. Figure 6: Worst-case number of accesses in a search: (a) 8k; (b) 32k; (c) 130k. tables, when the search failure rate is the most concern in storing a large set of elements to a limited size of memory.