Concept of Hashing

Concept of Hashing

AU: Dec.-04,05, May-05,14, Marks 8

• Hash file organization method is the one where data is stored at the data blocks whose address is generated by using hash function.

• The memory location where these records are stored is called as data block or bucket. This bucket is capable of storing one or more records.

• The hash function can use any of the column value to generate the address. Most of the time, hash function uses primary key to generate the hash index - address of the or data block.

• Hash function can be simple mathematical function to any complex mathematical function.

• For example - Following figure represents the records of student can be searched using hash based indexing. In this example the hash function is based on the age field of the record. Here the index is made up of data entry k* which is actual data record. For a hash function the age is converted to binary number format and the last two digits are considered to locate the student record.

Basic Terms used in Hashing

1) Hash Table: Hash table is a data structure used for storing and retrieving data

quickly. Every entry in the hash table is made using Hash function.

2) Hash function:

• Hash function is a function used to place data in hash table.

• Similarly hash function is used to retrieve data from hash table.

• Thus the use of hash function is to implement hash table.

For example: Consider hash function as key

3) Bucket: The hash function H(key) is used to map several dictionary entries in the hash table. Each position of the hash table is called bucket.

4) Collision: Collision is situation in which hash function returns the same address for more than one record.

For example:

5) Probe: Each calculation of an address and test for success is known as a

à probe.

6) Synonym: The set of keys that has to the same location are called synonyms. For example - In above given hash table computation 25 and 55 are synonyms.

7) Overflow: When hash table becomes full and new record needs to be inserted then ore it is called overflow.

For example -

Review Questions

1. Write a note on hashing.AU: May-14, Dec.- 05, Marks 8

2. Describe hash file organization.AU: Dec.-04, May-05, Marks 8