February 03, 2020
Amitraj
Static Hashing
In static hashing, when a search-key value is provided, the hash function always computes the same address. For example, if mod-4 hash function is used, then it shall generate only 5 values. The output address shall always be same for that function. The number of buckets provided remains unchanged at all times.
Operations of Static Hashing -
Searching a record
-> When a record needs to be searched, then the same hash function retrieves the address of the bucket where the data is stored.
Insert a Record
-> When a new record is inserted into the table, then we will generate an address for a new record based on the hash key and record is stored in that location.
Delete a Record
-> To delete a record, we will first fetch the record which is supposed to be deleted. Then we will delete the records for that address in memory.
Update a Record
-> To update a record, we will first search it using a hash function, and then the data record is updated.
Bucket Overflow -
If we want to insert some new record into the file but the address of a data bucket generated by the hash function is not empty, or data already exists in that address. This situation in the static hashing is known as bucket overflow. The condition of bucket-overflow is known as collision.
->To overcome this situation, there are various methods:-
1. Open Hashing
When a hash function generates an address at which data is already stored, then the next bucket will be allocated to it. This mechanism is called as Linear Probing.
For example: suppose R3 is a new address which needs to be inserted, the hash function generates address as 112 for R3. But the generated address is already full. So the system searches next available data bucket, 113 and assigns R3 to it.
2. Close Hashing
When buckets are full, then a new data bucket is allocated for the same hash result and is linked after the previous one. This mechanism is known as Overflow chaining.
For example: Suppose R3 is a new address which needs to be inserted into the table, the hash function generates address as 110 for it. But this bucket is full to store the new data. In this case, a new bucket is inserted at the end of 110 buckets and is linked to it.
In static hashing, when a search-key value is provided, the hash function always computes the same address. For example, if mod-4 hash function is used, then it shall generate only 5 values. The output address shall always be same for that function. The number of buckets provided remains unchanged at all times.
Operations of Static Hashing -
Searching a record
-> When a record needs to be searched, then the same hash function retrieves the address of the bucket where the data is stored.
Insert a Record
-> When a new record is inserted into the table, then we will generate an address for a new record based on the hash key and record is stored in that location.
Delete a Record
-> To delete a record, we will first fetch the record which is supposed to be deleted. Then we will delete the records for that address in memory.
Update a Record
-> To update a record, we will first search it using a hash function, and then the data record is updated.
Bucket Overflow -
If we want to insert some new record into the file but the address of a data bucket generated by the hash function is not empty, or data already exists in that address. This situation in the static hashing is known as bucket overflow. The condition of bucket-overflow is known as collision.
->To overcome this situation, there are various methods:-
1. Open Hashing
When a hash function generates an address at which data is already stored, then the next bucket will be allocated to it. This mechanism is called as Linear Probing.
For example: suppose R3 is a new address which needs to be inserted, the hash function generates address as 112 for R3. But the generated address is already full. So the system searches next available data bucket, 113 and assigns R3 to it.
2. Close Hashing
When buckets are full, then a new data bucket is allocated for the same hash result and is linked after the previous one. This mechanism is known as Overflow chaining.
For example: Suppose R3 is a new address which needs to be inserted into the table, the hash function generates address as 110 for it. But this bucket is full to store the new data. In this case, a new bucket is inserted at the end of 110 buckets and is linked to it.
