A Bloom Filter with the Integrated Hash Table Using an Additional Hashing Function

Mahmood Ahmadi, Reza Pourian


A Bloom filter is a simple space-efficient randomized data structure

for representing a set in order to support membership queries. In recent years, Bloom filters have increased in popularity in database and networking applications. A Bloom filter has two steps that called programming and membership query. In this paper, we introduce a new approach to integrate

a hash table with Bloom filter to decrease the hash table access time. This means that when a Bloom filter for an incoming item is programmed, the incoming item simultaneously is stored in a hash table. In addition in the membership query step, if the query is successful, simultaneously the address of item in the hash table is generated.

Furthermore, we analyze the average bucket size, maximum search length and number of collisions for the proposed approach and compare to the fast hash table (FHT) approach. We implemented our approach in a software packet classifier based on tuple space search with the $H3$ class of universal hashing functions. Our results show that our approach is able to reduce the average bucket size, maximum search length and number of collisions when compared to a FHT.


Bloom filters, packet classification, hashing functions

Full Text:


DOI: https://doi.org/10.5296/npa.v7i1.6240

To make sure that you can receive messages from us, please add the 'macrothink.org' domain to your e-mail 'safe list'. If you do not receive e-mail in your 'inbox', check your 'bulk mail' or 'junk mail' folders.

Copyright © Macrothink Institute ISSN 1943-3581