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.

Dynamic Hashing in DBMS


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.


  • 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.