CSC148H1 Lecture Notes - Lecture 31: Birthday Problem, Hash Table
CSC148: Lecture 31: Chaining or Probing
References: The pictures can be found on the CSC148 website:
http://www.teach.cs.toronto.edu/~csc148h/winter
Chaining or Probing
- Couple of tactics for dealing with 2 different keys ending up at same index
o Chaining- keep a small list at that index (sometimes called bucket)
o Probing- explore, in a systematic way, until the next open index
- Either tactic has costs
- Keep collisions to a minimum by keeping the list partly empty
- Python dictionaries are implemented using has tables and probing
- The cost of collisions is kept small by enlarging the underlying list when necessary
o Cost of enlarging is amortized over many dictionary accesses
- Result = access to a dictionary element is 𝛩(1)
o The time it takes to access a list element
- 1 downside:
o Extra work required to order the keys or values
o What is their “natural” order?
Collisions: Linear Probing
1
CSC148H1 Full Course Notes
Verified Note
1 document
