Hash TablesLesson 20Free preview

DSA Hash Tables

This lesson is part of DSA · All levels

Summary

Hash tables store data as a pair of key values with the help of a hash function that converts the key into an index. With good hash function, average access is O(1) for insert, delete, and lookup. When two keys produce the same index, a collision occurs that is resolved by chaining or open addressing.

Key points

The hash function maps the keys to the index in the internal array
Average access to P1 is the worst in many collisions.
Collision is handled by chaining or open addressing
The quality of hash functions determines the distribution of data and performance

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.