Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort

Hashing

Hashing: Hashing is a process in which a large amount of data is mapped to a small table with the help of hashing function. It is a searching technique.

Hash table

We can understand the hash table better based on the following points:

  1. In a data structure, the hash table is used to store key-value pairs.
  2. The data items are stored in an array format in it, where each data value has its unique index value.
  3. It is a collection of stored data items that you can easily search later.
  4. In this, the hash function is used to compute the index of the array, from which you can find your desired value.
  5. It has a list of the array where each list is called a bucket.
  6. It contains the value based on the key.
  7. The hash table is used to implement the map interface and extend the dictionary class.
  8. The hash table is a synchronized table, and it contains unique elements only.
Hashing
  • The figure above shows the hash table whose size is n = 10. Each position of the hash table is called a slot. This hash table has not contained any item, so each slot is empty.

Basic operations

There is the following type of basic operation in the hash table:

  1. Search operation
  2. Delete operation
  3. Insert operation

Search operation: The search operation is used to search a particular value in a hash table.

Delete operation: The delete operation is used to delete a particular value in a hash table.

Insert operation: The Insert operation is used to add particular value in a hash table.

Hash function

The hash function is a type of function that is applied to a key from which an integer is obtained. This integer is used as the address of the hash table. This integer is called a hash key.

Type of hash functions

There are various types of hash functions in the data structure:

  1. Mid Square Hash Function
  2. Division Hash Function

Division hash function

In this function, the hash function depends on the remainder of the division. If the list size is a prime number, there is less collision.

The formula of division hash function is h(k) = k mod n

Where k is key, and n is list size.

For example: Suppose we have this record (101, 103, 107, 109), and the table size is 10.

Solution: Record is (101, 103, 107, 109)

                Table size is 10.

                Put value in the formula h(k) = k mod n

                                        1 = 101 mod 10

                                        3 = 103 mod 10

                                        7 = 107 mod 10

                                        9 = 109 mod 10

Hashing

Mid square hash function

In this function, firstly hash function key is squared, and then the middle part of the square is selected as the index.

For example: Suppose we have this record 96.

                        96 = 962 = 9216                              // middle part of the square is index address    

                        The address of index is 21 

Characteristics of a good hash function

To get a good hashing mechanism, we need a good hash function. Therefore, we describe below the characteristic of a good hash function:

  1. The hash function should generate different hash values ??for the same type of string.
  2. A good hash function reduces the chance of collisions.
  3. It should be easy to compute.
  4. The hash function is perfect when it uses all input data.
  5. The hash function should generate such keys that are easy to distribute.



ADVERTISEMENT
ADVERTISEMENT