Design and Investigation of a Record System using Hash Collision Resolving Techniques: A Case Study

Jacob John*, Shaik Naseera**
* UG Scholar, School of Computer Science and Engineering, Vellore Institute of Technology, Vellore, Tamil Nadu, India.
** Associate Professor, School of Computer Science and Engineering, Vellore Institute of Technology, Vellore, Tamil Nadu, India.
Periodicity:October - December'2018
DOI : https://doi.org/10.26634/jse.13.2.15247

Abstract

With an increasing demand to structure data for efficient access in large data warehouses, hash tables serve as an efficient way for the implementing dictionaries by providing with keys to values of the dictionary. However, such algorithms tend to get computationally expensive due to collisions in a hashing (or hash) table. A searching in the hash table under reasonable assumptions, could take an expected time of O(1) (Aspnes, 2015). Although, in practice, when hashing performs extremely well, it could take as long as a linked list in a worst case scenario, which is O(n) (Sing & Garg, 2009). Collision occurs when two keys hash to the same slot or value. The purpose of this article is to research and provide a comparative study on the different hashing techniques and then implement a suitable one for a banking record system scenario.

Keywords

Hashing, Hash Tables, Collisions, Algorithm, C Language, Record System, Double Hashing

How to Cite this Article?

John, J., Naseera, S. (2018). Design and Investigation of a Record System using Hash Collision Resolving Techniques: A Case Study, i-manager's Journal on Software Engineering, 13(2), 37-43. https://doi.org/10.26634/jse.13.2.15247

References

[1]. Aspnes, J. (2015). Notes on Data Structures and Programming Techniques. New Haven: Yale U. CPSC 223, Spring 2015, Yale University.
[2]. Coffman, E. G. J., & Eve, J. (1970). File structures using hashing functions. Communications of the ACM, 13(7), 427-432.
[3]. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to Algorithms. MIT Press.
[4]. Danker, S., Ayers, R., & Mislan, R. P. (2009). Hashing Techniques for Mobile Device Forensics. Small Seate Digital Forensics Journal, 3(1), 1-6.
[5]. Devillers, R., & Louchard, G. (1979). Hashing techniques, a global approach. BIT Numerical Mathematics, 19(3), 302-311.
[6]. Harrison, G. (2016, March). The Database Technologies of the Future. Database Trends and Applications. Retrieved from http://www.dbta.com/ Authors/Guy-Harrison-3539.aspx
[7]. Hash Tables. (2016). Data Structures and Algorithms. Tutorials Point (I) Pvt. Ltd.
[8]. Horowitz, E., Sahni, S., & Rajasekaran, S. (2008). Fundamentals of Computer Algorithms, Second Ed. New Delhi, India.
[9]. Nemes, R. M. (1992). U.S. Patent No. 5,121,495. Washington, DC: U.S. Patent and Trademark Office.
[10]. Rathi, A., Lu, H., & Hedrick, G. E. (1991). Performance comparison of extendible hashing and linear hashing techniques. ACM SIGSMALL/PC Notes, 17(2), 19-26.
[11]. Singh, M., & Garg, D. (2009, March). Choosing best hashing strategies and hash functions. In Advance Computing Conference, 2009. IACC 2009. IEEE International (pp. 50-55). IEEE.
[12]. Srivastava, S. K., & Srivastava, D. (2003). Data Structures through C in depth. BPB Publications.
[13]. Vlajic, & Natalija, (2003). COSC 2011: Fundamentals of Data Structures. Department of Computer Science, York University.
[14]. Wang, J., Kumar, S., & Chang, S. F. (2012). Semi-supervised hashing for large-scale search. IEEE Transactions on Pattern Analysis & Machine Intelligence, 12(2012), 2393-2406.
[15]. Wolfson, H. J., & Rigoutsos, I. (1997). Geometric hashing: An overview. IEEE Computational Science and Engineering, 4(4), 10-21.
If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Single Article

North Americas,UK,
Middle East,Europe
India Rest of world
USD EUR INR USD-ROW
Online 15 15

Options for accessing this content:
  • If you would like institutional access to this content, please recommend the title to your librarian.
    Library Recommendation Form
  • If you already have i-manager's user account: Login above and proceed to purchase the article.
  • New Users: Please register, then proceed to purchase the article.