CFP last date
22 April 2024
Reseach Article

An Efficient Strategy for Collision Resolution in Hash Tables

by Peter Nimbe, Samuel Ofori Frimpong, Michael Opoku
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 99 - Number 10
Year of Publication: 2014
Authors: Peter Nimbe, Samuel Ofori Frimpong, Michael Opoku
10.5120/17411-7990

Peter Nimbe, Samuel Ofori Frimpong, Michael Opoku . An Efficient Strategy for Collision Resolution in Hash Tables. International Journal of Computer Applications. 99, 10 ( August 2014), 35-41. DOI=10.5120/17411-7990

@article{ 10.5120/17411-7990,
author = { Peter Nimbe, Samuel Ofori Frimpong, Michael Opoku },
title = { An Efficient Strategy for Collision Resolution in Hash Tables },
journal = { International Journal of Computer Applications },
issue_date = { August 2014 },
volume = { 99 },
number = { 10 },
month = { August },
year = { 2014 },
issn = { 0975-8887 },
pages = { 35-41 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume99/number10/17411-7990/ },
doi = { 10.5120/17411-7990 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:27:52.428045+05:30
%A Peter Nimbe
%A Samuel Ofori Frimpong
%A Michael Opoku
%T An Efficient Strategy for Collision Resolution in Hash Tables
%J International Journal of Computer Applications
%@ 0975-8887
%V 99
%N 10
%P 35-41
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This paper presents NFO, a new and innovative technique for collision resolution based on single dimensional arrays. Hash collisions are practically unavoidable when hashing a random subset of a large set of possible keys and should be seen as an event that can disrupt the normal operations or flow of hash functions computing an index into an array of buckets or slots. Hash tables provide efficient table implementations but then its performance is greatly affected if there are high loads of collisions. This new approach intends to manage these collisions effectively and properly although there are some algorithms for handling collisions currently. NFO incorporates certain features to resolve some problems of existing techniques. The performance of our approach is quantified via analytical modeling and software simulations. Efficient implementations that are easily realizable and productive in modern technologies are discussed. The performance benefits are significant and require machines with moderate memory and speed specifications. Depending on observations of the results of implementation of the proposed approach or technique on a set of real data of several types, all results are registered and analyzed.

References
  1. Clifford, A. Shaffer. , 2007. Hashing Tutorial.
  2. Erickson, J. , 2009. Hash Tables
  3. Bruno, D. G. , 1999. Data structures and algorithm with object oriented design in C++ (1* Ed). Addison Wesley Publishing Company-America. PP. 225-248
  4. Archaya, A. , 2012. Input Segmented Universal Hashing
  5. D. E. Knuth. , 1998. The Art of Computer Programming: Sorting and Searching, volume3. Addison- Wesley Longman, second edition.
  6. Jauhar, A. , 2008. Hashing: Collision Resolution Schemes
  7. Bello, S. A. , Liman, A. M. , Gezawa, A. S. , Garba, A. , Ado, A. , "Comparative Analysis of Linear Probing, Quadratic Probing and Double Hashing Techniques for Resolving Collusion in a Hash Table", International Journal of Scientific & Engineering Research, 2014
  8. Askitis, N, Zobel, J. , 2005. Cache-Conscious Collision Resolution in String Hash Tables
Index Terms

Computer Science
Information Sciences

Keywords

Hash Function Open Addressing Separate Chaining Linear Probing Quadratic Probing Double Hashing