Concept explainers
(a)
To determine the longest probe while performing insertion in hash table.
(a)
Explanation of Solution
Given Information: The probability of ith insertion in hash table by using uniform hashing is atmost 2-k.
Explanation:
In the uniform hashing, where keys are inserted uniformly in available hashes. Suppose there is an open address hash table and keys are inserted one by one then average probe will be (1/(1-a)), where a is equals to load factor. So, while inserting keys into empty hash table, for the first hash slot, unsuccessful expected number of probe will be
Since
So, the at most probability will be
(b)
Show that the ith insertion requires more than 2lg n probe and probability
(b)
Explanation of Solution
Given Information: An open addressing hash table having size m and contains
Explanation: From the above section, where the probability of ith insertion of an item in the hash table by using uniform hashing is at most 2-k.
Where k is the no. of probes. Now from the given condition, put the value of probe k is equals to 2 logn.
So, the complexity will be
(c)
To show the asymptotic bounds for the probes required is equals to
(c)
Explanation of Solution
Given Information: For a particular event A, probability of probes required
Explanation: For an event A, required probes X>2lg n, and for the ith insertion, required probes for an event
An event
by Boole’s inequality
So, the asymptotic bound for the probe required is equals to
(d)
To determine the expected length of the longest probe sequence is
(d)
Explanation of Solution
Given Information: Probability of number of probes required
Explanation:The expected length of the longest probe E[X] can be dependent on the given probability
Here,break the above equation into two parts by using some breaking point, in this case its 2lg n.
Want to see more full solutions like this?
- Problem 2: In this problem we assume that h: U → {0, 1, . . . , m − 1} is a good hashfunction, that is, every key k has the same probability 1/m to map to any place in the tableT of length m.(i) What is the probability that three pairwise distinct elements u1, u2, u3 ∈ U aremapped by the function h to the same place in the table (that is, h(u1) = h(u2) =h(u3))?(ii) We insert three elements into an empty hash table T using the hash function h. Ifcollision is solved by chaining, what is the probability that T[0] and T[1] are empty?arrow_forwardcode in python attached please Define a hash table with an associated hash function ℎ(?)h(k) mapping keys ?k to their associated hash value. b) In simple uniform hashing, each key is assumed to have equal probability to map to any of the hashes in a given table of size m. Given an open-address table of size 500500 and 22 random keys, what is the probability that they hash to the same value? What is the probability that they hash to different values?arrow_forwardSuppose we are hashing integers with 7-bucket hash table using the hash function h(i) = I mod 7. Show the resulting closed hash table with linear resolution of collisions (i.e., handling collisions with separate chaining) if the perfect cubes 1, 8, 27, 64, 125, 216, 343 are inserted.arrow_forward
- Regarding the Hash algorithm, which one(s) of the following is/are correct, check all that apply. Given a hash of a piece of information, it is hard to recover the original information itself. Given a piece of information, it is hard to find another piece of information that can generate the same hash. O It is theoretically possible, but practically infeasible, to find two pieces of information that generates the same hash. O Hash is unique to a piece of information, there are no any two piece of information that can generate the same hash unless these two pieces of information are identical.arrow_forwardProve that In a hash table in which collisions are resolved by chaining, a successful searchtakes average-case time ‚.1C˛/, under the assumption of simple uniform hashing.arrow_forwardComputer Science (a) Let h be a collision resistant hash function. Now consider the following function H that is defined for binary strings of even length. Let x = x1||x2 with x1 ∈ F2n and x2 ∈ Fn2 . Then H(x) = h(x1 ⊕ x2). Prove that this function is not collision resistant.arrow_forward
- Given input {71, 22, 21, 99, 53, 69, 39} and a hash function h(x) = x mod 10, show the resulting: Hash table with double hash function (Use: h(x)=5-(x mod 5) ) and give the time complexity of search and insert operation with big-oh notation.arrow_forwardThis is question which I want you to solve but solve with this step and draw Q/Given input (4371, 1323, 6173, 4199, 4344, 9679, 1989) and hash function h(x):=xmod 10 show the resulting a. Separate chaining hash table.. B.Hash table using linear probing. C. Hash table using quadratic probing This is examples pls follow step same step when you solve questions up EX: given input (89, 18, 49, 58, 69) and a hash function h(x) = x mod 10, show the resulting: 1. Hash table using linear probing. 2. Hash table using quadratic probing. Sol: 1- Linear probing 9 89 0 49 في حالة وجود تصادم نتحرك بمقدار واحد لتفادي التصادم H(x)=x mod 10 1 2 3 4 58 89 2- quadratic probing. H(x)=x mod 10 0 1 2 49 58 3 69 5 6 H(x)=x + imod 10 4 5 7 6 نبدي من 1 وفي حاله حصل تصادم نزيد واحد 8 7 18 8 18 9 89arrow_forwardInsert into a hash table with open addressing - linear probing with size 12 and hashing function h(x) = 5x mod 12: 31, 24, 51, 73, 89, 4, 103, 21, 33, 55, 81, 62arrow_forward
- Let r[i][j]r[i][j] be the maximum value we can carry using only items 1 to i given a knapsack of сарacity ij. Suppose there are 4 items in the shop. The values of the items are [5, 7, 10, 6] and the weights of the items are [3, 2, 4, 1]. 1. If our knapsack has capacity 1, compute r[i][1] for each 1<=i<=4. Which items should we take?arrow_forwardGiven a sequence of 5 element keys < 23, 26, 16, 38, 27 > for searching task:a) Given the hash function H(k) = (3.k) mod 11, insert the keys above according to its original sequence (from left to right) into a hash table of 11 slots. Indicate the cases of collision if any. b) In case of any collisions found above in a) part, determine the new slot for each collided case using Linear Probing to solve the collision problem. Clearly show your answer for each identified case. No step of calculation required. (Answer with “NO collision found”, in case there is no collisions found above) c) In case of any collisions found above in a) part, determine the new slot for each collided case using Double-Hashing (with functions below) to solve the collision problem. Show your steps and calculations with a table as in our course material. d1 = H(k) = (3.k) mod 11 di = (di−1 + ((5·k) mod 10) + 1) mod 11 , i ≥ 2 (Answer with “NO collision found”, in case there is no collisions found above)…arrow_forwardextermal (overilow) chaining is used to resolve collisions. The hash function is suh DL. Consider a hash table with n buckets, where extermal (overilow) chaining is used t resolve collisions. The hash tunction is that the probability that a key value is hashed The hash table is to a particular bucket is initially empty and K distinct values a inserted in the table.arrow_forward
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education