### 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.

Key={10,1,18,15,26,11,19} Part -A) separate chain method h(x)=x mod7 key hash function 10…

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)

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

Related questions

Q: Index 1 2 3 4 Value using Quadratic Overflow is processed Index 0 1 2 3 4 Value 0 5 6 probing. 5 6 7…

A: the

Q: Create a hash table

A: Given :- A hash table of size 8 hash function h(k) = 2k + 3 where k is the key value the following…

Q: Given the series of inputs [45, 7, 46, 90, 34, 6, 7, 71, 23, 24], insert each of these integers into…

Q: Suppose we have a hash map that uses the standard “mod” hash function shown in the chapter and uses…

A: Step by step solution for the given question on hashmap is given below.

Q: 0 1 11592 2 4786 3 4 5 6 589 7 1794 For this problem the hash function h(k) is equal to the sum of…

A: Linear probing is a collision resolution technique employed in hash tables to address collisions…

Q: Given the array of size 13, and the hashing function h(x) = x%13, at which array location would data…

A: For the given hash function, we need to find the array location at which key value 33 be stored.

Q: Jump to level 1 valsTable: o 1 2 3 4 5 6 7 8 6 76 98 Empty-since-start Empty-after-removal Occupied…

A: Hashing is a technique that provides direct access to the value stored in a table or storage space.…

Q: A hash table is an efficient data structure to store and access data via keys. In this problem, you…

A: a) The number of unique subarrays in an array of length n can be calculated as n(n+1)/2. b) To…

Q: One of the goals of a hash table is to get O(1) for set operations add() and remove(). With linear…

A: true or false question

Q: Insert the following numbers in a hash table of size N=5 using a modulo function and linear probing.…

A: Hash table size, N = 5 Keys: 10, 14, 41, 50, 62, 70, 86, 30, 37, 5

Q: 1. Let H be a hash table of size 7 with the hash function h(K) = 3*K mod 7 implemented using CHAINED…

A: Given that, Size of the hash table= 7 Hash function h(K)= 3*K mod 7 Chained Hashing: Chained Hashing…

Q: b) Consider an empty hash table of size 7. Draw the table that results after inserting, in the given…

A: The answer is as follows:-

Q: I am having troubles understanding part 4: hash table with second hash· function h2 = 7 - (x mod 7).…

A: This is very simple. Note: Indexing starts with 0 (always remember) Initially, the hash table is…

Q: Given a hash table with m=10 entries and the following hash function h: h(key)= key mod m Input:…

A: Collision in Hash Table: If we want to insert a key into the hash table and that place is occupied…

Q: 1. Given the hash function: h(i) = i % 13 and double hash function: d(i) = 1 + i % 12. Show the…

A: Introduction: Using a collection of inputs of any size, a hash function organizes them into a table…

Q: 1. Draw the 11-entry hash table that results from using the hash function h(i)=(3i+5) mod 11, to…

A: Hash table:A hash table, also known as a hash map, is a fundamental data structure used in computer…

Q: ). This problem is about linear probing method we discussed in the class. Problem 4, Consider a hash…

A: Hash Function hx=x mod 11 Start with 5. 5 will be placed at index 5 (a). 8 will be placed at index…

Q: Consider the following cuckoo hashing with 2 tables. Both tables have a size of 11. The hashing…

A: Answer

Q: 1.Question: Consider a hash table of size m=7. Draw the table that results after inserting the…

A: Given : Keys to insert: 19,26,13,48,17

Q: 6. Hashing Given a hash table with m = 11 entries and the following hash function h1 and step…

A: Chaining : In chaining, all the values having same hash function value are stored as a linked…

Q: The following should be taken into account while creating a fully working open hash table:

A: Tableau hash When data is hashed, a hash table represents it as an array where each item carries a…

Q: Given the following hash map array of size 10 (horrible array size!!) and a hashing function of…

A: Answer 1: Explanation: Given hash function is num%arraysize In the question, num=73 and…

Q: L is a list of data elements that is linear. Use the list as follows: I a linear open addressed…

A: L is a list of data elements that is linear. Use the list as follows: I a linear open addressed hash…

Q: Problem 1: What is the 11-entry hash table that results from inserting the keys 19, 37, 20, 81, 30,…

A: To determine the hash table resulting from inserting the given keys. We need to calculate the hash…

