Hashing in DBMS: Static and Dynamic Hashing Techniques

By : Fiona Brown Fiona Brown
Hours Updated

⚡ Smart Summary

Hashing in DBMS is a technique that computes the disk location of a record directly from its key, without walking an index. A hash function maps search keys to data buckets, and static or dynamic hashing manages how those buckets grow.

  • ⚡ Core Idea: A hash function turns a key into a bucket address, so a record is found in one step rather than by index traversal.
  • 🪣 Data Bucket: The memory location, or unit of storage, where records with the same hash are placed.
  • 📌 Static Hashing: The bucket count is fixed, so a given key always maps to the same address.
  • 📈 Dynamic Hashing: Buckets are added and removed on demand as the data volume changes.
  • 💥 Collision: Two keys mapping to the same bucket, resolved by probing, rehashing, or chaining.
  • 🔍 Best For: Exact-match lookups on the search key, where hashing beats ordered indexing.
  • 📊 Trade-off: Ordered indexing wins for range queries; hashing wins for constant inserts and point lookups.
Read More

Static and Dynamic Hashing in DBMS

What is Hashing in DBMS?

In DBMS, hashing is a technique to directly search the location of desired data on the disk without using an index structure. The hashing method is used to index and retrieve items in a database, as it is faster to search for a specific item using the shorter hashed key instead of its original value. Data is stored in the form of data blocks whose address is generated by applying a hash function; the memory location where these records are stored is known as a data block or data bucket.

Why Do We Need Hashing?

Here are the situations in a DBMS where you need to apply the hashing method:

  • For a huge database structure, it is tough to search all the index values through all their levels and then reach the destination data block to get the desired data.
  • Hashing is used to index and retrieve items in a database, because it is faster to search for a specific item using the shorter hashed key than the original value.
  • Hashing is an ideal method to calculate the direct location of a data record on the disk without using an index structure.
  • It is also a helpful technique for implementing dictionaries.

Important Terminologies in Hashing

Here are important terminologies used in hashing:

  • Data bucket: data buckets are memory locations where the records are stored. It is also known as the unit of storage.
  • Key: a DBMS key is an attribute or set of attributes that helps you identify a row (tuple) in a relation (table).
  • Hash function: a mapping function that maps all the set of search keys to the address where the actual records are placed.
  • Linear Probing: a fixed interval between probes. In this method, the next available data block is used to enter the new record, instead of overwriting the older record.
  • Quadratic Probing: helps determine the new bucket address by adding the consecutive output of a quadratic polynomial to the starting value given by the original computation.
  • Hash index: the address of the data block. A hash function could be a simple mathematical function or a complex one.
  • Double Hashing: a method used in hash tables to resolve collisions by applying a second hash function.
  • Bucket Overflow: the condition of bucket overflow is called collision. This is a fatal stage for any static hash function.

Types of Hashing Techniques

There are mainly two types of hashing techniques in DBMS:

  1. Static Hashing
  2. Dynamic Hashing

The two differ mainly in whether the number of buckets is fixed, as the next two sections explain.

Static Hashing

In static hashing, the resultant data bucket address will always remain the same.

Therefore, if you generate an address for, say, Student_ID = 10 using the hashing function mod(3), the resultant bucket address will always be 1. So you will not see any change in the bucket address.

Therefore, in the static hashing method, the number of data buckets in memory always remains constant.

RELATED ARTICLES

Static Hash Functions

  • Inserting a record: when a new record needs to be inserted into the table, you generate an address for it using its hash key. Once the address is generated, the record is stored in that location.
  • Searching: when you need to retrieve the record, the same hash function is used to retrieve the address of the bucket where the data is stored.
  • Delete a record: using the hash function, you first fetch the record you want to delete, then remove the record from that address in memory.

Static hashing is further divided into:

  1. Open hashing
  2. Closed hashing

Open Hashing

In the open hashing method, instead of overwriting the older record, the next available data block is used to enter the new record. This method is also known as linear probing.

For example, A2 is a new record you want to insert. The hash function generates the address 222, but it is already occupied by another value. That is why the system looks for the next data bucket, 501, and assigns A2 to it.

How open hashing works with linear probing
How Open Hash Works

Closed Hashing

In the closed hashing method, when buckets are full, a new bucket is allocated for the same hash and the result is linked after the previous one.

Dynamic Hashing

Dynamic hashing offers a mechanism in which data buckets are added and removed dynamically and on demand. In this hashing method, the hash function helps you create a large number of values, and the structure grows or shrinks with the data. This makes it a strong fit for tables whose size cannot be predicted in advance, where static hashing would either waste space or overflow.

Difference Between Ordered Indexing and Hashing

Below are the key differences between indexing and hashing:

Parameters Ordered Indexing Hashing
Storing of address Addresses in memory are sorted according to a key value called the primary key. Addresses are always generated using a hash function on the key value.
Performance It can decrease as data increases, because the data is stored sorted and each insert, delete, or update reorders it. Performance is best with constant addition and deletion of data. For a huge database, hash file maintenance becomes costlier.
Use for Preferred for range retrieval, where data is retrieved for a particular range. Ideal for retrieving a particular record based on the search key, and only performs well when the hash function is on the search key.
Memory management Many unused data blocks arise from delete and update operations and cannot be released for re-use, so regular maintenance is required. In static and dynamic hashing, memory is always managed and bucket overflow is handled to extend static hashing.

In short, choose ordered indexing for range queries and hashing for exact-match lookups on the key.

What is Collision?

A hash collision is a state where the resultant hashes from two or more items in the data set wrongly map to the same place in the hash table.

How to Deal With a Hashing Collision

There are two techniques you can use to avoid a hash collision:

  1. Rehashing: this method invokes a secondary hash function, which is applied continuously until an empty slot is found where a record can be placed.
  2. Chaining: the chaining method builds a linked list of items whose keys hash to the same value. This method requires an extra link field at each table position.

FAQs

Static hashing keeps a fixed number of buckets, so it can overflow as data grows. Dynamic hashing adds and removes buckets on demand, so it adapts to changing data size without a full rebuild.

For range queries. Hashing scatters keys across buckets, so a between or greater-than query cannot walk them in order. An ordered index keeps keys sorted and is the better fit there.

A bucket overflows when more records hash to it than it can hold. In static hashing this is common as data grows, and it is handled by open addressing, chaining, or overflow buckets.

AI systems use hashing for fast feature lookup and for the hashing trick, which maps high-cardinality categories into a fixed vector. Similarity hashing also groups near-duplicate records efficiently.

Rehashing finds another open slot in the same table using a second function. Chaining keeps colliding records in a linked list attached to the bucket, so the table itself never fills a slot twice.

Summarize this post with: