Assume that linear probing is used for hash-tables. To improve the time complexity of the operations performed on the table, a special AVAILABLE object is used to mark a location when an item is removed from the location. Assuming that all keys are positive integers, the following two techniques were suggested instead of marking the location as AVAILABLE: i) When an entry is removed, instead of marking its location in the table as AVAILABLE, indicate the key in the location as the negative value of the removed key (e.g., if the removed key was 16, indicate the key as -16). Searching for an entry with the removed key would then terminate once a negative value of the key is found (instead of continuing to search if AVAILABLE is used). ii) Instead of using AVAILABLE, find a key in the table that should have been placed in the location of the removed entry, then place that key (the entire entry of course) in that location (instead of setting the location as AVAILABLE). The motive is to find the key faster since it is now in its hashed location. This would also avoid the dependence on the AVAILABLE object. Will either of these approaches have an advantage? You should analyze in terms of both time and space complexities. Additionally, will any of these approaches result in misbehaviors (in terms of functionalities)? If so, explain clearly through illustrative examples.
Assume that linear probing is used for hash-tables. To improve the time complexity of the operations
performed on the table, a special AVAILABLE object is used to mark a location when an item is
removed from the location. Assuming that all keys are positive integers, the following two techniques
were suggested instead of marking the location as AVAILABLE:
i) When an entry is removed, instead of marking its location in the table as AVAILABLE, indicate the key in the location as the negative value of the removed key (e.g., if the removed key was 16, indicate the key as -16). Searching for an entry with the removed key would then terminate once a negative value of the key is found (instead of continuing to search if AVAILABLE is used).
ii) Instead of using AVAILABLE, find a key in the table that should have been placed in the location of the removed entry, then place that key (the entire entry of course) in that location (instead of setting the location as AVAILABLE). The motive is to find the key faster since it is now in its hashed location. This would also avoid the dependence on the AVAILABLE object. Will either of these approaches have an advantage? You should analyze in terms of both time and space complexities. Additionally, will any of these approaches result in misbehaviors (in terms of functionalities)? If so, explain clearly through illustrative examples.
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 4 images
