## 5 Performance Evaluation  
In this section, we evaluate and compare the performance of four hash-based data structures described in the previous section using a specific example of name lookup in Named Data Networking (NDN), which uses a key-value data structure. In this application, keys are URLs and values are their output faces. As an FBF stores values only, the number of bits in an FBF cell is allocated according to the number of output faces; however, hash tables store the signature of a key and a corresponding value in pairs. Simulations are carried out using random URLs provided by Web Information Company ALEXA [47]. For simulation, we have randomly selected and made three experimental sets. Table 2 shows experimental data sets. Set \(S\) is stored to hash tables and to a functional Bloom filter. The number of URLs in input set \(U\) used in searching is three times the number of URLs of set \(S\). One-third of set \(U\) is the same as set \(S\), which means that these inputs should have a match from hash tables and from the functional Bloom filter. The remaining two-thirds is included in set \(S^{c}\), which means that these inputs do not have a match. We assume 14 kinds of return values, and therefore the size of a return value is 4 bits. In our simulation, search failure performance is evaluated in various load factors, and load factors are controlled by adjusting the size of a hash table instead of the number of stored elements. In other words, the number of elements to be inserted in a hash table is fixed, and the load factor is increased by reducing hash table sizes. We first construct a multi-hash table with load factors (\(\alpha\)) of 0.6, 0.8, 1, 1.2, and 1.4, and then measure the required amount of memory for each multi-hash table according to \(\alpha\). We then construct a cuckoo hash table, a \(d\)-left hash table, and a functional Bloom filter, using the same amount of memory as the multi-hash table. We assume that the number of hash functions \(d\) in a \(d\)-left hash table is equal to \(k\), which is the optimal number of hash indexes of a functional Bloom filter. A 64-bit cyclic redundancy check (CRC) generator is used as a hash function for our simulation. A number of hash indexes were extracted by combining a variable number of bits of a CRC code \begin{table}
\begin{tabular}{c c c} \hline \hline
**Set** & \(\mathbf{n(S)}\) & \(\mathbf{n(U)}\) \\ \hline
8k & \(2^{13}\) & \(2^{13}+2^{13}\times 2\) \\
32k & \(2^{15}\) & \(2^{15}+2^{15}\times 2\) \\
130k & \(2^{17}\) & \(2^{17}+2^{17}\times 2\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Number of elements in experimental data sets. generated by a key or an input. Therefore, even if multiple hash indexes are required, there is almost no difference in the amount of computational overhead, once a CRC code is obtained. Figure 3 shows the average number of memory accesses in inserting an element according to load factors. As the load factor increases, the cuckoo hash table requires a large number of accesses because many buckets are affected until an empty entry is found. The multi-hash table shows the best performance in most cases, as elements can be inserted if an empty entry is found even before two accesses. However, it is worth noting that the multi-hash table, the \(d\)-left hash table, and the functional Bloom filter have the performance proportional to \(O(1)\). The average number of memory accesses for the functional Bloom filter is always \(k\) obtained from Label (1). As the load factor increases, \(k\) decreases, as \(\frac{m}{n}\) in Label (1) decreases. Figure 4 shows the worst-case number of memory accesses in inserting an element according to load factors. As shown, the multi-hash table, the \(d\)-left hash table, and the functional Bloom filter show better performance than the cuckoo hash table, and these structures have a performance proportional to \(O(1)\). The worst-case performance of the cuckoo hash table is not acceptable as shown.