Assume that we have a hash table of 10 slots, and we use the hash function h(k) = k mod 10. Show the results of inserting the following series of records in the table using the various collision resolution methods: 11, 31, 32, 56, 46, 47, 66. a) Linear probing b) Double hashing with second hash function h2(k)= k/10.

Assume that we have a hash table of 10 slots, and we use the hash function h(k) = k mod 10. Show the results of inserting the following series of records in the table using the various collision resolution methods: 11, 31, 32, 56, 46, 47, 66. a) Linear probing b) Double hashing with second hash function h2(k)= k/10.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Insert keys {10, 22, 11, 31, 24, 88, 38, 21} into an empty hash table with CAPACITY = 10 using quadratic probing (c1=0 and c2=1) to resolve collision (You shouldn't use a for/while loop except to increment the value of i for quadratic probing). Use the hash function is h(k, i) = (h’(k) + c1* i + c2* i^2) mod 10 and h’(k) = k mod 10.
1. Give the contents of the resulting hash table when you insert items with the keys L A G U N I V E R S in that order into an initially empty table of size M = 16 using linear probing. Use the hash function 11k mod M to transform the kth letter of the alphabet into a table index. Example: hash(J) hash(10) = 110 % 16 = 14 Show the detailed solution for each key and plot the items in the hash table.
Consider the following sequence of key-value pairs: (1, "A"), (2, "B"), (3, "C"), (4, "D"), (5, "E"), (6, "F"), (7, "G"), (8, "H"), (9, "I"), (10, "J"). Insert these key-value pairs into an empty hash table of size 5 using the hash function h(k) = k mod 5. Draw the resulting hash table after each insertion. Assume that collisions are handled using linear probing.
Given the array of size 13, and the hashing function h(x) = x%13, at which array location would data with key value 33 be stored? Assuming 45 and 71 have already been inserted in the array and the quadratic probing is used for collision. Question options: A. 7 B. 10 C. 9 D. 2 E. 11
20 a) Given a hashing function hash(x) = ((x * x) + x) % 11, Insert the value 17 into each hash table using the rules specified below. Note that some of the boxes in each hash table are already full. If there’s a collision, start the probing at i = 0 and increment from there if you collide. b) After we insert our new data (that 17) into these hash tables, should we resize and rehash the values? Why or Why not? c) If this was a hash table using separate chaining instead of linear probing, would it be time to rehash after we insert 17?
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
Suppose that we are using extendable hashing on a file that contains recordswith the following search-key values:2, 3, 5, 7, 11, 17, 19, 23, 29, 31Show the extendable hash structure for this file if the hash function is h(x) = xmod 8 and buckets can hold three records.
Given n data (n=15) as 19, 39, 94, 97, 89, 72, 78, 80, 12, 18, 31, 25, 77, 48, and 99. Using hash function (key = data mod P), where P is the smallest prime number which is bigger than n, create hash table H1 using chaining strategy for collision and compute the average comparison times in searching process.
Insert the following data into a hash table implemented using linear openaddressing. Assume that the buckets have three slots each. Make use of the hashfunction h(X) = X mod 9.{17, 09, 34, 56, 11, 71, 86, 55, 22, 10, 4, 39, 49, 52, 82, 13, 40, 31, 35, 28, 44}
Show what occurs when the keys 5, 28, 19, 15, 20, 33, 12, 17, and 10 are inserted into a hash table with collisions addressed by chaining. If the table has nine slots, then the hash function should be h.k/D k mod nine.
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
Consider a OBHTin which the keys are student identifiers (strings of 6 digits). Assume the following number of buckets and hash function: m = 100; hash(id) = first two digits of id Starting with an empty hash table, show the effect of successively adding the following student identifiers: 000014, 990021, 990019, 970036, 000015, 970012, 970023. Use following function as second hash function hash(id) = last digit of id 2. Show the effect of deleting 000014 from the hash table