A hash function h defined h(key)=key % 7 is used to insert the keys 44, 45,, 79, 55, 91, 19 into a table indexed from 0 to 7 (that is, HT[0], HT [1],HT[2],HT(3],HT[4],HT[5], HT[6], HT[7] ). Show the how these keys, in the order given, are inserted in HT using the above hashing function when collisions are handled by 1) a linear probing, and 2) double hashing using a second hash function g(k)=D5 - (key%5). The double hashing rule is (h(X) +i*g (X)) % HTSize, i=0,1,2,..). Note that some keys (44, 45, 55 ) are already inserted. You need to inser the keys, 79, 91, 19 into the hash table.

A hash function h defined h(key)=key % 7 is used to insert the keys 44, 45,, 79, 55, 91, 19 into a table indexed from 0 to 7 (that is, HT[0], HT [1],HT[2],HT(3],HT[4],HT[5], HT[6], HT[7] ). Show the how these keys, in the order given, are inserted in HT using the above hashing function when collisions are handled by 1) a linear probing, and 2) double hashing using a second hash function g(k)=D5 - (key%5). The double hashing rule is (h(X) +i*g (X)) % HTSize, i=0,1,2,..). Note that some keys (44, 45, 55 ) are already inserted. You need to inser the keys, 79, 91, 19 into the hash table.

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

Related questions

Q: Jump to level 1 An empty hash table hash Table has 15 buckets and a hash function of key % 15. The…

A: Collision occurs in hash table when more than one key is inserted at same location. Here 15 buckets…

Q: Exists a fixed number of linked lists in an m-sized hash table? The purpose of a hash function is…

A: The question is solved in step2

Q: Given the following hash function: h (x) - round (x.key) which rounds to the nearest whole number,…

A: Hashing is a technique that is used to uniquely identify a specific object from a group of similar…

Q: Using separate chaining and the hash function ‘key mod 7’, insert the following sequence of keys in…

A: The objective of the question is to insert a sequence of keys into a hash table using the separate…

Q: Given the following hash function: h (x) - round (x.key) which rounds to the nearest whole number,…

A: Hash table The key value pair in the given table stored in the hash code using hash function…

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: Given the hash function as h(key) = key mod m where m=3, create an hash table for these entities…

A: - We need to work on the hash table shown.

Q: Use the table below to convert a character key to an integer for the following questions. Letter A…

A: The Answer is

Q: Show what occurs when the keys 5, 28, 19, 15, 20, 33, 12, 17, and 10 are inserted into a hash table…

A: To demonstrate the process of inserting the given keys into a hash table with chaining, we'll follow…

Q: Determine the total number of linked lists contained in a chaining hash table of size T. Can you…

A: Introduction: Within the scope of this specific investigation, we posed the following query: If a…

Q: T is an empty hash table. The size of T is 4 and the hash function is h(key) = key mod 4. Draw the…

A: Given that initially T is empty.

Q: Q4. Let I be a table of size 5. Given is the hash function division, defined as the modulus of a key…

A: Using linear probing

Q: Start with an empty hash table of capacity 10 and load factor .75 • Double the table capacity during…

A: Solution :-

Q: 5. After keys: 24, 17, 32, 26, 44, 62 are given, Use linearly exploration method to build a closed…

A: here we have given solution to build a closed hash table and generated ASL values

Q: 2. Which memory locations are assigned by the hashing function h(k) = k mod 101 to the records of…

A: % returns the remainder left over when one operand is divided by a second operand. a) 104578690 h(k)…

Q: Does a hash table of size m contain the same number of linked lists at all times? No matter how hard…

A: No, a hash table of size m does not necessarily contain the same number of linked lists at all…

Q: 2. Using the keys as given below: 40, 32, 18, 90 Compute the hash values, using h(k) = k mod m Size…

A: Hello student Greetings Hashing is a technique used to store and retrieve data in a data structure…

Q: Explain a situation where you could change the runtime of a hash table from O(1) to O(n) when using…

A: Chaining is a hashing collision resolution technique which is used to solve the collisions problem…

Concept explainers

Hash Table

