EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Hash Table in Data Structure
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Hash Table in Data Structure

Hash Table in Data Structure

Introduction to Hash Table

Hash Table in Data Structure, Hash Table is the table that stores all the values of the hash code used while storing the keys and element data values using hashing mechanism. The hash table stores hash codes which are generated by using the hash function. Hashing is the mechanism that helps to identify all the objects uniquely within the set of groups of objects.

This type of system is also used in day-to-day life like when assigning the ids to employees, books or roll numbers to students so that it is easy to identify each of them individually in a better way. In all these examples the unique key that is used for identification is called as hash codes, hash values, hash or hash sums when we are implementing hashing by using hash tables.

In this article, we will see how the hash table proves to be helpful in implementing hashing and also see one example to study how hashing can be implemented.

Working of Hash Table

Working of hash table are given below:

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

  • Indexing of the array makes the data access very fast, hence, the hash table internally makes the use of array to store all the values while the unique indexing created by using hash tables acts as the indexing of the array. When we know exactly where which value is stored using its key, it becomes very easy and fast to access it.
  • This data structure stores all the values of the array or simply any other list or group of elements along with its keys. This keys act as a index that is useful while referring and storing the data in hash tables. Whenever the key or index becomes very big, the hash code reduces the key length by using a hash function.
  • The hash function should be chosen appropriately depending on the factors that the resulting storage of elements should be distributed uniformly across the hash table. This makes sure that there is no clustering of data at a single place in hash table. Also, the hash function should be very easy and simple for calculation as increasing its complexity will increase the storage requirement as well as the computations required.
  • One should also make sure to take the at the most collision prevention technique usage as it is common that even though a good hash function is chosen for hashing it may result more than one value is mapped to the same hash value. There are many collision detection and resolution techniques followed such as open hashing also known as separate chaining, linear probing or closed hashing, quadratic probing or double hashing.

Applications of Hash Tables and Hashing Technique

Many of the algorithms internally make use of hash tables to make computing faster. The hashing is used in various ways such as –

  • Database Indexing: The disk-based data structures involve the usage of hash tables. For example, dbm.
  • Associative arrays: in-memory tables implementation involves the usage of hash tables for storing complicated or arbitrary strings as index implementing associative arrays in it.
  • Caches:  auxiliary data tables implement hash tables which increase the speed of accessing the data.
  • Object Representation: The programming languages that are dynamic in nature such as Perl, ruby, JavaScript or python make the use of hash tables for storing objects.

Implementation of Hash Table in Data Structure

There are three operations which can be carried out on the hash table which are insertion, deletion and searching a particular value of the hash table. Let us have a look at how the hash table can be implemented in C programming language with the help of an example –

Code:

#include <string.h>
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define LENGTH 20
struct keyValuePair {
int value;
int key;
};
struct keyValuePair* hashArray[LENGTH];
struct keyValuePair* temporarykeyValuePair;
struct keyValuePair* item;
int generateHashCode(int key) {
return key % LENGTH;
}
struct keyValuePair *search(int key) {
//retrieve the hash value
int hashIndex = generateHashCode(key);
//shift the value to an array until it is empty
while(hashArray[hashIndex] != NULL) {
if(hashArray[hashIndex]->key == key)
return hashArray[hashIndex];
//move to next value
++hashIndex;
//Table is wrapped
hashIndex %= LENGTH;
}
return NULL;
}
void insertItem(int key,int value) {
struct keyValuePair *item = (struct keyValuePair*) malloc(sizeof(struct keyValuePair));
item->value= value;
item->key = key;
//retrieve hash value
int hashIndex = generateHashCode(key);
//move in array until an empty or deleteItemd cell
while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= LENGTH;
}
hashArray[hashIndex] = item;
}
struct keyValuePair* deleteItem(struct keyValuePair* item) {
int key = item->key;
//get the hash
int hashIndex = generateHashCode(key);
//shift the array until it is completely vacant
while(hashArray[hashIndex] != NULL) {
if(hashArray[hashIndex]->key == key) {
struct keyValuePair* temp = hashArray[hashIndex];
//give the value of the temporary dummy item at the place where the element was deleteItemd
hashArray[hashIndex] = temporarykeyValuePair;
return temp;
}
//move to next item
++hashIndex;
//wrap around the table
hashIndex %= LENGTH;
}
return NULL;
}
void display() {
int i = 0;
for(i = 0; i<LENGTH; i++) {
if(hashArray[i] != NULL)
printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->value);
else
printf(" - ");
}
printf("\n");
}
int main() {
temporarykeyValuePair = (struct keyValuePair*) malloc(sizeof(struct keyValuePair));
temporarykeyValuePair->value= -1;
temporarykeyValuePair->key = -1;
insertItem(1, 20);
insertItem(2, 70);
insertItem(42, 80);
insertItem(4, 25);
insertItem(12, 44);
insertItem(14, 32);
insertItem(17, 11);
insertItem(13, 78);
insertItem(37, 97);
display();
item = search(37);
if(item != NULL) {
printf("keyValuePair found: %d\n", item->value);
} else {
printf("keyValuePair not found\n");
}
deleteItem(item);
item = search(37);
if(item != NULL) {
printf("The hash keys and its corresponding values are : %d\n", item->value);
} else {
printf("Key Value Pair not found\n");
}
}

The output of the execution of above program is as shown below displaying all the contents of the hash table and also when we perform the deletion operation the message displayed shows that the key value pair was not found.

1

Conclusion

Hash tables are used to implement hashing technique for uniquely identifying each of the value with the help of key. All this key value pairs are stored in the array where the elements stored in it are values and the indexes of the array are the key. When the key length becomes very big, it is reduced by making the use of hash function. This results in uniform and even distribution of data across the hash table.

Recommended Articles

This is a guide to Hash Table in Data Structure. Here we also discuss the introduction and applications of hash tables along with example. You may also have a look at the following articles to learn more –

  1. Hash Table in C
  2. Hashtable in Java
  3. DB2 alter table
  4. C++ Hash Table
Popular Course in this category
Data Scientist Training (85 Courses, 67+ Projects)
  85 Online Courses |  67 Hands-on Projects |  660+ Hours |  Verifiable Certificate of Completion
4.8
Price

View Course

Related Courses

All in One Data Science Bundle (360+ Courses, 50+ projects)4.9
Oracle DBA Database Management System Training (2 Courses)4.8
SQL Training Program (7 Courses, 8+ Projects)4.7
0 Shares
Share
Tweet
Share
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

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

EDUCBA
Free Data Science Course

SPSS, Data visualization with Python, Matplotlib Library, Seaborn Package

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

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

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

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

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

By signing up, you agree to our Terms of Use and Privacy Policy.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

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

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more