An Improved Method of Hash Table Based on Transform and Conquer

Abstract:

This paper presented a improved method of hash table, the algorithm based on transform and conquer, established a number of small-scale array, then imitated binary search processes and reduced the hash collision. Simulation results shows that , not only the continuous memory requirement is reduced greatly, but also that when the hash collisions occur, the searching efficiency is improved by an order of magnitude from O(n) to O(logn), the space utilization rate is also improved greatly.

• Periodical: Applied Mechanics and Materials (Volumes 556-562)
• Pages: 6203-6206
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.556-562.6203
• Online since: May 2014
• Authors: Wei Gan*, Ying Hua Zhou
• Keywords: Conquer, Hash Collision, Hash Table, Searching, Transform

References

[1] Thomas H. Cormen Charles E. Leiserson, Ronald L. Rivest Clifford Stein. Introduction to Algorithms[M]. Beijing: Mechanical Industry Press, 2013: 142-155.

DOI: 10.1177/0036850419873799b

[2] Kumar S, Turner J, Crowley P. Peacock hashing: Deterministic and updatable hashing for high performance networking[C]/The 27th Conference on Computer Communications. Washington, DC: IEEE Computer Society, 2008: 101-105.

DOI: 10.1109/infocom.2008.29

[3] Lu Y, Prabhakar B, Bonomi F, Perfect hashing for network application[C]/IEEE Symposium on Information Theory. NY: IEEE Press, 2006: 2774-2778.

DOI: 10.1109/isit.2006.261567

[4] AHMADI M, WONG S. A memory-optimized bloom filer using an additional hashing function[C]/IEEE Global Telecommunications conference, Washington, DC: IEEE Computer Society, 2008: 1-5.

DOI: 10.1109/glocom.2008.ecp.476

[5] Anany Levitin. Design and analysis of algorithms[M]. Version2: Beijing: Tsinghua University Press, 2011: 150-151.

[6] Kyle Loudon. Algorithm succinctly[M]. Beijing: Mechanical Industry Press, 2012: 119-136.