IIARD International Institute of Academic Research and Development

INTERNATIONAL JOURNAL OF COMPUTER SCIENCE AND MATHEMATICAL THEORY (IJCSMT )

E-ISSN 2545-5699
P-ISSN 2695-1924
VOL. 11 NO. 5 2025
DOI: 10.56201/ijcsmt.vol.11.no5.2025.pg34.45

---

Collision Resolution Hash Tables: A Comparative Performance Study Using Synthetic Data in C++

Dambo Itari, Obhuo Benjamin and Oguara Richard

---

Abstract

Hash tables are essential for fast data storage and retrieval; however, managing collisions remains a core challenge that affects overall efficiency. This research aims to evaluate and compare the performance of three prominent collisions resolution strategies; Linear Probing, Quadratic Probing, and Double Hashing in hash tables. To achieve this, C++ implementation was developed, and synthetic datasets of varying sizes were generated to simulate different load conditions. The research employed experimental method, measuring key performance indicators such as execution time, number of collisions and memory consumption across multiple trials were employed to assess performance under varying load factors. The results reveal that Linear Probing is prone to primary clustering leading to significant performance degradation as the load factor increases. Quadratic Probing mitigates clustering more effectively but encounter limitations when its probing sequence cycles. Double Hashing consistently outperforms the other techniques, delivering superior results through more uniform distribution of keys, particularly in high-load environments. This study concludes that Double Hashing offers the best balance of speed and efficiency for collision resolution, making it a preferred choice for optimizing hash table performance in data-intensive and high-performance computing applications.

keywords:

Hash Tables, Collision Resolution, Linear Probing, Quadratic Probing, Double Hashing, C++ Implementation

---

References:

1. Wang, Q. (2025). The Bathroom Model: A realistic approach to hash table algorithm
optimization arXiv. https://doi.org/10.48550/arXiv.2502.10977
2. 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. Proceedings of
International Conference on Computational Inteligience ,153-
165.https://doi.org/10.1007/978-981-97-3526-6_13
3. Fatourou, P., Kallimanis, N. D., & Ropars, T. (2022). An efficient wait-free resizable hash
table. arXiv. https://arxiv.org/abs/2204.09624
4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to
algorithms (4th ed.). MIT Press.
5. Hassan, F. A., Farah, N. I., & Haifaa, A. H. (2022). A review of hash function types and
their applications. Wasit Journal of Computer and Mathematics Science, 3(1), 120–139.
6. Bender, M. A., Conway, A., Farach-Colton, M., Kuszmaul, W., & Tagliavini, G. (2021).
Iceberg hashing: Optimizing many hash-table criteria at once. arXiv.
https://arxiv.org/abs/2109.04548
7. Pandey, P., Bender, M. A., Conway, A., Farach-Colton, M., Kuszmaul, W., Tagliavini, G.,
& Johnson, R. (2022). IcebergHT: High performance PMEM hash tables through stability
and low associativity. arXiv. https://arxiv.org/abs/2210.04068
8. Knuth, D. E. (2022). The art of computer programming, volume 3: Sorting and searching
(2nd ed.). Addison-Wesley.
9. Hassan, F.A., Farah, N.I & Haifaa A.H (2022). A review of Hash function types and their
applications. Wasist Journal of Computer and Mathematic Science, 3(1), 120-139.
10. Ahmed, D.Y., Saleh, A., Mouussa, M.B., & Salisu, I.Y (2021). Collision resolution
techniques in hash table: A review. International Journal of Advance Computer Science
and Application, 12(9), 120-139.
11. Qin, C., Zhang, L., Yang., Y., & Lu, C (2022). Adaptive and dynamic multi-resolution
hashing for pairwise summations. Proceedings of the 39thInternational Conference on
Machine Learning,162:18639-18658. https://proceedings.mir.press/v162/qin22a.html
12. Lu, Y., Shen, M., Wang, H., Wang, X., Van Rechem, C., Fu, T., & Wei, W. (2023),
Machine learning for synthetic data generation: A review. arXiv.
https://doi.org/10.48550/arXiv.2302.04062
13. Álvarez, Á., & Vaz, B. (2022). Survey on synthetic data generation, evaluation methods
and GANs. Mathematics, 10(15), 2733. https://doi.org/10.3390/math10152733
14. Mitzenmacher, M.,&Upfai,E (2017).Probability and Computing: Randomization and
probalististic techniques in algorithms and Data analysis (2nd ed.).
15. Nimbe, Peter, Samuel Ofori Frimpong, & Michael Opoku (2014).” An efficient strategy
for collision resolution in hash tables,” International Journal of Computer Applications
99(10), 35-41
16. Bello, S.?A., Mukhtar, A.?L., Gezawa, A.?S., Garba, A., & Ado, A. (2014). Comparative
analysis of linear probing, quadratic probing, and double hashing techniques for resolving
collision in a hash table. International Journal of Scientific & Engineering Research, 5(4),
685–686.

DOWNLOAD PDF

---

Back