Homework Help is Here – Start Your Trial Now!
Engineering
Computer Engineering
8. Insert the following keys one-by-one into an initially empty hash table of size 7. Use the hash function h(x) = x mod 7 Show the result for {10, 1, 18, 15, 26, 11, 19} (a) a separate chaining hash table (do not rehash if the load factor becomes too large). (b) a table with linear probing, i.e. using the probing function f(i) = i. For parts (c) and (d), it is possible that you will not be able to insert some of the keys into the table. If you find such a key, rehash the table into a new table of size 11. You need to modify the hash function h(x) accordingly to adjust for the new table size. You do not have to change g(x) for part (d). Do not rehash earlier for any of the tables (even if the load factor becomes too large). (c) a table with quadratic probing, i.e. using the probing function f(i) = 1² (d) a table that uses double hashing with a secondary hash function, i.e. f(i) = i* g(x), where the secondary hash function is g(x) = 5 - (x mod 5).

8. Insert the following keys one-by-one into an initially empty hash table of size 7. Use the hash function h(x) = x mod 7 Show the result for {10, 1, 18, 15, 26, 11, 19} (a) a separate chaining hash table (do not rehash if the load factor becomes too large). (b) a table with linear probing, i.e. using the probing function f(i) = i. For parts (c) and (d), it is possible that you will not be able to insert some of the keys into the table. If you find such a key, rehash the table into a new table of size 11. You need to modify the hash function h(x) accordingly to adjust for the new table size. You do not have to change g(x) for part (d). Do not rehash earlier for any of the tables (even if the load factor becomes too large). (c) a table with quadratic probing, i.e. using the probing function f(i) = 1² (d) a table that uses double hashing with a secondary hash function, i.e. f(i) = i* g(x), where the secondary hash function is g(x) = 5 - (x mod 5).

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
### Hash Table Exercise **Problem Statement:** Insert the following keys one-by-one into an initially empty hash table of size 7. Use the hash function h(x) = x mod 7. Keys to insert: {10, 1, 18, 15, 26, 11, 19} Show the result for: **(a) A separate chaining hash table** - Do not rehash even if the load factor becomes too large. **(b) A table with linear probing** - Use the probing function f(i) = i. --- **Instructions for Parts (c) and (d):** If you cannot insert some keys, rehash the table into a new table of size 11. Modify the hash function h(x) for the new table size. Do not change g(x) for part (d). Do not rehash earlier for any tables, even if the load factor becomes too large. **(c) A table with quadratic probing** - Use the probing function f(i) = i². **(d) A table that uses double hashing** - Use a secondary hash function. - The probing function is f(i) = i * g(x), where g(x) = 5 - (x mod 5). --- These exercises explore various collision resolution techniques in hash tables, including separate chaining and open addressing methods like linear probing, quadratic probing, and double hashing.
Transcribed Image Text:### Hash Table Exercise **Problem Statement:** Insert the following keys one-by-one into an initially empty hash table of size 7. Use the hash function h(x) = x mod 7. Keys to insert: {10, 1, 18, 15, 26, 11, 19} Show the result for: **(a) A separate chaining hash table** - Do not rehash even if the load factor becomes too large. **(b) A table with linear probing** - Use the probing function f(i) = i. --- **Instructions for Parts (c) and (d):** If you cannot insert some keys, rehash the table into a new table of size 11. Modify the hash function h(x) for the new table size. Do not change g(x) for part (d). Do not rehash earlier for any tables, even if the load factor becomes too large. **(c) A table with quadratic probing** - Use the probing function f(i) = i². **(d) A table that uses double hashing** - Use a secondary hash function. - The probing function is f(i) = i * g(x), where g(x) = 5 - (x mod 5). --- These exercises explore various collision resolution techniques in hash tables, including separate chaining and open addressing methods like linear probing, quadratic probing, and double hashing.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 8 steps with 4 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