Dynamic Hashing

The problem with static hashing is that it does not expand or shrink dynamically as the size of the database grows or shrinks. Dynamic hashing provides a mechanism in which data buckets are added and removed dynamically and on-demand. Dynamic hashing is also known as extendible hashing.

Hash function, in dynamic hashing, is made to produce a large number of values and only a few are used initially.

ORGANIZATION

The prefix of an entire hash value is taken as a hash index. Only a portion of the hash value is used for computing bucket addresses. Every hash index has a depth value to signify how many bits are used for computing a hash function. These bits can address 2n buckets. When all these bits are consumed − that is, when all the buckets are full − then the depth value is increased linearly and twice the buckets are allocated.

OPERATION

• Querying − Look at the depth value of the hash index and use those bits to compute the bucket address.
• Update − Perform a query as above and update the data.
• Deletion − Perform a query to locate the desired data and delete the same.
• Insertion − Compute the address of the bucket
  • If the bucket is already full.
    • Add more buckets.
    • Add additional bits to the hash value.
    • Re-compute the hash function.
  • Else
    • Add data to the bucket,
  • If all the buckets are full, perform the remedies of static hashing.

Hashing is not favorable when the data is organized in some ordering and the queries require a range of data. When data is discrete and random, hash performs the best.

Hashing algorithms have high complexity than indexing. All hash operations are done in constant time.

www.techglads.com