Back to Data Structures

Study notes

LearnExams

Qwestrum Engineering360 · IT & Software · Data Structures

Hashing Techniques

Hashing maps keys to table slots via a hash function for near O(1) average lookup; collisions (two keys to one slot) are resolved by chaining or open addressing, and performance degrades as the load factor rises.
Exam tip: keep SI units consistent end-to-end, write the governing relation symbolically before substituting, and sanity-check magnitude and sign.

Key formulas & points

Skim these first — then read the full notes below.

  • Collision resolution: chaining or open addressing
  • Linear probing risks primary clustering
  • Universal hashing defends against adversarial keys

Topic details

Introduction

This topic covers hash tables. You design hash functions (division and multiplication methods), compare chaining against open-addressing schemes like linear and quadratic probing, compute the load factor, and reason about how it drives expected probe length and when to resize.

Key relations & formulas

h(k)=kmodmh(k) = k mod m
(division method)
h(k)=floor(m×(kAmod1))h(k) = floor(m \times (kA mod 1))
(multiplication method)

Formulas (Indian textbook notation)

  • loadfactorα=nm;averagechainlength∝αload factor \alpha = \frac{n}{m}; average chain length ∝ \alpha

Notation and sign conventions

Relation 1 —
hh
h(k)=kmodmh(k) = k mod m
(division method)
Write this relation with symbols exactly as in Schaum Ds — Standard reference before substituting numbers. Examiners award partial marks for a correct setup even when arithmetic slips.
Relation 2 —
hh
h(k)=floor(m×(kAmod1))h(k) = floor(m \times (kA mod 1))
(multiplication method)
Write this relation with symbols exactly as in Schaum Ds — Standard reference before substituting numbers. Examiners award partial marks for a correct setup even when arithmetic slips.
Relation 3 —
loadfactorα=nm;averagechainlength∝αload factor \alpha = \frac{n}{m}; average chain length ∝ \alpha

Formulas (Indian textbook notation)

  • loadfactorα=nm;averagechainlength∝αload factor \alpha = \frac{n}{m}; average chain length ∝ \alpha
Write this relation with symbols exactly as in Schaum Ds — Standard reference before substituting numbers. Examiners award partial marks for a correct setup even when arithmetic slips.

Concept in depth

A hash table trades a little memory for near-constant lookup by computing a slot directly from the key. Because the key space is larger than the table, collisions are inevitable, and the resolution strategy defines behaviour: chaining stores colliding keys in a per-slot list, so cost grows gracefully with load factor, while open addressing keeps everything in the array by probing to the next slot, which is cache-friendly but suffers clustering that lengthens probe sequences. The load factor α is the key performance dial — beyond about 0.7 for open addressing, probe lengths climb sharply, prompting a resize and rehash. A good hash function spreads keys uniformly to keep chains short.

Assumptions and validity limits

State assumptions explicitly before using any relation for hashing techniques — steady state, uniform properties, linear elastic material, ideal gas, incompressible flow, etc., as applicable.
Wrong assumptions invalidate the entire solution even when the formula is correct. In Data Structures viva and GATE descriptive questions, listing valid assumptions often earns separate marks.

Step-by-step problem approach

1. Read the question and list given data with SI units (common in Data Structures papers).
2. Draw a neat labelled diagram where applicable — examiners in Indian universities award diagram marks even when arithmetic slips.
3. Identify which relation from this topic applies to hashing techniques.
4. Use equation 1:
hh
.
5. Use equation 2:
hh
.
6. Substitute values, compute, and verify units and sign (direction).
7. State conclusion in one line — e.g. safe/unsafe, stable/unstable, feasible/infeasible.

Applications & exam relevance

Hashing Techniques appears in interviews and systems programming. In Indian it software curricula this topic is tested because it connects theory to organising data for efficient algorithms.
GATE and semester exams often combine hashing techniques with earlier units — revise prerequisites before attempting mixed problems.
Industry interview panels sometimes ask: "Where did you use hashing techniques?" — answer with a lab, mini-project, or plant visit example if possible.

Common mistakes in exams

Students pick a poor table size for the division method (a power of two wastes high bits; a prime is safer), confuse chaining with open addressing, and ignore load-factor limits so open addressing thrashes. Forgetting that deletion in open addressing needs tombstones is a subtle error.

Quick revision checklist

Before attempting hashing techniques problems, confirm you can:
1. Collision resolution: chaining or open addressing
2. Linear probing risks primary clustering
3. Universal hashing defends against adversarial keys
Revise the solved examples in Schaum Ds — Standard reference and one previous-year GATE or university paper for this unit.

Worked examples

Try the problem first — open the solution when you are ready to check.

Load factor check

Problem

A hash table has size m = 20 and stores n = 14 keys. Compute the load factor and comment.

Solution

α = n/m = 14/20 = 0.7. This is acceptable for chaining but near the practical ceiling for open addressing, where probe cost rises steeply beyond 0.7.

Conceptual check — Hashing Techniques

Problem

In a Data Structures semester or GATE paper you are asked: "State the main assumption, the governing relation, and one practical consequence of hashing techniques." What should a complete answer include?

Exams & GATE

Compare chaining versus open addressing for GATE hashing questions.

📖 Standard books (India)

  • Schaum Ds — Standard reference

    Read: Syllabus unit

    Referenced in Indian B.Tech syllabus

Explore related topics

See real it & software careers

After exams and interviews, see how engineers actually built careers — milestones and decisions from people in the field.

Browse IT & Software journeysPlan your path