Abstract
Database Management Systems hash the data values into memory using a hash function to generate a key or hash using which data is stored at the appropriate memory location. This is done to ensure faster data retrieval operations from memory. Many times duplicate keys may be generated for different data points leading to a collision. Presently, there are varied algorithms to resolve collisions such as separate chaining, linear probing, quadratic probing, and double hashing. In this paper, we have worked to develop a new collision resolution algorithm titled as Binary Probing. Binary probing was developed with an objective to resolve the inadequacies of existing schemes. Binary probing works to efficiently hash the data values into the hash table using the divide and conquer method in association with binary tree and queue structures. Binary Probing was able to hash data values ranging from one lakh to one crore values in less than 1 s.
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
L. H. Byun H, “Comparison on Search Failure between Hash Tables and a Functional Bloom Filter,” Appl. Sci., vol. 10, p. 5218, 2020.
B. Hentschel, U. Sirin, and S. Idreos, “Entropy-Learned Hashing: Constant Time Hashing with Controllable Uniformity,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, Association for Computing Machinery, 2022, pp. 1640–1654.
S. Yusuf, Ahmed and Abdullahi, Saleh and Boukar, Moussa and Yusuf, “Collision Resolution Techniques in Hash Table: A Review,” Int. J. Adv. Comput. Sci. Appl., vol. 12, no. 9, 2021.
M. Bender, Michael A. and Farach-Colton, Martin and Kuszmaul, John and Kuszmaul, William and Liu, “On the Optimal Time/Space Tradeoff for Hash Tables,” in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pp. 1284–1297.
D. Liu and S. Xu, “Comparison of hash table performance with open addressing and closed addressing: An empirical study,” Int. J. Networked Distrib. Comput., vol. 3, no. 1, pp. 60–68, 2015.
W. Bender, Michael A. and Kuszmaul, Bradley C. and Kuszmaul, “Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering,” in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022, pp. 1171–1182.
H. Lessley, Brenton and Childs, “Data-Parallel Hashing Techniques for GPU Architectures,” IEEE Trans. Parallel Distrib. Syst., vol. 31, no. 1, pp. 237–250, 2020.
O. Green, “HashGraph—Scalable Hash Tables Using a Sparse Graph Data Structure,” ACM Trans. Parallel Comput., vol. 8, no. 2, 2021.
D. Köppl, “Separate Chaining Meets Compact Hashing,” pp. 1–14, 2019, [Online]. Available: http://arxiv.org/abs/1905.00163
A. Pagh, R. Pagh, and M. Ružić, “Linear probing with 5-wise independence,” SIAM Rev., vol. 53, no. 3, pp. 547–558, 2011.
P. Nimbe, S. Ofori Frimpong, and M. Opoku, “An Efficient Strategy for Collision Resolution in Hash Tables,” Int. J. Comput. Appl., vol. 99, no. 10, pp. 35–41, 2014, https://doi.org/10.5120/17411-7990.
R. A. . Mugher and N. A. M. . Alhammadi, “Performance Evaluation of Quadratic Probing and Random Probing Algorithms in modeling Hashing Technique,” J. Soft Comput. Data Min., pp. 52–59, 2022.
Y. M. K. Omar, H. Osama, and A. Badr, “Double Hashing Sort Algorithm,” Comput. Sci. Eng., vol. 19, no. 2, pp. 63–69, 2017.
S. Dhar, K. Pandey, M. Premalatha, and G. Suganya, “A tree based approach to improve traditional collision avoidance mechanisms of hashing,” in Proceedings of the International Conference on Inventive Computing and Informatics, ICICI 2017, 2018, pp. 339–342.
H. L. Dapeng Liu, Shaochun Xu, Zengdi Cui, “An Empirical Study on the Performance of Hash Table,” in 2014 IEEE/ACIS 13th International Conference on Computer and Information Science (ICIS), 2014, pp. 477–484.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Halkarnikar, P.P., Meshram, P.A., Joshi, S.S., Mahajan, D.A., Pawar, V. (2024). Binary Probing: A Novel Approach for Efficient Hash Table Operations. In: Tiwari, R., Saraswat, M., Pavone, M. (eds) Proceedings of International Conference on Computational Intelligence. ICCI 2023. Algorithms for Intelligent Systems. Springer, Singapore. https://doi.org/10.1007/978-981-97-3526-6_13
Download citation
DOI: https://doi.org/10.1007/978-981-97-3526-6_13
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-3525-9
Online ISBN: 978-981-97-3526-6
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)