Static Hashing

Static Hashing

• In this method of hashing, the resultant data bucket address will be always same.

• That means, if we want to generate address for Stud_RollNo = 34789. Here if we use mod 10 hash function, it always result in the same bucket address 9. There will not be any changes to the bucket address here.

• Hence number of data buckets in the memory for this static hashing remains constant throughout. In our example, we will have ten data buckets in the memory used to store the data.

• If there is no space for some data entry then we can allocate new overflow page, put the data record onto that page and add the page to overflow chain of the bucket. For example if we want to add the Stud_RollNo= 35111 in above hash table then as there is no space for this entry and the hash address indicate to place this record at index 1, we create overflow chain as shown in Table 4.11.1.

Example 4.11.1 Why is hash structure not the best choice for a search key on which range of queries are likely ? AU: May-06, Marks 8

Solution :

• A range query cannot be answered efficiently using a hash index, we will have to read all the buckets.

• This is because key values in the range do not occupy consecutive locations in the buckets, they are distributed uniformly and randomly throughout all the buckets.

Advantages of Static Hashing

(1) It is simple to implement.MI

(2) It allows speedy data storage.

Disadvantages of Static Hashing

There are two major disadvantages of static hashing:

1) In static hashing, there are fixed number of buckets. This will create a problematic situation if the number of records grow or shrink.

2) The ordered access on hash key makes it inefficient.

Open Hashing

The open hashing is a form of static hashing technique. When the collision occurs, that means if the hash key returns the same address which is already allocated by some data record, then the next available data block is used to enter new record instead of overwriting the old record. This technique is also called as linear probing. For example

Consider insertion of record 105 in the hash table below with the hash function h (key) mod 10.

The 105 is probed at next empty data block as follows -

Advantages:

1) It is faster technique.

2) It is simple to implement.

Disadvantages:

1) It forms clustering, as the record is just inserted to next free available slot.

2) If the hash table gets full then the next subsequent records can not be accommodated.