EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 600+ Courses All in One Bundle
  • Login

Hashing Function in C

Home » Software Development » Software Development Tutorials » C Programming Tutorial » Hashing Function in C

Hashing function in C

Introduction to Hashing Function in C

This article has a brief note on hashing (hash table and hash function). The most important concept is ‘searching’ which determines time complexity. To reduce the time complexity than any other data structure hashing concept is introduced which has O(1) time in the average case and the worst case it will take O(n) time.

Hashing is a technique with faster access to elements that maps the given data with a lesser key for comparisons. In general, in this technique, the keys are traced using hash function into a table known as the hash table.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

What is Hash Function?

The hash function is a function that uses the constant-time operation to store and retrieve the value from the hash table, which is applied on the keys as integers and this is used as the address for values in the hash table.

Types of a Hash Function In C

The types of hash functions are explained below:

1. Division method

In this method, the hash function is dependent upon the remainder of a division.

Example: elements to be placed in a hash table are 42,78,89,64 and let’s take table size as 10.

Hash (key) = Elements % table size;

2 = 42 % 10;

8 = 78 % 10;

9 = 89 % 10;

4 = 64 % 10;

The table representation can be seen as below:

hashing function in C

2. Mid Square Method

In this method, the middle part of the squared element is taken as the index.

Element to be placed in the hash table are 210, 350, 99, 890 and the size of the table be 100.

210* 210 = 44100, index = 1 as the middle part of the result (44100) is 1.

350* 350 = 122500, index = 25 as the middle part of the result (122500) is 25.

99* 99 = 9801, index = 80 as the middle part of the result (9801) is 80.

890* 890 = 792100, index = 21 as the middle part of the result (792100) is 21.

Popular Course in this category
C Programming Training (3 Courses, 5 Project)3 Online Courses | 5 Hands-on Projects | 34+ Hours | Verifiable Certificate of Completion | Lifetime Access
4.5 (5,617 ratings)
Course Price

View Course

Related Courses
C++ Training (4 Courses, 5 Projects, 4 Quizzes)Java Training (40 Courses, 29 Projects, 4 Quizzes)

3. Digit Folding Method

In this method the element to be placed in the table uh is sing hash key, which is obtained by dividing the elements into various parts and then combine the parts by performing some simple mathematical operations.

Element to be placed are 23576623, 34687734.

  • hash (key) = 235+766+23 = 1024
  • hash key) = 34+68+77+34 = 213

In these types of hashing suppose we have numbers from 1- 100 and size of hash table =10. Elements = 23, 12, 32

Hash (key) = 23 % 10 = 3;

Hash (key) = 12 % 10 = 2;

Hash (key) = 32 % 10 = 2;

From the above example notice that both elements 12 and 32 points to 2nd place in the table, where it is not possible to write both at the same place such problem is known as a collision. To avoid this kind of problems there are some techniques of hash functions that can be used.

Types of Collision Resolution Techniques

Let us discuss the types of collision resolution techniques:

1. Chaining

In this method as the name suggests it provides a chain of boxes for the record in the table having two entries of elements. So whenever such collisions occur then the boxes act as a linked list will be formed.

Example: 23, 12, 32 with table size 10.

Hash (key) = 23 % 10 = 3;

Hash (key) = 12 % 10 =2;

Hash (key) = 32 % 10 =2;

Chaining

2. Open Addressing

  • Linear Probing

This is another method for solving collision problems. As the name says whenever a collision occurs then two elements should be placed on the same entry in the table, but by this method, we can search for next empty space or entry in the table and place the second element. This can again lead to another problem; if we do not find any empty entry in the table then it leads to clustering. Thus this is known as a clustering problem, which can be solved by the following method.

Example: 23, 12, 32 with table size 10

Hash (key) = 23 % 10 = 3;

Hash (key) = 12 % 10 =2;

Hash (key) = 32 % 10 =2;

Open addressing

In this diagram 12 and 32 can be placed in the same entry with index 2 but by this method, they are placed linearly.

  • Quadratic probing

This method is a resolution for the clustering problem during linear probing. In this method the hash function with hash key is calculated as hash (key) = (hash (key) + x * x) % size of the table (where x =0, 1, 2 …).

Example: 23, 12, 32 with table size 10

Hash (key) = 23 % 10 = 3;

Hash (key) = 12 % 10 =2;

Hash (key) = 32 % 10 =2;

hashing function in C.3

In this, we can see that 23 and 12 can be placed easily but 32 cannot as again 12 and 32 shares the same entry with the same index in the table, as per this method hash (key) = (32 + 1*1) % 10 = 3. But in this case table entry with index 3 is placed with 23 so we have to increment x value by 1. Hash (key) = (32 + 2 * 2) % 10 = 6. So we now can place 32 in the entry with index 6 in the table.

  • Double hashing

This method we have to calculate 2 hash functions to resolve the collision problem. The first is calculated using a simple division method. Second has to satisfy two rules; it must not be equal to 0 and entries must be probed.

  • 1 (key) = key % size of the table.
  • 2 (key) = p – (key mod p), where p is prime numbers < size of the table.

