Consider a hash table π[0, 1, β¦ , 10] that is initially empty. The hash table is
maintained using open addressing with linear probing. The hash function used is
β(π₯) = (π₯+ 7) mod 11.
Consider the following sequence of insertions performed on π:
1, 13, 22, 15, 11, 24
Which of the following positions in the hash table is/are empty after these insertions
are performed?
Consider a hash table π[0, 1, β¦ , 10] that is initially empty. The hash table is
maintained using open addressing with linear probing. The hash function used is
β(π₯) = (π₯+ 7) mod 11.
Consider the following sequence of insertions performed on π:
1, 13, 22, 15, 11, 24
Which of the following positions in the hash table is/are empty after these insertions
are performed?
Show Hint
- 0
- 10
- 2
- 1
The Correct Option is C
Solution and Explanation
Let's track the hash table as a running occupancy list after each insertion, rather than computing all hash values and filling in afterward, to visualize how collisions get resolved.
Step 1: Compute all six hash values up front using \(h(x) = (x+7) \mod 11\).
\(h(1)=8\), \(h(13)=9\), \(h(22)=7\), \(h(15)=0\), \(h(11)=7\), \(h(24)=9\).
Step 2: Track occupancy slot by slot.
After inserting 1, 13, 22, 15 (all land on their home slots 8, 9, 7, 0 with no collision), the table looks like: slot0=15, slot7=22, slot8=1, slot9=13, and slots 1-6 and 10 are still empty.
Step 3: Insert 11, home slot 7, which is taken.
Walking forward from slot 7: slot7 taken, slot8 taken, slot9 taken, slot10 free. So 11 goes to slot 10. Now slots 0,7,8,9,10 are filled; slots 1-6 remain empty.
Step 4: Insert 24, home slot 9, which is taken.
Walking forward from slot 9: slot9 taken, slot10 taken, wrap to slot0 taken, slot1 free. So 24 goes to slot 1. Now the filled slots are 0,1,7,8,9,10; the only slots left empty are 2, 3, 4, 5, 6.
Step 5: Match against the answer choices.
The choices given are indices 0, 10, 2, and 1. Checking against our empty-slot list of 2,3,4,5,6: index 0 is filled (15), index 10 is filled (11), index 1 is filled (24), and only index 2 is genuinely empty.
Hence the only index among the options that is empty after all insertions is 2.
Top Questions on Hashing
- Match the following:
List I List II 1 FIFO a Stack 2 Look up op. b Queue 3 Last-In first out c Hash table - Match the items in Column 1 with the items in Column 2 in the following table :
Column 1 Column 2 (p) First In First Out (i) Stacks (q) Lookup Operation (ii) Queues (r) Last In First Out (iii) Hash Tables - Consider performing uniform hashing on an open address hash table with load factor \(Ξ± = \frac{n}{m}< 1\), where n elements are stored in the table with m slots. The n m expected number of probes in an unsuccessful search is at most \(\frac{1}{1-\alpha}\)
Inserting an element in this hash table requires at most ______ probes, on average. - Want to practice more? Try solving extra ecology questions todayView All Questions
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the blockβs anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems