ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2017, Vol. 54 ›› Issue (11): 2508-2515.doi: 10.7544/issn1000-1239.2017.20160795

Previous Articles     Next Articles

DCuckoo: An Efficient Hash Table with On-Chip Summary

Jiang Jie1, Yang Tong1,2, Zhang Mengyu1, Dai Yafei1, Huang Liang3, Zheng Lianqing4   

  1. 1(School of Electronics Engineering and Computer Science, Peking University, Beijing 100871); 2(Collaborative Innovation Center of High Performance Computing, National University of Defense Technology, Changsha 410073); 3(Military 94782/65, Hangzhou 310021); 4(Department of Control Engineering, Xijing University, Xi'an 710123)
  • Online:2017-11-01

Abstract: Hash tables are extensively used in many computer-related areas because of their efficiency in query and insertion operations. However, Hash tables have two disadvantages: collisions and memory inefficiency. To solve these two disadvantages, minimal perfect Hash table uses N locations to store N incoming elements. However, MPHT doesn't support incremental updates. Therefore, in this paper, combining Cuckoo hashing and d-left hashing, we propose a novel Hash table architecture called DCuckoo, which ensures fast query speed, fast update speed in worst cases, efficient utilization of memory and dynamic capacity change. In DCuckoo, multiple sub-tables and Cuckoo hashing's mechanism of transferring existing elements are used to improve the load factor. Pointers except for ones in the last sub-table are eliminated for less wasted space. Also, in order to optimize the query performance, fingerprints and bitmaps are used as a summary in on-chip memory to reduce off-chip memory accesses. The bucket will be probed only if the corresponding fingerprint is matched in on-chip memory. We conduct a series of experiments to compare the performance of DCuckoo and other five Hash table schemas. Results demonstrate that DCuckoo eliminates shortcomings of both Cuckoo hashing and d-left hashing, hence DCuckoo achieves the four design goals.

Key words: Hash table, lookup, fingerprint, on-chip memory, key-value store

CLC Number: