# Hashing Lab## Instructions1. Given the following key values, show what the data structures would look like after insertions: - Key values: 27, 53, 13, 10, 138, 109, 49, 174, 26, 24 - No preprocessing necessary: \(D_k = \text{key}\)### a. Linear Array of 10 Elements- **Using Division Hashing and the Linear-Quotient Collision Path Algorithm** **Parameters:** - \(N = 13\) - \(4k+3 \text{ prime } = 19\) **Algorithm:** **LOHashing:** 1. \(i_p = D_k \% N\) 2. \(q = D_k / N\) - If \((q \% N) \neq 0\), then - \(\text{offset} = q\) - Else - \(\text{offset} = 4k+3 \text{ prime}\) 3. While collisions occur: - \(i_p' = (i_p + \text{offset}) \% N\) 4. Set \(\text{Array}[i_p'] = \text{key}\) **Array:** ``` 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | ```### b. Bucket Hashing of 10 Elements (N=10)- \(i_p = (D_k) \% N\) **Array:** ``` 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ``` ### Explanation- The diagram illustrates two types of hashing for storing the key values in arrays.- **Array a:** Uses linear array hashing with a complex collision resolution strategy, combining division hashing and a calculated offset.- **Array b:** Demonstrates simple bucket hashing where the **Exercise 2: Complete the Table Based on Exercise 1**The table below is designed to help you understand the number of comparisons required to retrieve elements from a data structure, based on a given key. This is part of an exercise focusing on hash tables and the differences between collision resolution strategies: linear probing and separate chaining with buckets.**Number of Comparisons to Retrieve This Element**| Key | Linear Array - (Length of Collision Path +1) | Buckets - (# of Elements in Linked List Compared) ||-----|---------------------------------------------|--------------------------------------------------|| 53 | | || 138 | | || 109 | | || 49 | | || 174 | | || 26 | | |- *Linear Array Column*: Represents the number of comparisons needed using linear probing. This is calculated as the length of the collision path plus one.- *Buckets Column*: Indicates the number of elements compared within a linked list when using separate chaining in hash tables.

1. For the given question : (a) Linear array status:

Hashing Lab 1. Given the following key values, show what the data structures would look like after insertions 27 53 13 10 138 109 49 174 26 24 (no preprocessing necessary: P= key) Linear and the linear-quotient collision path algorithm N= 13, 4k+3 prime = 19 of 10 elements using division hashing b. Bucket hashing of 10 elements (N=10) in = (P) % N а. array Array: Array: LOHashing: 1. ip = pk % N 2. q=pk/N if (q%N != 0) 1 1 3 3 4 4 offset = q 5 else 6 offset = 4k+3 prime

Hashing Lab 1. Given the following key values, show what the data structures would look like after insertions 27 53 13 10 138 109 49 174 26 24 (no preprocessing necessary: P= key) Linear and the linear-quotient collision path algorithm N= 13, 4k+3 prime = 19 of 10 elements using division hashing b. Bucket hashing of 10 elements (N=10) in = (P) % N а. array Array: Array: LOHashing: 1. ip = pk % N 2. q=pk/N if (q%N != 0) 1 1 3 3 4 4 offset = q 5 else 6 offset = 4k+3 prime

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Similar questions

determine if each following statement is True or False
help
PLEASE DRAW IT. IT IS NOT CODING
Data Structure/Operation Stack/Push Balanced Binary Search Tree/Delete Binary Heap/DeleteMin Hash Table/Find Vector/push_back Binary Heap/Insert Balanced Binary Search Tree/Delete Queue/pop Vector/Find Linked List/InsertAtHead Hash Table/Insert Average Complexity in Big-O 0 (1)
Create a merge-sort multithread.A is an array, and p and q are array indexes used to sort the sub-array A[p..r]. B is a subarray that will be filled by the sort. A p-merge-sort(A,p,r,B,s) call sorts items from A[p..r] and places them in B[s..s+r-p].
Trace counting sort on the following list L of unordered keys which lie withinthe range [10, 18].L[1:10]: 16 11 18 13 11 12 15 15 18 16