DBMS Topics
HubUnit 1 — Introduction to DBMS & Entity-Relationship ModelAdvantages and Disadvantages of DBMSAggregationCharacteristics of DBMSData IndependenceData ModelsDatabase Users and AdministratorsDBMS LanguagesER DiagramsEntity-Relationship ER ModelIntroduction to DBMSKeys in DBMSRelationships and CardinalitySchema and InstanceSpecialization and GeneralizationUnit 1 Summary — Introduction to DBMS & ER ModelThree-Level Architecture ANSI/SPARC ArchitectureWeak Entity SetUnit 2 — Relational Model & SQLConstraints in SQLCursorsDCL and TCL CommandsDDL CommandsDML CommandsDomain Relational Calculus DRCFunctions and Stored ProceduresJoins in SQLNested Queries SubqueriesRelational AlgebraRelational CalculusRelational ModelSQL IntroductionUnit 2 Summary — Relational Model & SQLTriggers in SQLTuple Relational Calculus TRCViews in SQLArmstrong's Axioms & Closure of AttributesBoyce-Codd Normal Form BCNFClosure of AttributesDependency PreservationFifth Normal Form 5NFFirst Normal Form 1NFFourth Normal Form 4NFFunctional DependencyLossless DecompositionMultivalued DependencyNormal Forms — OverviewNormalization — IntroductionSecond Normal Form 2NFUnit 3 Summary — NormalizationThird Normal Form 3NFUnit 4 — Transaction Management & Concurrency ControlACID PropertiesCheckpointsConcurrency Control & SerializabilityDeadlock in DBMSLock-Based Protocols & Two-Phase LockingLog-Based RecoveryRecovery SystemSerializabilityShadow PagingUnit 4 Summary — Transaction Management & Concurrency ControlTimestamp-Based ProtocolTransaction ManagementTransaction StatesTwo-Phase Locking 2PLUnit 5 — Storage & IndexingB+ TreeB-TreeCost EstimationDynamic HashingFile OrganizationHashing TechniquesIndexing — IntroductionMulti-Level IndexingQuery OptimizationQuery ProcessingSingle-Level IndexingStatic HashingUnit 5 Summary — Storage & IndexingUnit 6 — Advanced Topics in DBMSBig Data and DBMSCloud DatabaseData MiningData WarehouseDatabase SecurityDistributed DatabaseDistributed Query ProcessingDistributed DBMS Architecture, Fragmentation & ReplicationMongoDB — IntroductionNoSQL DatabaseReplication in Distributed DatabasesUnit 6 Summary — Advanced Topics in DBMSViva Voce — DBMSImportant Viva Questions — DBMSInterview Questions — DBMSViva Answers — DBMSDBMS Multiple Choice Questions MCQsDBMS Lab Programs
Hashing Techniques
Last Updated : 21 May, 2026
Hashing is a technique for direct address computation — a hash function maps a key value directly to a bucket address disk block where the record is stored. It avoids the
Unit 5218 words7 headingsTables includedExamples included
What is Hashing?
Hashing is a technique for direct address computation — a hash function maps a key value directly to a bucket address (disk block) where the record is stored. It avoids the need for traversing an index structure.
Key K
│
▼
Hash Function h(K)
│
▼
Bucket Address → Read that disk block → Find Record
Access time: O(1) — direct computation, no traversal
Hash Function
A hash function h maps search-key values to a set of bucket addresses (integers 0 to B−1):
h: Key Space → {0, 1, 2, ..., B-1}
Common hash functions:
h(K) = K mod B (division / modulo method)
h(K) = ⌊B × (K × A mod 1)⌋ (multiplication method, A ≈ 0.618)
h(K) = sum of ASCII values mod B (for string keys)
Example
| B = 5 buckets, Keys | 101, 102, 103, 204, 305 |
| h(101) = 101 mod 5 = 1 | Bucket 1 |
| h(102) = 102 mod 5 = 2 | Bucket 2 |
| h(103) = 103 mod 5 = 3 | Bucket 3 |
| h(204) = 204 mod 5 = 4 | Bucket 4 |
| h(305) = 305 mod 5 = 0 | Bucket 0 |
| Bucket 0 | [E305] |
| Bucket 1 | [E101] |
| Bucket 2 | [E102] |
| Bucket 3 | [E103] |
| Bucket 4 | [E204] |
Collisions
A collision occurs when two different keys hash to the same bucket:
h(K) = K mod 5:
h(101) = 1 → Bucket 1
h(106) = 1 → Bucket 1 (COLLISION! Both map to bucket 1)
Collision Resolution
1. Open Addressing (within buckets):
- Each bucket has multiple slots
- If a collision occurs, place the record in the same bucket (multiple records per bucket)
- If bucket is full → use overflow chaining (linked list of overflow blocks)
Bucket 1: [E101][E106] ← both fit in same bucket
If bucket fills: [E101][E106] → [overflow block: E211]
2. Chaining:
- Each bucket is a linked list of records or overflow pages
- Unlimited records per bucket in theory
Types of Hashing
Hashing
├── Static Hashing
│ └── Fixed number of buckets; good when data size is known
│
└── Dynamic Hashing
├── Extendible Hashing → directory doubles in size
└── Linear Hashing → buckets added one at a time
Hashing vs. Indexing (B+ Tree)
| Feature | Hashing | B+ Tree Index |
|---|---|---|
| Equality search | O(1) — excellent | O(log n) |
| Range query | Poor (no order) | Excellent (sorted) |
| Insertion | O(1) avg | O(log n) |
| Storage | May waste space (empty buckets) | Space-efficient |
| Ordering | No | Yes |
| Skew handling | Can be poor | Handles well |
Use hashing when: Only equality searches needed (e.g., WHERE emp_id = 105) Use B+ Tree when: Range queries needed (e.g., WHERE salary BETWEEN 50000 AND 80000)
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Hashing Techniques.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this DBMS topic.
Search Terms
dbms, database management system, database notes, sql, unit, hashing, techniques, hashing techniques
Related DBMS Topics
Continue learning this concept
Unit 5Dynamic HashingStatic hashing suffers when data size changes unpredictably:Unit 5Static HashingStatic hashing uses a fixed number of buckets B. The hash function always maps keys to the same set of B buckets. The number of buckets is chosen at design time and does Unit 5Unit 5 — Storage & IndexingThis unit covers how databases physically store and efficiently retrieve data. Understanding storage structures and indexing is essential for database performance tuning Unit 5B+ TreeA B+ Tree is a variation of the B-Tree where:Unit 5B-TreeA B-Tree Balanced Tree is a self-balancing, sorted tree data structure that maintains sorted data and allows searches, insertions, and deletions in Olog n time. It is desUnit 5Cost EstimationCost estimation is the process of predicting the execution cost of a query plan without actually running it. The query optimizer uses cost estimates to compare alternativ