GATE Exam > GATE Questions > Consider a double hashing scheme in which the...
Start Learning for Free
Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.
Correct answer is '13'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Consider a double hashing scheme in which the primary hash function is...
For double hashing we use the formula as (h1(k) + i h2(k ))% table size where i denotes probe value.
h1(k) = 90% 23 = 21
h2(k) = 1 + k % 19
= 1 + 90 % 19 = 15
For probe 1 the value of i is 1 thus, (21 + 13) % 23 = 13
h1(k) = 90% 23 = 21
h2(k) = 1 + k % 19
= 1 + 90 % 19 = 15
For probe 1 the value of i is 1 thus, (21 + 13) % 23 = 13
Most Upvoted Answer
Consider a double hashing scheme in which the primary hash function is...
The given double hashing scheme uses two hash functions to determine the address of a key in a hash table. Let's break down the process step by step to understand why the address returned by probe 1 for key value k = 90 is 13.
1. Primary Hash Function (h1):
The primary hash function, h1(k) = k mod 23, maps the key value to an index in the range [0, 22]. In this case, h1(90) = 90 mod 23 = 21.
2. Secondary Hash Function (h2):
The secondary hash function, h2(k) = 1 (k mod 19), always returns 1. This function is used to determine the probe offset when there is a collision.
3. Probe Sequence:
The probe sequence is generated by repeatedly applying the secondary hash function with increasing probe numbers until an empty slot is found in the hash table. The probe sequence starts at probe 0.
To find the address for key value k = 90, we need to determine the probe sequence. Since h2(k) always returns 1, the probe sequence for k = 90 will be as follows:
Probe 0: h1(k) + 0 * h2(k) = 21 + 0 * 1 = 21
Probe 1: h1(k) + 1 * h2(k) = 21 + 1 * 1 = 22
Probe 2: h1(k) + 2 * h2(k) = 21 + 2 * 1 = 23
Probe 3: h1(k) + 3 * h2(k) = 21 + 3 * 1 = 24
Probe 4: h1(k) + 4 * h2(k) = 21 + 4 * 1 = 25
...
4. Address returned by Probe 1:
From the probe sequence above, we can see that at probe 1, the address is 22. However, since the table size is 23, we need to wrap around the address. Therefore, the address returned by probe 1 will be 22 % 23 = 13.
Hence, the correct answer is 13.
1. Primary Hash Function (h1):
The primary hash function, h1(k) = k mod 23, maps the key value to an index in the range [0, 22]. In this case, h1(90) = 90 mod 23 = 21.
2. Secondary Hash Function (h2):
The secondary hash function, h2(k) = 1 (k mod 19), always returns 1. This function is used to determine the probe offset when there is a collision.
3. Probe Sequence:
The probe sequence is generated by repeatedly applying the secondary hash function with increasing probe numbers until an empty slot is found in the hash table. The probe sequence starts at probe 0.
To find the address for key value k = 90, we need to determine the probe sequence. Since h2(k) always returns 1, the probe sequence for k = 90 will be as follows:
Probe 0: h1(k) + 0 * h2(k) = 21 + 0 * 1 = 21
Probe 1: h1(k) + 1 * h2(k) = 21 + 1 * 1 = 22
Probe 2: h1(k) + 2 * h2(k) = 21 + 2 * 1 = 23
Probe 3: h1(k) + 3 * h2(k) = 21 + 3 * 1 = 24
Probe 4: h1(k) + 4 * h2(k) = 21 + 4 * 1 = 25
...
4. Address returned by Probe 1:
From the probe sequence above, we can see that at probe 1, the address is 22. However, since the table size is 23, we need to wrap around the address. Therefore, the address returned by probe 1 will be 22 % 23 = 13.
Hence, the correct answer is 13.
|
Explore Courses for GATE exam
|
|
Similar GATE Doubts
Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer?
Question Description
Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer?.
Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer?.
Solutions for Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer? in English & in Hindi are available as part of our courses for GATE.
Download more important topics, notes, lectures and mock test series for GATE Exam by signing up for free.
Here you can find the meaning of Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer?, a detailed solution for Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer? has been provided alongside types of Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23 and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________.Correct answer is '13'. Can you explain this answer? tests, examples and also practice GATE tests.
|
|
Explore Courses for GATE exam
|
|
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
Follow Us
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup