Hashing

Hashing is a technique used in data structures to map data of arbitrary size to fixed-size values, typically for the purpose of creating a faster and more efficient data retrieval system. The concept is based on a hash function, which takes an input (or 'key') and produces a fixed-size string of characters, which is usually a hash code. The hash code is then used to index into a data structure (usually an array or a hash table) where the values are stored.

Let's go through the key components and concepts related to hashing:

Hash Function:

A hash function is a mathematical function that takes an input (or 'key') and produces a fixed-size string of characters, which is the hash code. The goal is to distribute the keys uniformly across the range of possible hash codes.

Key properties of a good hash function:

  1. Deterministic: For the same input, the hash function should always produce the same hash code.
  2. Efficient: The hash function should be computationally efficient to calculate.
  3. Uniform Distribution: The hash function should distribute keys as uniformly as possible across the hash code space to minimize collisions.

Hash Code:

The output of the hash function is called the hash code. It is used as an index to access the corresponding data in the data structure.

Collision:

A collision occurs when two different keys hash to the same hash code. Collisions are inevitable due to the finite range of hash codes and the potentially infinite number of keys. Handling collisions is a crucial aspect of designing a good hashing system.

Collision Resolution Techniques:

  1. Open Addressing: In open addressing, when a collision occurs, the algorithm looks for the next available slot in the hash table. This can be done using various methods such as linear probing, quadratic probing, or double hashing.

  2. Separate Chaining: In separate chaining, each slot in the hash table contains a linked list. When a collision occurs, the new key is simply appended to the linked list at that slot.

Applications of Hashing:

  1. Data Retrieval: Hashing is used in data structures like hash tables, where it provides constant time average-case complexity for search, insert, and delete operations.

  2. Cryptography: Hash functions are used in various cryptographic applications, such as digital signatures and checksums.

  3. Load Balancing: Hashing can be used in load balancing algorithms to distribute data or tasks evenly across multiple nodes or servers.

  4. Caching: Hash functions are used in caching mechanisms to quickly locate cached data.

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more