Prompt Title: ADS LAB 8

Human: TITLE: Implementation of direct access file using Hashing: linear probing with replacement and without replacement PROBLEM STATEMENT: Implement Direct access file using hashing (linear probing with and without replacement) perform following operations on it a) Create Database b) Display Database c) Add a record d) Search a record e) Modify a record OBJECTIVE: 1. To study hashing techniques 2. To implement different hashing techniques 3. To study and implement linear probing with & without replacement 4. To study how hashing can be used to model real world problems THEORY: //To be Written by Students // Write theory by elaborating below points Write in brief about ● What is Hashing? Compare hashing with other searching techniques. ● Write different hash functions ● Explain hash collision resolution techniques. CET2001B IMPLEMENTATION: ● PLATFORM: o 64-bit Open source Linux or its derivatives. o Open Source C++ Programming tool like g++/Eclipse Editor. ● TEST CONDITIONS:- 1. Input min 10 elements. 2. Display collision with replacement and without replacement. ● PSEUDO CODE: //To be Written by Students Write pseudo code for linear probing with replacement and without replacement. TIME COMPLEXITY: //To be Written by Students Find out time complexity of linear probing method ● CONCLUSION: Thus, we have implemented linear probing with and without replacement. ● FAQs //To be Written by Students 1. Write different types of hash functions. 2. Explain chaining with & without replacement with example. 3. Explain quadratic probing with example

ChatGPT:

THEORY:

Hashing is a technique used in computer programming to quickly locate a specific record or element in a large set of data. It involves applying a hash function to a key, which is typically a unique identifier for the record or element, to generate a hash value. The hash value is used as an index in an array or a hash table to directly access the record or element, allowing for fast retrieval.

Compared to other searching techniques, such as linear search or binary search, hashing can provide faster and more efficient retrieval of data, especially when dealing with large datasets. Hashing allows for constant-time average-case complexity for retrieval, insertion, and deletion operations, making it ideal for applications that require fast data access, such as databases or search engines.

Different hash functions can be used in hashing, depending on the requirements of the application. Some common types of hash functions include:

1. Division Hashing: This involves dividing the key by a prime number and taking the remainder as the hash value.
2. Multiplication Hashing: This involves multiplying the key by a constant value between 0 and 1, and then taking the fractional part of the result as the hash value.
3. XOR Hashing: This involves performing an XOR operation on the bytes of the key to generate the hash value.

Hash collision occurs when two or more keys produce the same hash value. There are several techniques to resolve hash collisions, including:

1. Linear Probing: This involves finding the next available slot in the array if the current slot is occupied. If the next slot is also occupied, the search continues until an empty slot is found.
2. Quadratic Probing: This involves finding the next available slot in the array using a quadratic function of the hash value, instead of a linear increment.
3. Chaining: This involves storing multiple records with the same hash value in the same slot using a linked list or another data structure.

PSEUDO CODE:

Linear Probing with Replacement:

vbnetCopy code
initialize an array with null values
while performing operations on the database:
    take input key and record
    calculate hash value using hash function
    if the slot at the hash value is empty:
        store the record at the hash value
    else:
        find the next available slot using linear probing
        if an empty slot is found:
            store the record at the empty slot
        else:
            if replacement is allowed:
                replace the existing record with the new record
            else:
                display an error message indicating that the database is full

Linear Probing without Replacement:

vbnetCopy code
initialize an array with null values
initialize a flag array to keep track of occupied slots
while performing operations on the database:
    take input key and record
    calculate hash value using hash function
    if the slot at the hash value is empty:
        if the flag at the hash value is not set:
            store the record at the hash value
            set the flag at the hash value
        else:
            find the next available slot using linear probing
            if an empty slot is found:
                store the record at the empty slot
                set the flag at the empty slot
            else:
                display an error message indicating that the database is full
    else:
        display an error message indicating that the slot is already occupied

TIME COMPLEXITY:

The time complexity of linear probing depends on the load factor, which is the ratio of the number of occupied slots to the total number of slots in the array. In the worst case, when all the slots are occupied and the load factor is 1, the time complexity of linear probing can degrade to O(n), where n is the number of records in the database. However, on average, with a low load factor,

Human: ● FAQs //To be Written by Students 1. Write different types of hash functions. 2. Explain chaining with & without replacement with example. 3. Explain quadratic probing with examp

ChatGPT:

FAQs:

1. Different types of hash functions:

• Division Method: In this method, the key is divided by a constant value, and the remainder is used as the hash value.
• Multiplication Method: In this method, the key is multiplied by a constant value between 0 and 1, and the fractional part of the result is used as the hash value.
• Folding Method: In this method, the key is divided into equal-sized parts, and these parts are summed up to get the hash value.
• Mid-Square Method: In this method, the key is squared, and the middle digits of the result are used as the hash value.

2. Chaining with & without replacement with example:

• Chaining with replacement: In this method, each slot in the hash table contains a linked list of records. When a collision occurs, the new record is appended to the end of the linked list in the corresponding slot. This method allows multiple records to be stored in the same slot, but it requires additional memory for the linked lists.

Example: Let's say we have a hash table with 5 slots, and we want to insert records with keys 10, 15, 20, and 25. Using the hash function, the keys 10 and 20 both hash to slot 1. So, the hash table would look like:

Slot 1: 10 -> 20 -> NULL Slot 2: 15 -> NULL Slot 3: NULL Slot 4: 25 -> NULL Slot 5: NULL

• Chaining without replacement: In this method, each slot in the hash table can only contain one record. When a collision occurs, the new record replaces the existing record in the slot. This method does not require additional memory for linked lists, but it can result in data loss if multiple records hash to the same slot.

Example: Using the same hash table with 5 slots, let's say we want to insert records with keys 10, 15, 20, and 25. Using the hash function, the keys 10 and 20 both hash to slot 1. So, the hash table would look like:

Slot 1: 20 Slot 2: 15 Slot 3: NULL Slot 4: 25 Slot 5: NULL

3. Quadratic Probing with example: Quadratic probing is a method to resolve hash collisions where the hash value is incremented by a quadratic function of the probing sequence.

Example: Let's say we have a hash table with 7 slots, and we want to insert records with keys 10, 15, 20, and 25. Using the hash function, the keys 10 and 20 both hash to slot 1. Since slot 1 is already occupied, we start quadratic probing with a probing sequence of 1^2, 2^2, 3^2, and so on.

• Inserting 10: Slot 1: 10 Slot 2: NULL Slot 3: NULL Slot 4: NULL Slot 5: NULL Slot 6: NULL Slot 7: NULL

• Inserting 15: Slot 1: 10 Slot 2: 15 Slot 3: NULL Slot 4: NULL Slot 5: NULL Slot 6: NULL Slot 7: NULL

• Inserting 20: Slot 1: 10 Slot 2: 15 Slot 3: 20 Slot 4: NULL Slot 5: NULL Slot 6: NULL Slot 7: NULL

• Inserting 25: Slot 1: 10