Abstract
Hashing is a procedure that can be used for a program to gain access to data quickly. It is very popular in many IT areas such as route lookup, cryptography development, and string data indexing for fast searching among others. Open Addressing and Separate Chaining are the generally two known collision resolutions if a hash function fails to plot a unique index. Engaging any collision resolution will result in multiple key comparisons and memory accesses causing time to increase linearly thus the lookup latency becomes indeterminate, posing an unpredictable outcome to some time-critical systems. Although the collision problem is inevitable, the proposed hashing algorithm using 2D vector and hash functions on its collision resolution can achieve lookup time at one or two memory accesses while resolving the collision.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Khorasani F, Belviranli ME, Gupta R, Bhuyan LN (2016) Stadium hashing: scalable and flexible hashing on GPUs. In: Parallel architectures and compilation techniques—conference proceedings, PACT, vol 2016–March, pp 63–74. https://doi.org/10.1109/pact.2015.13
Singh M, Garg D (2009) Choosing best hashing strategies and hash functions. In: 2009 IEEE international advance computing conference, IACC 2009, pp 50–55. https://doi.org/10.1109/pact.2015.13
He G, Du Y, Yu D (2016) Efficient hashing technique based on bloom filter for High-Speed Network. In: Proceedings—2016 8th international conference on intelligent human-machine systems and cybernetics, IHMSC 2016, vol 1, pp 58–63. https://doi.org/10.1109/ihmsc.2016.94
Li D, Li J, Du Z (2016) Deterministic and efficient hash table lookup using discriminated vectors. In: Proceedings of 2016 IEEE global communications conference, GLOBECOM 2016, 2016, pp 0–5. https://doi.org/10.1109/glocom.2016.7841732
Song T, Yang Y, Crowley P (2017) RwHash: rewritable hash table for fast network processing with dynamic membership updates. In: 2017 ACM/IEEE symposium architecture network communication system, pp 142–152. https://doi.org/10.1109/ancs.2017.28
Cantu M, Kim J, Finding hash collisions using MPI on HPC clusters, pp 1–6. https://doi.org/10.1109/lisat.2017.8001961
Kidon M, Dobai R (2017) Evolutionary design of hash functions for IP address hashing using genetic programming. In: Proceedings of 2017 IEEE congress on evolutionary computation, CEC 2017, pp 1720–1727. https://doi.org/10.1109/cec.2017.7969509
Liu D, Xu S, Liu H, Cui Z (2014) An empirical study on the performance of Hash Table. In: ICIS 2014
Wang D, Jiang Y, Song H, He F, Gu M, Sun J (2017) Verification of implementations of cryptographic hash functions. IEEE Access 5, no. c, 7816–7825. https://doi.org/10.1109/access.2017.2697918
Steinebach M, Klöckner P, Reimers N, Wienand D, Wolf P (2013) Robust hash algorithms for text. In: Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics), vol 8099 LNCS, pp 135–144. https://doi.org/10.1007/978-3-642-40779-6_11
Partow A Available hash function algorithm
Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Hash tables. In: Introduction to algorithms
Kumar S, Crowley P (2005) Segmented hash: an efficient hash table implementation for high-performance networking subsystems. In: 2005 symposium on architectures for networking and communications systems, ANCS 2005, pp 91–103. https://doi.org/10.1109/ancs.2005.4675269
Liu D, Xu S (2015) Comparison of hash table performance with open addressing and closed addressing : an empirical study 3(1), 60–68. https://doi.org/10.2991/ijndc.2015.3.1.7
Shaffer C (2012) Data structures and algorithm analysis, 2
Franek F (2003) Linked data structures, 132–158. https://doi.org/10.1017/cbo9780511584046.010
Bhullar RK (2016) A novel prime numbers based hashing technique for minimizing collisions. In: 2nd international conference on next generation computing technologies (NGCT-2016), 522–527. https://doi.org/10.1109/ngct.2016.7877471
Srinivasan J, Notes on hashing
Myers A (2014) CS 2112_ENGRD 2112 Fall 2014
Granville B, Del Tongo L (2008) Annotated reference with examples, p 101
CS240_ Data Structures & Algorithms I. (Online). Available: https://www.cpp.edu/~ftang/courses/CS240/lectures/hashing.htm. Accessed: 15 Sep 2017
Sullivan DG (2012) Fall 2012 alternative representation : a linked list, pp 1–19
Straub J (2008) C programming : data structures and algorithms
Cho C, Lee J, Ryoo J (2017) A collision-mitigation hashing scheme utilizing empty slots of cuckoo hash table, pp 514–517. https://doi.org/10.23919/icact.2017.7890143
Limon MR, Sharker R, Biswas S, Rahman MS (2014) Efficient de Bruijn graph construction for genome assembly using a hash table and auxiliary vector data structures. In: 2014 17th international conference on computer and information technology, ICCIT 2014, pp 121–126. https://doi.org/10.1109/iccitechn.2014.7073147
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Eclarin, B.A., Fajardo, A.C., Medina, R.P. (2019). Enhanced Hash Algorithm Using a Two-Dimensional Vector to Improve Data Search Performance. In: Piuri, V., Balas, V., Borah, S., Syed Ahmad, S. (eds) Intelligent and Interactive Computing. Lecture Notes in Networks and Systems, vol 67. Springer, Singapore. https://doi.org/10.1007/978-981-13-6031-2_32
Download citation
DOI: https://doi.org/10.1007/978-981-13-6031-2_32
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-6030-5
Online ISBN: 978-981-13-6031-2
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)