基于D维映射的布谷鸟哈希表

Cuckoo hash table based on D-dimensional mapping

哈希的数据结构和算法是海量信息存储的有效方式,特别是对于与网络流量测量、监控和安全相关的应用。目前存在许多哈希表算法,如布谷鸟哈希、Peacock Hash、Link Hash和Double Hash等,但是这些哈希算法仍存在着一些问题,如占用内存空间过大、插入查找等操作时间过长以及插入过程中遇到死循环而导致插入失败需要进行重新哈希等。针对这些问题,文中提出了基于D维映射的布谷鸟哈希算法,对哈希表进行属性划分,并增加链表结构,然后与辅助数据结构布隆过滤器和位图进行结合,并通过预先识别踢出操作是否有必要来减少不必要的内存访问次数,提高了哈希表的负载因子和插入查找效率。

Hash tables and hash functions provide an effective way to store massive data,especially for applications related to network traffic measurement,monitoring,and security.Current hashing algorithms,including cuckoo hashing,peacock hashing,link hashing and double hashing,still have some problems,such as occupying too much memory space,costing too long time during inserting and searching,and infinitely looping during inserting that may result in failed insertion and re-hashing.In this regard,this paper proposes a cuckoo hash algorithm based on D-dimensional mapping.This algorithm categorizes the attributes of the hash table,and adds a linked list structure.Then,it deploys an auxiliary data structure,the combination of the Bloom filter and the bitmap.The algorithm also reduces unnecessary memory accesses by determining the necessity of kick-out operation in advance,and improves the load factor of the hash table and the efficiency for insertion and search.