Q1 Implement Kwhashmap Interface In The Book Using The Following Hashing Methods To Organize The Hash Table 1 Impleme 1 (80.61 KiB) Viewed 82 times
Q1 Implement Kwhashmap Interface In The Book Using The Following Hashing Methods To Organize The Hash Table 1 Impleme 2 (80.61 KiB) Viewed 82 times
Q1 Implement Kwhashmap Interface In The Book Using The Following Hashing Methods To Organize The Hash Table 1 Impleme 3 (46.56 KiB) Viewed 82 times
Q1. Implement KWHashMap interface in the book using the following hashing methods to organize the hash table: 1. Implement the chaining technique for hashing. However, use binary search trees to chain items mapped on the same table slot. 2. Implement a hashing technique that is a combination of the double hashing and coalesced hashing techniques (which is a hybrid of open addressing and chaining). a. Research about coalesced hashing. Explain the method and its advantages and disadvantages over standard open addressing and chaining methods in your report. b. Research about double hashing. Explain the method and its advantages and disadvantages over standard open addressing and chaining methods in your report. In our hybrid method, during an insertion operation, the probe positions for the colliding item are calculated by using the double hashing function. Moreover, the colliding items are linked to each other through the pointers as in the coalesced hashing technique. Use the following hash function to calculate probe positions. tabelsize = determined dynamically. Note that it should be prime and should be increased twice if the load factor is above the threshold. (10 in the example) • Prime_number = the largest prime number smaller than 0.8*tablesize (7 in the example) • Hash1 = key % tablesize (10 in our case) • Hash2 = Prime_number - (key % Prime_number) • Hash function = (Hash1 + li* Hash2]) % tablesize for the ith probe. Note that you should use the links during the search operation. The deletion of a key is performed by linking its next entry to the entry that points to the deleted key. If the deleted element is found without any probe, you should replace deleted entry with the next entry. As an example, see the illustrations below to insert 3, 12, 13, 25, 23, 51, and delete 25. 3. Test and compare your hash table implementations empirically. Use 100 randomly generated data sets for each three different set sizes (small (size = 100), medium (size = 1000), and large size = 10000)). Insert the elements in a data set into initially empty hash table. Perform different tasks over the tables to compare their performance results (like accessing existing/non-existing items or adding/removing items). a
Insert 3: Hash Key Value Next Insert 12: Hash Кеу Value Next Insert 13: Hash Кеу Value Next WNO 2 3 12 12 00WNO NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL 1 2 3 4 5 6 7 8 9 NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL 1 2 3 4 5 6 7 8 OPNM N 000 NULL NULL NULL NULL 5 NULL NULL NULL NULL NULL 13 3 3 3 Insert 25: Hash Кеу Value Next Insert 23: Hash Key Value 0 Next Insert 51: Hash Value Key Next 00ouWNO 1 2 3 4 5 6 7 8 9 1 2 3 4 12 13 NULL NULL NULL NULL 5 NULL NULL NULL NULL NULL 23 12 13 NULL NULL NULL NULL 5 NULL NULL NULL 3 NULL 00V AWNO 1 2 3 4 5 6 7 8 9 5 6 7 8 Misimi m NULL NULL NULL NULL 5 NULL NULL NULL 3 NULL 23 12 13 51 3 25 3 25 5 N001 3 25 Delete 25: Hash Value Key Next 2 3 OPNM N 000 12 13 51 3 23 NULL NULL NULL NULL 5 NULL NULL NULL NULL NULL 9
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!