Data StructuresHashingcore
Hash Table (Chaining)
Resolves collisions by hanging a linked list off each bucket. Lookup is constant time plus a walk down one chain, so the cost is governed by the load factor — keys per bucket — rather than by the table size. A small table here keeps collisions frequent enough to watch.
- Best
- O(1)
- Average
- O(1 + α)
- Worst
- O(n)
- Space
- O(n)