Hash Table
A hash table is a data structure that implements an associative array, also called a dictionary or simply map.
Time Complexity
Most operations in a hash table (read, create, update, delete) typically execute in Θ(1) time on average but can degrade to O(n) in the worst case due to hash collisions. 1
| Operation | Average | Worst |
|---|---|---|
| read | \(Θ(1)\) | \(O(n)\) |
| create | \(Θ(1)\) | \(O(n)\) |
| update | \(Θ(1)\) | \(O(n)\) |
| delete | \(Θ(1)\) | \(O(n)\) |
Space Complexity
| Space | Average | Worst |
|---|---|---|
| \(Θ(n)\) | \(O(n)\) |
Practice
- ↗ Leetcode 1742. Maximum Number of Balls in a Box
- ↗ Leetcode 3160. Find the Number of Distinct Colors Among the Balls
References
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). Massachusetts Institute of Technology. pp. 253–280. ISBN 978-0-262-03384-8.