Data Structures and Algorithms

Abstract

Describe Larsen's method of dynamic hashing that enables a record to be located on a disk given its key using just one disk transfer and only a modest amount of information held in main memory. [10 marks] In Larsen's method each key has associated pseudo-random sequences of probe and signature values. Discuss what properties these sequences should have. Outline an algorithm that could be used to compute the n th probe–signature pair for a given key. You may assume that the key is a character string. [6 marks] Briefly discuss why Larsen's method is not used in most current filing systems. [4 marks]