An Efficient Strategy for Collision Resolution in Hash Tables
|
10.5120/17411-7990 |
Peter Nimbe, Samuel Ofori Frimpong and Michael Opoku. Article: An Efficient Strategy for Collision Resolution in Hash Tables. International Journal of Computer Applications 99(10):35-41, August 2014. Full text available. BibTeX
@article{key:article,
author = {Peter Nimbe and Samuel Ofori Frimpong and Michael Opoku},
title = {Article: An Efficient Strategy for Collision Resolution in Hash Tables},
journal = {International Journal of Computer Applications},
year = {2014},
volume = {99},
number = {10},
pages = {35-41},
month = {August},
note = {Full text available}
}
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
- Clifford, A. Shaffer. , 2007. Hashing Tutorial.
- Erickson, J. , 2009. Hash Tables
- Bruno, D. G. , 1999. Data structures and algorithm with object oriented design in C++ (1* Ed). Addison Wesley Publishing Company-America. PP. 225-248
- Archaya, A. , 2012. Input Segmented Universal Hashing
- D. E. Knuth. , 1998. The Art of Computer Programming: Sorting and Searching, volume3. Addison- Wesley Longman, second edition.
- Jauhar, A. , 2008. Hashing: Collision Resolution Schemes
- 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
- Askitis, N, Zobel, J. , 2005. Cache-Conscious Collision Resolution in String Hash Tables