Homework Help is Here – Start Your Trial Now!
Engineering
Computer Engineering
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)
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
icon
Related questions
Question
# Hashing Lab ## Instructions 1. 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
Transcribed Image Text:# Hashing Lab ## Instructions 1. 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.
Transcribed Image Text:**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.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps with 3 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY
SEE MORE TEXTBOOKS