5.7 In the quadratic probing hash table, suppose that instead of inserting a new item into the location suggested by findPos, we insert it into the first inactive cell on the search path (thus, it is possible to reclaim a cell that is marked "deleted," potentially saving space). a. Rewrite the insertion algorithm to use this observation. Do this by having find- Pos maintain, with an additional variable, the location of the first inactive cell it encounters. (Solution Not available) b. Explain the circumstances under which the revised algorithm is faster than the original algorithm. Can it be slower? Sol: If the number of deleted cells is small, then we spend extra time looking for inactive cells that are not likely to be found. If the number of deleted cells is large, then we may get improvement. | |
| View Solution | |
| << Back | Next >> |