## 1 Introduction  
A key-value data structure that returns a value corresponding to an input key has been used in many fields [1; 2; 3]. Various network applications, such as Internet Protocol (IP) address lookup, packet classification, name lookup in Named Data Networking (NDN), traffic classification in Software-Defined Networking (SDN), and cloud computing [4; 5; 6; 7; 8], use key-value structures for data storage. For example, in performing a Pending Interest Table (PIT) lookup in the NDN, a content name is used as a key, and the input faces of each _Interest_ packet are returned as the value corresponding to the key [9; 10; 11; 12].  
As a representative key-value data structure, hashing has been popularly applied to various applications [13; 14; 15; 16]. Hashing converts an input key string to an index, which can be used to point an entry in a hash table. The pointed entry stores both the key itself (or the signature of the key) and a return value. Collision in hash indexes is an intrinsic problem of hash-based data structures. Elements that could not be stored in a hash table because of hash collisions cause failures in search process. To reduce the number of hash collisions, several variant structures have been studied such as multi-hashing, cuckoo hashing, and \(d\)-left hashing [17; 18; 19]. In order to avoid an excessive number of hash collisions, the load factor of a hash table, which indicates the ratio of the number of stored elements compared to the number of entries in a hash table, should be small enough.  
A functional Bloom filter satisfies the key-value operation required in various applications [20; 21; 22; 23; 24; 25]. Unlike a hash table, a functional Bloom filter does not require to store input keys, as different combinations of Bloom filter indexes for each input key can work as the signature of the input key.  
Even though modern hardware equipments have a sufficient amount of internal memory to accommodate large hash tables, an efficient use of the memory, which is a limited resource, is required to provide scalability. For example, according to Cisco's annual Internet report [26], IoT devices will account for 50 percent of all networked devices by 2023, and a 5G connection will generate nearly three times more traffic than the 4G connection of 2018 because there will be 29.3 billion networked devices by 2023, up from 18.4 billion of 2018. In order to keep up with the ever-increasing network traffic, it is necessary to build effective data structures which utilize limited memory resources efficiently [27; 28; 29].  
In this paper, we claim that a functional Bloom filter provides a lower search failure rate than hash-based data structures in storing a large amount of data to a limited size of memory. The search failure is the most important criterion for evaluating the performance of key-value structures. Therefore, as a key-value structure, the FBF can effectively replace hash tables. The basic idea of this paper was briefly introduced in [30], and we provide a thorough theoretical analysis and compare each data structure in their search failure probabilities in this paper. Our theoretical analysis is validated by simulation results for each structure.  
The remainder of this paper is organized as follows. Section 2 describes the Bloom filter and hash table as related works. In Section 3, we explain and compare four data structures: a multi-hash table, a cuckoo hash table, a \(d\)-left hash table, and a functional Bloom filter. Section 4 theoretically analyzes the probability of signature collision and the probability of search failure for each structure. Section 5 evaluates and compares the performance of each data structure, and Section 6 concludes the paper.