Example: 23, 12, 32 with table size 10

Hash (key) = 23 % 10 = 3;

Hash (key) = 12 % 10 =2;

Hash (key) = 32 % 10 =2;

Hashing function in C.4

In this again the element 32 can be placed using hash2 (key) = 5 – (32 % 5) = 3. So 32 can be placed at index 5 in the table which is empty as we have to jump 3 entries to place it.

Conclusion

 Hashing is one of the important techniques in terms of searching data provided with very efficient and quick methods using hash function and hash tables. Each element can be searched and placed using different hashing methods. This technique is very faster than any other data structure in terms of time coefficient.

Recommended Articles

This is a guide to the Hashing function in C. Here we discussed brief overview, with types of Hash function in C and collision resolution techniques in detail. You can also go through our other suggested articles to learn more–

  1. Hashing in DBMS
  2. Encryption process
  3. Hashing Function in Java
  4. Hashing Function in PHP

C Programming Training (3 Courses, 5 Project)

3 Online Courses

5 Hands-on Projects

34+ Hours

Verifiable Certificate of Completion

Lifetime Access

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
C Programming Tutorial
  • Function
    • Math Functions in C
    • Hashing Function in C
    • Recursive Function in C
    • Power Function in C
    • fputs in C
    • C puts() Function
    • fprintf() in C
    • fseek() in C
    • Stderr in C
    • ASCII Value in C
    • strcat() in C
    • Inline Function in C
    • sizeof() in C
    • Function Prototype in C
    • C ftell()
  • Basic
    • Introduction to C
    • What is C
    • Career in C Programming
    • Advantages of C
    • How to Install C
    • Best C Compilers
    • Data Types in C
    • Variables in C
    • C Keywords
    • C Command
    • Command Line Arguments in C
    • C Literals
    • Constants in C
    • Unsigned Int in C
    • String in C
  • Pointers
    • Pointers in C
    • Null pointer in C
    • Function Pointer in C
    • Double Pointer in C
    • Void Pointer in C
    • Const Pointer in C
    • Dangling Pointers in C
    • Pointer Arithmetic in C
  • Operators
    • C Operators
    • Arithmetic Operators in C
    • Relational Operators in C
    • Assignment Operators in C
    • Logical Operators in C
    • Conditional Operator in C
    • Modulus Operator in C
    • Ternary Operator in C
    • Address Operator in C
    • Unary Operator in C
    • Operators Precedence in C
    • Left Shift Operator in C
  • Control Statement
    • Control Statements in C
    • If Statement in C
    • If-else Statement in C
    • Else if Statement in C
    • Nested if Statement in C
    • #else in C
    • Structure Padding in C
    • Nested Structure in C
    • Continue Statement in C
    • Break Statement in C
    • Switch Statement in C
    • Goto Statement in C
  • Loops
    • Loops in C
    • For Loop in C
    • While Loop in C
    • Do While Loop in C
    • Nested Loop in C
    • Infinite Loop in C 
  • Array
    • Arrays in C Programming
    • 2-D Arrays in C
    • 3D Arrays in C
    • Multidimensional Array in C
    • Array Functions in C
    • Strings Array in C
  • Sorting
    • Sorting in C
    • Heap Sort in C
  • Advanced
    • Constructor in C
    • Encapsulation in C
    • C Storage Classes
    • Static Keyword in C
    • File Handling in C
    • Queue in C
    • Hexadecimal in C 
    • typedef in C
    • Memory Allocation in C
    • Linked List in C
    • Volatile in C
    • Tokens in C
    • Expression in C
    • Regular Expression in C
    • Error Handling in C
    • Types of Errors in C
    • Preprocessor in C
    • Preprocessor Directives in C
    • fscanf() in C
    • #Pragma in C
    • #ifndef in C
    • #undef in C
    • Macros in C
  • C programs
    • Patterns in C Programming
    • Star Patterns in C
    • Number Patterns in C
    • Swapping in C
    • Reverse Number in C
    • Palindrome in C Program
    • Factorial in C
    • Fibonacci Series in C
    • Square Root in C
    • Random Number Generator in C
    • Prime Numbers in C
    • Escape Sequence in C
    • Reverse String in C
    • Leap Year Program in C
    • Anagram Program in C
    • Strong Number in C
    • String Concatenation in C
    • C Programming Matrix Multiplication
    • Decimal to Octal in C
    • Expression Evaluation in C
    • Decimal to Hexadecimal in C
  • Interview question
    • C Programming Interview Questions

Related Courses

C Programming Training Course

C++ Training Course

Java Training Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Java Tutorials
  • Python Tutorials
  • All Tutorials
Certification Courses
  • All Courses
  • Software Development Course - All in One Bundle
  • Become a Python Developer
  • Java Course
  • Become a Selenium Automation Tester
  • Become an IoT Developer
  • ASP.NET Course
  • VB.NET Course
  • PHP Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

Special Offer - C Programming Training (3 Courses, 5 Project) Learn More