C DSALesson 64Free preview

C Hash Tables

This lesson is part of C · All levels

Summary

The hash table stores key pairs and values by converting the key into an array index through a hash function, so that the average access takes place very quickly approaching O(1). Since two different keys can produce the same index, collision handling is required through a chain of linked lists per bucket or open addressing that searches for the next empty slot. The quality of the hash function and load factor determines whether the performance remains good as the data increases.

Key points

The data position is determined by the capacity modulo of the table.
Collision is two keys falling into the same bucket; completed with chaining or open probing.
Load factor is the ratio of the amount of data to the capacity; when too high a table needs to be enlarged.
The average of the insert, search, and delete operations is close to O(1), but can be O(n) when all keys collide.
A good hash function should be quickly calculated, even, and always consistent for the same key.

Full lesson

Code examples and quizzes

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