Hash Tables

Search = O(1)

SSN or UM-D barcode

  10^9  vs  10^4
  used     needed

Library Example

• 1000 books
  
• 100 students (75% actually visit the library)

Collision Resolution

• linear probing
• rehashing
• chaining

O(N) can result if we are not careful

    = 2.0 (with 15% density)

Quadratic Probing

  key + IČ
  I  = 0, 1, 2, 3, 4, ...
  IČ = 0, 1, 4, 9, 16, ...

Heuristic Rule for Table Sizes = 4 * J + 1

Return to CIS 350 Index Page