![]() After inserting 6 values into an empty hash table, the table is as shown below. A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. However, to find possible sequences leading to a given hash table, we need to consider all possibilities. Type 3: Given a hash table with keys, verify/find possible sequence of keys leading to hash table –įor a given hash table, we can verify which sequence of keys can lead to that hash table. Remaining option is (C) which is the answer. Option (D) is incorrect as some indexes in hash table have more than one key which never happens using linear probing. Option (A) and (B) are incorrect as all keys are not inserted in hash table. Similarly, 23, 5 and 15 will be placed at index 6, 7, 9 respectively.Īlternative Approach: We can also solve this using elimination approach as: Therefore, using linear probing, 3 will be placed at index 5 as index 3 and 4 are already occupied. However, index 3 is already occupied with 13. Therefore, using linear probing, 2 will be placed at index 4 as index 2 and 3 are already occupied.įor key 3, h(3) is 3%10 = 3. However, index 2 is already occupied with 12. Therefore, 13 is placed at 3rd index in the hash table.įor key 2, h(2) is 2%10 = 2. Therefore, 18 is placed at 8th index in the hash table.įor key 13, h(13) is 13%10 = 3. Therefore, 12 is placed at 2nd index in the hash table.įor key 18, h(18) is 18%10 = 8. The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. In linear probing technique, collision is resolved by searching linearly in the hash table until an empty location is found. Type 2: Insertion of keys into hash table using linear probing as collision resolution technique – Therefore, statement (i) and (ii) are correct which match with option (C). Solutions: Using given hash function h(x) = x mod 10Īs we can see, 9679, 19 hash to same value 9. ![]() In this type of questions, hash values are computed by applying given hash function on given keys. Type 1: Calculation of hash values for given keys –
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |