Hashing Techniques

 In hash table data structures, several hashing techniques are commonly used. Here are some of the most popular ones:

  1. Division Hashing:

    • Uses the modulo operation to obtain a hash code. The formula is hash_code = key % table_size.
    • Simple and computationally efficient.
    • Prone to clustering if keys have a pattern that aligns with the table size.

  2. Multiplication Hashing:

    • Involves multiplying the key by a constant A in the range (0, 1), extracting the fractional part, and then multiplying it by the size of the hash table.
    • Formula: hash_code = int(table_size * ((key * A) % 1)).
    • Provides a more uniform distribution compared to division hashing.

  3. Universal Hashing:

    • Uses a family of hash functions, and a random hash function is selected for each instance of the hash table.
    • Reduces the likelihood of collisions, even for worst-case key distributions.
    • Achieves good average-case performance.

  4. Double Hashing:

    • Involves using a secondary hash function to resolve collisions.
    • The formula is hash_code = (hash1(key) + i * hash2(key)) % table_size, where i is the number of collision resolution attempts.
    • Effective in minimizing clustering and providing good distribution.

  5. Cuckoo Hashing:

    • Uses multiple hash functions and two or more hash tables.
    • Each key is assigned to one of the hash tables based on multiple hash functions.
    • If a collision occurs, the existing key is moved to the other hash table.
    • Repeats the process until there are no collisions.
    • Effective for resolving collisions with a constant worst-case lookup time.

  6. Perfect Hashing:

    • Aims to eliminate collisions entirely by designing a hash function that guarantees no collisions for a specific set of keys.
    • Involves two levels of hashing: the first level hashes keys into buckets, and within each bucket, a second-level hash function is used.
    • Ideal for situations where the set of keys is fixed.

  7. Quadratic Probing:

    • A form of open addressing that resolves collisions by incrementing the probe sequence quadratically.
    • The formula is hash_code = (hash1(key) + c1 * i + c2 * i^2) % table_size, where c1 and c2 are constants.
    • Helps avoid clustering and provides good distribution.

  8. Chaining (Separate Chaining):

    • Each bucket in the hash table contains a linked list of key-value pairs.
    • Collisions are resolved by appending key-value pairs to the linked list at the corresponding bucket.
    • Provides a simple and effective way to handle collisions.

These hashing techniques vary in their approach to handling collisions and distributing keys. The choice of a hashing technique depends on factors such as the nature of the data, expected workload, and performance requirements for specific applications.

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