Collision Resolution Techniques in Hash Table: A Review

One of the major challenges of hashing is achieving constant access time O (1) with an efficient memory space at a high load factor environment when various keys generate the same hash value or address. This problem causes a collision in the hash table, to resolve the collision and achieve constant access time O (1) researchers have proposed several methods of handling collision most of which introduce a non-constant access time complexity at a worst-case scenario. In this study, the worst case of several proposed hashing collision resolution techniques are analyzed based on their time complexity at a high load factor environment, it was found that almost all the existing techniques have a non-constant access time complexity. However, they all require an additional computation for rehashing keys in a hash table some of which is as a result of deadlock while iterating to insert a key. It was also found out that there are wasted slots in a hah table in all the reviewed techniques. Therefore, this work, provides an in-depth understanding of collision resolution techniques which can serve as an avenue for further research work in the field.

@article{Yusuf2021,
  title     = {Collision Resolution Techniques in Hash Table: A Review},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {12},
  number    = {9},
  year      = {2021},
  publisher = {The Science and Information Organization},
  author    = {Ahmed Dalhatu Yusuf and Saleh Abdullahi and Moussa Mahamat Boukar and Salisu Ibrahim Yusuf},
  doi       = {10.14569/IJACSA.2021.0120984},
  url       = {https://doi.org/10.14569/IJACSA.2021.0120984}
}