함수 블룸필터와 해싱 기반 데이터 구조의 성능비교

Key-value data structures, which return a value corresponding to an input key, are commonly used in many applications. Hashing is a representative key-value data structure. However, as the load factor of the hash table increases, the number of collisions increases, and unsaved elements cause false results. In this paper, we propose to use a functional Bloom filter instead of the hash table. While the hash table should store the signature of each input key in addition to the return value, the functional Bloom filter stores values only. Simulation results show that the functional Bloom filter is more efficient than hashing-based data structures such as hashing with a linked list, cuckoo hashing, and d-left hashing. Especially when the load factor is close to 1, while the number of incorrect results increases in hashing-based data structures because of collisions, the functional Bloom filter provides more accurate results using the same amount of memory.