help please cse problem Problem 4. [15 pts] Given: the hash function: h(x) = | 2

Question

help please
cse problem

Problem 4. [15 pts] Given: the hash function: h(x) = | 2x + 3 | mod M a bucket array of capacity N a set of objects with keys: 12,-44, 13,-88, 23, 94, 11, 39,-20, 16, 5 (to input from left to right) . . 4.a [5 pts] Write the hash table where M=N= 11 and collisions are handled using separate chaining. 0 1 2 3 45 6 7 8 910 4.b [5 pts] Write the hash table where M-N-11 and collisions are handled using linear probing. 0 1 2 3 4 5 678 9 10 4.c [5 pts] Would a size N for the bucket array exist, such that no collisions would happen with the hash function hash function h(x) | 2x+3 | mod 11 and the keys above?

Explanation / Answer

You have a function which given a number (x) determines where that should go in a table. The table has a given size, N. In the case of parts a and b of this question N is 11. M is 11 for questions a, b and c. M is just a value which is plugged into the given formula h(x) = (2x + 5) mod M So given the number 12, h(12) = (2 * 12 + 5) mod 11 => 7. So the first result goes into bucket 7. You then work your way through the rest of the numbers in turn, working out what h(x) is for each. However, when you come to a collision (i.e. a scenario where the bucket which the number should go in has already been filled by a previous number) you need to select a different bucket for it. Which bucked you select will depend on your overflow strategy. If C is taken as read I assume it means that take the numbers from the start of the list until you hit the first collision; however many numbers you already have in your bucket is the value for N. However, I believe question C I believe is a misprint. I think it wants you to find a value for M which would allow the given list of numbers to all be assigned to a unique bucket (i.e. no collisions / no overflow strategy).

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.