What is a hashing function? What are the properties of a good hashing function? Describe the folding technique for hashing functions.
Ans: Hashing function is a method to store a file on the disk. A hash function is a function which while applied to a value of a record (hash field) gives a hash value that is the address of the disk block where the record is stored.
The properties of a good hash function are like this:
- It must be easy to evaluate.
- The hash value acquired should be within the range of valid addresses for a given file.
- The hash values should be consistently distributed over the range of addresses so that the collisions are minimum.
Folding method for hashing functions: It includes applying an arithmetic function like addition or a logical function such as exclusive OR to different parts of a hash field to compute the hash addresses. For instance, the numeric hash field can be split into start, middle and end regions, like that the sum of the lengths of the start and end regions equivalents the length of the middle region. The start, middle and end regions' digits are added to acquire a new value, x. After that x mod s, where s is the upper limit for the hash function, provides the hash value.