A hash table also called a hash map, is a data structure that maps key-value pairs. The hash table can be used in complex systems to provide fast access and compact storage. A hash table is a structure that stores data in an abstract data type kind of associative array. It keeps data in an array format, with a distinct index value for every data value. If the index of the required data is known, then the data can be accessed very easily.

Question

A hash function h defined h(key)=key % 7 is used to insert the keys 44, 45, 79, 55, 91, 19 into a table indexed from 0 to 7 (that is, HT(0], HT
[1],HT[2],HT[3],HT[4],HT[5], HT[6], HT[7] ). Show the how these keys, in the order given, are inserted in HT using the above hashing
function when collisions are handled by 1) a linear probing, and 2) double hashing using a second hash function g(k)=5 - (key%5). The
double hashing rule is (h(X) + i*g (X)) % HTSize, i=0,1,2,..). Note that some keys (44, 45, 55 ) are already inserted. You need to insert
the keys, 79,91, 19 into the hash table.
Index
Linear Probing to resolve collision
Double Hahing to resolve collision
(a)
(f)
(g)
1
(b)
44
44
3
45
45
4.
(c)
(h)
(i)
(d)
6
55
55
(e)
(i)

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 hash table

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 2 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

Using the values provided below, show the hash key and what the hash table will look like when using the two different techniques indicated. The hash function used is based upon the first letter of the person's last name. The array size is 27 Index 0 is not used The letter 'A' will go to index 1, 'B' to index 2, etc Separate chaining Open addressing with linear probing i_table = ( h(k) + j ) mod S where i is the index of the underlying array,h is the hash function,j is the iteration of the probe, andS is the size of the table Values needing to be hashed (in order from top to bottom) Big Bird The Penguin Jackie Chan The Joker The Riddler Lewis Carroll Arthur Doyle Clark Kent Clive Lewis Lois Lane Yogi Bear Charles Dickens Geoffrey Chaucer Mr Ranger William Shakespeare John Tolkien Fred Rogers
What is the average time complexity to delete a key from a chaining hash table? (Assume that the table size is k; and the hash table hold m data)
The following is a prioritised list of considerations that might impact a hash table's Big-O performance:
Given hash function h(key), when inserting an item with key k to the hash table A, which linked list and position the item should be placed?
You are asked to insert the following values into the hashing table size 9: 9, 18, 19, 27, 8, 17. Use linear probing if there is a collision. Your answer will be in the form of the order of inserted elements. The order of inserted elements:: 9 18 19 - - 27 8 - 17 The order of inserted elements: 9 18 19 27 - - 17 - 8 O The order of inserted elements: 9 18 19 27 17 - - -8 O The order of inserted elements: 9 18 19 27 8 - -17 -
What is the total number of linked lists in a chaining hash table of size T? What kind of basic data structures are contained in the Separate Chaining hash table?
If N items are inserted into a hash tabble of size H, what is the expected average chain length?
For a hash table of size 23, the hash function used is h1(key)=key%23. Initially the table contains a single key stored in the table at location 15. If double hashing is used, and h2(key) = 7 – key%7, where will the next 3 keys (key1=15, key2=84, key3=383) that hash to location 15 be stored? Question 12 options: 6, 19, 24 21, 22, 17 21, 14, 20 6, 13, 14
Hashing (4’). For the input 30, 20, 56, 75, 31, 25 and hash function h(K) = K mod 12a. (1’) Construct the open hash table.b. (1’) Find the average number of key comparisons in a successful search in this table.c. (1’) Construct the closed hash table.d. (1’) Find the average number of key comparisons in a successful search in this table.
The following is a prioritised list of considerations that might impact a hash table's Big-O performance:
Best hash function will never create any collision among the hash table values. O True O False QUESTION 4 There exists a data structure to maintain a dynamic set with operations Insert(x), Delete(X) and Contains(X) that has an expected running time of O(1) per operation. O True O False
If the sizeof hash table is 11, the hash function is H(key)=(2*key+1)MOD 11，open addressing, square probing. According to the keywords sequence (19,21,10,7,23,32,17,15,11,22), please insert these keywords in the hash table from 0-10 .