Hash Table

A hash table is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. This provides a data structure that can be searched in O(1) time. Each bucket can consists of S slots. Each bucket can hold only one record if it contains one slot.

Example: Lets consider a hash table with 26 buckets and 2 slots. Lets consider a hash function F(X) which maps all identifiers X based on the first character in X.
The identifiers A,A2,D,GA,G are hashed into the corresponding buckets/slots as shown below.

Here are the key components and characteristics of a hash table:
    Hash Function:
    A hash function takes a key as input and produces a hash code, which is used as an index to access the corresponding value in the hash table.
    The hash function should be deterministic (same key should always produce the same hash code) and provide a uniform distribution of hash codes to minimize collisions.

    Array or Bucket Array:
  1. The hash table is typically implemented as an array of buckets or slots, where each bucket can store one or more key-value pairs in slots.
    The array size is usually determined based on the expected number of keys and the desired efficiency of the hash table.

  3. Collision Resolution:
    • Collisions occur when two different keys hash to the same index. There are various techniques to handle collisions:
        Open Addressing: In this approach, when a collision occurs, the algorithm looks for the next available slot in the array (e.g., linear probing, quadratic probing, double hashing).
        Separate Chaining: Each bucket contains a linked list, and when a collision occurs, new key-value pairs are appended to the linked list at that bucket.

  6. Load Factor:
  7. The load factor is the ratio of the number of stored elements to the size of the array. It influences the efficiency and performance of the hash table.
    A higher load factor increases the likelihood of collisions but reduces memory usage, while a lower load factor increases memory usage but reduces collisions.

    8. Time Complexity:
    When the hash function is well-designed and collisions are minimized, hash tables can provide constant-time average-case complexity for basic operations like search, insert, and delete.


    2. Example:
    A hash table is a collection of items which are stored in such a way as to make it easy to find them later. Each position of the hash table, often called a slot, can hold an item and is named by an integer value starting at 0. For example, we will have a slot named 0, a slot named 1, a slot named 2, and so on.
Figure shows a hash table of size m=11. In other words, there are m slots in the table, named 0 through 10.
The mapping between an item and the slot where that item belongs in the hash table is called the hash function. The hash function will take any item in the collection and return an integer in the range of slot names, between 0 and m-1. Assume that we have the set of integer items 54, 26, 93, 17, 77, and 31. Our first hash function, sometimes referred to as the “remainder method,” simply takes an item and divides it by the table size, returning the remainder as its hash value (ℎ(k)=k%11). Note that this remainder method (modulo arithmetic) will typically be present in some form in all hash functions, since the result must be in the range of slot names.


Item  

                                                                   Hash Value

54

10

26

4

93

5

17

6

77

0

31

9





Once the hash values have been computed, we can insert each item into the hash table at the designated position as shown below. Note that 6 of the 11 slots are now occupied. This is referred to as the load factor, and is commonly denoted by lambda=Number of items/Table size
For this example, lambda=6/11.

Now when we want to search for an item, we simply use the hash function to compute the slot name for the item and then check the hash table to see if it is present. This searching operation is O(1), since a constant amount of time is required to compute the hash value and then index the hash table at that location. If everything is where it should be, we have found a constant time search algorithm.

You can probably already see that this technique is going to work only if each item maps to a unique location in the hash table. For example, if the item 44 had been the next item in our collection, it would have a hash value of 0 (44%11==0). Since 77 also had a hash value of 0, we would have a problem. According to the hash function, two or more items would need to be in the same slot. This is referred to as a collision (it may also be called a “clash”). Clearly, collisions create a problem for the hashing



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