Scribd Logo
Upload

Welcome to Scribd!

  • 10 views

    20C23027 Prac4

    Uploaded by

    purvivaghela2003
    The document discusses implementing a hash table using separate chaining in Python. It explains the concepts of hashing, hash functions, and collision handling using chaining. The Python code provided implements a hash table as a nested list and uses chaining to handle collisions by storing multiple values in each hash table slot.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    20C23027 Prac4

    Uploaded by

    purvivaghela2003
    10 views4 pages
    The document discusses implementing a hash table using separate chaining in Python. It explains the concepts of hashing, hash functions, and collision handling using chaining. The Python code provided implements a hash table as a nested list and uses chaining to handle collisions by storing multiple values in each hash table slot.

    Original Description:

    Practical

    Original Title

    20C23027_Prac4

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses implementing a hash table using separate chaining in Python. It explains the concepts of hashing, hash functions, and collision handling using chaining. The Python code provided implements a hash table as a nested list and uses chaining to handle collisions by storing multiple values in each hash table slot.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    10 views4 pages

    20C23027 Prac4

    Uploaded by

    purvivaghela2003
    The document discusses implementing a hash table using separate chaining in Python. It explains the concepts of hashing, hash functions, and collision handling using chaining. The Python code provided implements a hash table as a nested list and uses chaining to handle collisions by storing multiple values in each hash table slot.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 4

    ITM SLS Baroda University

    School of Computer Science Engineering & Technology


    BTech Semester IV AI and CS and
    BTech Semester IV CSE and IT
    Batch 2020-24
    Data Structure & Algorithm II Practical Lab Journal

    Practical 04
    Aim: Python Implementation of Hash Table using Separate Chaining
    Theory:

    Hash table is a data structure that is used to store a large amount of data, which can be accessed in
    O(1) time by operations such as search, insert and delete.

    The various applications of hashing are:


     Indexing in database
     Cryptography
     Symbol tables in compilers/interpreters
     Dictionaries, caches etc

    Concept of hashing, hash table and hash function:

    Hashing is an important data structure which is designed to use a special function called the Hash
    Function which is used to map a given value with a particular key for faster access of elements. The
    efficiency of mapping depends on the efficiency of the hash function used.

    Example:
    h(large_value) = large_value % m
    Here h() is the required hash function and ‘m’ is the size of the hash table. For large values, hash
    functions produce value in a given range.

    How hash function works?


    1. It should always map large keys to small keys.
    2. It should always generate values between 0 to m-1 where m is the size of the hash table.
    3. It should uniformly distribute large keys into hash table slots.

    1|Page 2 0 C 2 3 0 2 7 – P u r v i Va g h e l a
    ITM SLS Baroda University
    School of Computer Science Engineering & Technology
    BTech Semester IV AI and CS and
    BTech Semester IV CSE and IT
    Batch 2020-24
    Data Structure & Algorithm II Practical Lab Journal

    Collision Handling:

    If we know the keys beforehand, then we have can have perfect hashing. In perfect hashing, we do
    not have any collisions. However, If we do not know the keys, then we can use the following
    methods to avoid collisions:

     Chaining
     Open Addressing (Linear Probing, Quadratic Probing, Double Hashing)

    Chaining

    While hashing, the hashing function may lead to a collision that is two or more keys are mapped to
    the same value. Chain hashing avoids collision. The idea is to make each cell of hash table point to
    a linked list of records that have same hash function value.

    Note: In Linear Probing, whenever a collision occurs, we probe to the next empty slot. While in
    Quadratic Probing, whenever a collision occurs, we probe for i^2th slot in the ith iteration and we
    keep probing until an empty slot in the hashtable is found.

    The performance of hashing is evaluated on the basis that each key is equally likely to be hashed for
    any slot of the hash table.

    m = Length of Hash Table


    n = Total keys to be inserted in the hash table

    2|Page 2 0 C 2 3 0 2 7 – P u r v i Va g h e l a
    ITM SLS Baroda University
    School of Computer Science Engineering & Technology
    BTech Semester IV AI and CS and
    BTech Semester IV CSE and IT
    Batch 2020-24
    Data Structure & Algorithm II Practical Lab Journal

    Load factor lf = n/m


    Expected time to search = O(1 +lf )
    Expected time to insert/delete = O(1 + lf)

    The time complexity of search insert and delete is


    O(1) if lf is O(1)

    Python Code for Hashing using Chaining

    # Function to display hashtable


    def display_hash(hashTable):

    for i in range(len(hashTable)):
    print(i, end = " ")

    for j in hashTable[i]:
    print("-->", end = " ")
    print(j, end = " ")

    print()

    # Creating Hashtable as
    # a nested list.
    HashTable = [[] for _ in range(10)]

    # Hashing Function to return


    # key for every value.
    def Hashing(keyvalue):
    return keyvalue % len(HashTable)

    # Insert Function to add


    # values to the hash table
    def insert(Hashtable, keyvalue, value):

    hash_key = Hashing(keyvalue)
    Hashtable[hash_key].append(value)

    # Driver Code
    insert(HashTable, 10, 'Allahabad')
    insert(HashTable, 25, 'Mumbai')
    insert(HashTable, 20, 'Mathura')
    insert(HashTable, 9, 'Delhi')

    3|Page 2 0 C 2 3 0 2 7 – P u r v i Va g h e l a
    ITM SLS Baroda University
    School of Computer Science Engineering & Technology
    BTech Semester IV AI and CS and
    BTech Semester IV CSE and IT
    Batch 2020-24
    Data Structure & Algorithm II Practical Lab Journal

    insert(HashTable, 21, 'Punjab')


    insert(HashTable, 21, 'Noida')

    display_hash (HashTable)

    Output:

    Advantages
    1. Separate Chaining is one of the simplest methods to implement and understand.
    2. We can add any number of elements to the chain.
    3. It is frequently used when we don't know about the number of elements and the number of
    keys that can be inserted or deleted.
    Disadvantages
    1. The keys in the hash table are not evenly distributed.
    2. Some amount of wastage of space occurs.
    3. The complexity of searching becomes O(n) in the worst case when the chain becomes long.

    4|Page 2 0 C 2 3 0 2 7 – P u r v i Va g h e l a

    You might also like