Q: Suppose you use hashing with separate chaining. The array is size 7, and the hashing function is…

A: - We need to perform hashing on the values shown.

Q: Extendible hash index: Consider the Extendible Hashing index shown in figure below: Show the state…

A: Directories and buckets are utilized in the dynamic hashing technique known as extensible hashing to…

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.

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1

VIEW

Step 2 : separate chain method

VIEW

Step 3

VIEW

Step 4 Linear Hash table

Step 5

Step 6

Step 7

Step 8

Trending now

This is a popular solution!

Step by step

Solved in 8 steps with 4 images

SEE SOLUTION Check out a sample Q&A here

Similar questions

(f) A hash table with 6 buckets is initially empty and the hash function is h(k) = k%6. What is the state of the hash table after inserting 3, 6, 1, 12, 7 assuming linear probing?
help
3. For the input 30, 20, 56, 75, 31, 19 and hash function h(K) = K mod 11 a. apply closed-hashing. b. find the average number of key comparisons in a successful search in this table. c. find the worst case number of key comparisons in a successful search in this table.
We are using a subpar hash map, where each value is accumulated in a single container. A hash map has successfully achieved its purpose.
Show the result when we insert the keys 5; 28; 19; 15; 20; 33; 12; 17; 10 into a hash table with collisions resolved by linked list at each slot. Let the hash table have 9 slots, and let the hash function be h(x) = (2x+1) mod 9. (You are expected to draw the final hash table)
Hash table is a data structure in which keys are mapped to array positions by a hash function. The process of mapping the keys to appropriate locations in a hash table is called hashing. Hash functions are used to reduce the number of collisions. i. Mention the methods to minimize collision. ii. Explain the advantage of using double hashing over linear and quadratic probing techniques. Load the keys given below in a hash table of size 7 in the same order using chaining with the hash function h(key)= key % 7. Show graphically how collisions are resolved using chaining in this particular case. ii. 12, 101, 3, 21, 14, 13, 16, 7, (last two digits of your reg # + 102)
Answer the following ture or false question 1. The 9-entry hash table that results from using the hash function, h(i) = (2i+7) mod 9, to hash the keys 12, 5, 13, 4, 10, 19, 8, 3, and 28, assuming collisions are handled by linear probing as follows: 0 1 2 3 4 5 6 7 8 10 19 3 28 12 8 13 4 5 Group of answer choices True False 2. Here is how the built-in sum function can be combined with Python’s comprehension syntax to compute the sum of all numbers in an n x n data set, represented as a list of lists: sum(sum(subset) for subset in data) Group of answer choices True False 3. Here is the comparison for asymptotic growth rate: (logn) < (n) < (nlogn) < (n^2) < (n^3) < (2^n) Group of answer choices True False 4. Here is the Python’s list comprehension syntax to produce the list of this 26 characters ['a', 'b', 'c', ..., 'z']: [chr(k) for k in range(97, 123)] Group of answer choices True False
Given the hash function: h(i) = i % 13Show the array after inserting the following keys: 18, 41, 22, 44, 59, 32, 31, 73, in this order. Use linear probing to resolve collisions.
Linear hash index:Consider the Extendible Hashing index shown in figure below.A bucket is split each time an overflow page gets created Show the state of the index after each operation:a) Insertion of entry 2b) Insertion of entry 40c) Insertion of entry 39
(b) Using the quadratic probe sequence from part (a), write the pseudo-code for an algorithm called HashInsert(T, k) that takes as input a hash table T[0,..., 12] and a key k to be inserted into the table. Your algorithm must insert the item k into the table, using the probe sequence h(k, i) and return true if the insertion is successful, and false otherwise. *You do not have to check for duplicates (you can assume when inserting k that it is not already in the table). You can assume that the table was initially empty and only inserts were carried out, no deletions
13. For the Hashing function h(x) = (x² + 1) mod 15, show how the data 5, 8, 20, 32 and 40 would be inserted in the order given in initially empty cells indexed 0 to 14. %3D
Let us consider an empty hash table with 10 positions indexed from 0 to 9. Please illustrate the content of the hash table after inserting the elements 79, 8, 39, 48, 3, and 60 using(1) Quadratic Probing (2) Double hashing with h(k) = k%10 and h’(k)= 7-k%7