CS210 · Hashing · Annotated SlidesHash Tables
Original
Overview

Hash Tables

Hash functions and Java’s hashCode conventions, modular hashing, the uniform hashing assumption, collisions, separate chaining, linear probing, resizing and deletion, and the cost summary.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 59 slides
  1. 1 A l g o r i t h m s A l g o r i t h m s
  2. 2 Hashing: basic plan
  3. 3 Slide 3
  4. 4 Slide 4
  5. 5 Computing the hash function
  6. 6 Java’s hash code conventions
  7. 7 Slide 7
  8. 8 key nv.me
  9. 9 Slide 9
  10. 10 away e
  11. 11 Implementing hash code: integers, booleans, and doubles
  12. 12 Implementing hash code: strings
  13. 13 Implementing hash code: strings
  14. 14 Implementing hash code: user-defined types
  15. 15 Hash code design
  16. 16 Modular hashing
  17. 17 Uniform hashing assumption
  18. 18 Uniform hashing assumption
  19. 19 Slide 19
  20. 20 Collisions
  21. 21 Slide 21
  22. 22 Ian soso.am sswy www.oiwoi.is
  23. 23 Separate-chaining symbol table
  24. 24 spin
  25. 25 Separate-chaining symbol table: Java implementation
  26. 26 Separate-chaining symbol table: Java implementation
  27. 27 Analysis of separate chaining
  28. 28 Resizing in a separate-chaining hash table
  29. 29 Deletion in a separate-chaining hash table
  30. 30 aiiiii.is
  31. 31 Symbol table implementations: summary
  32. 32 Slide 32
  33. 33 Collision resolution: open addressing
  34. 34 Slide 34
  35. 35 Linear-probing hash table demo
  36. 36 of collisions 6
  37. 37 Linear-probing hash table summary
  38. 38 Linear-probing symbol table: Java implementation
  39. 39 Linear-probing symbol table: Java implementation
  40. 40 Knuth's parking problem
  41. 41 Analysis of linear probing
  42. 42 Resizing in a linear-probing hash table
  43. 43 Deletion in a linear-probing hash table
  44. 44 ST implementations: summary
  45. 45 Slide 45
  46. 46 War story: algorithmic complexity attacks
  47. 47 Algorithmic complexity attack on Java
  48. 48 Diversion: one-way hash functions
  49. 49 Separate chaining vs. linear probing
  50. 50 Hashing: variations on the theme
  51. 51 66
  52. 52 1
  53. 53 Slide 53
  54. 54 13
  55. 55 of uselinear to collisionusing
  56. 56 13 26
  57. 57 soultion
  58. 58 Slide 58
  59. 59 11
Slide 1 / 59

A l g o r i t h m s A l g o r i t h m s

Slide 1: A l g o r i t h m s A l g o r i t h m s
Slide 2 / 59

Hashing: basic plan

Slide 2: Hashing: basic plan
Slide 3 / 59

Slide 3

Slide 3: Slide 3
Slide 4 / 59

Slide 4

Slide 4: Slide 4
Slide 5 / 59

Computing the hash function

Slide 5: Computing the hash function
Slide 6 / 59

Java’s hash code conventions

Slide 6: Java’s hash code conventions

Exam angle

PredictionQ1

Two objects with the same hashCode must be equal.

Slide 7 / 59

Slide 7

Slide 7: Slide 7
Slide 8 / 59

key nv.me

Slide 8: key nv.me
Slide 9 / 59

Slide 9

Slide 9: Slide 9
Slide 10 / 59

away e

Slide 10: away e
Slide 11 / 59

Implementing hash code: integers, booleans, and doubles

Slide 11: Implementing hash code: integers, booleans, and doubles
Slide 12 / 59

Implementing hash code: strings

Slide 12: Implementing hash code: strings
Slide 13 / 59

Implementing hash code: strings

Slide 13: Implementing hash code: strings
Slide 14 / 59

Implementing hash code: user-defined types

Slide 14: Implementing hash code: user-defined types
Slide 15 / 59

Hash code design

Slide 15: Hash code design
Slide 16 / 59

Modular hashing

Slide 16: Modular hashing
Slide 17 / 59

Uniform hashing assumption

Slide 17: Uniform hashing assumption
Slide 18 / 59

Uniform hashing assumption

Slide 18: Uniform hashing assumption
Slide 19 / 59

Slide 19

Slide 19: Slide 19
Slide 20 / 59

Collisions

Slide 20: Collisions
Slide 21 / 59

Slide 21

Slide 21: Slide 21
Slide 22 / 59

Ian soso.am sswy www.oiwoi.is

Slide 22: Ian soso.am sswy www.oiwoi.is
Slide 23 / 59

Separate-chaining symbol table

Slide 23: Separate-chaining symbol table

Notes

  1. Separate chaining: each slot holds a linked list of the keys that hash there.

Exam angle

PredictionQ1

In separate chaining, colliding keys are stored:

Slide 24 / 59

spin

Slide 24: spin
Slide 25 / 59

Separate-chaining symbol table: Java implementation

Slide 25: Separate-chaining symbol table: Java implementation
Slide 26 / 59

Separate-chaining symbol table: Java implementation

Slide 26: Separate-chaining symbol table: Java implementation
Slide 27 / 59

Analysis of separate chaining

Slide 27: Analysis of separate chaining
Slide 28 / 59

Resizing in a separate-chaining hash table

Slide 28: Resizing in a separate-chaining hash table
Slide 29 / 59

Deletion in a separate-chaining hash table

Slide 29: Deletion in a separate-chaining hash table
Slide 30 / 59

aiiiii.is

Slide 30: aiiiii.is
Slide 31 / 59

Symbol table implementations: summary

Slide 31: Symbol table implementations: summary
Slide 32 / 59

Slide 32

Slide 32: Slide 32
Slide 33 / 59

Collision resolution: open addressing

Slide 33: Collision resolution: open addressing

Exam angle

PredictionQ1

With linear probing, a key that hashes to a full slot goes to:

Slide 34 / 59

Slide 34

Slide 34: Slide 34
Slide 35 / 59

Linear-probing hash table demo

Slide 35: Linear-probing hash table demo
Slide 36 / 59

of collisions 6

Slide 36: of collisions 6
Slide 37 / 59

Linear-probing hash table summary

Slide 37: Linear-probing hash table summary

Notes

  1. Keep the table at most about half full for linear probing (α ≤ ½).

Slide 38 / 59

Linear-probing symbol table: Java implementation

Slide 38: Linear-probing symbol table: Java implementation
Slide 39 / 59

Linear-probing symbol table: Java implementation

Slide 39: Linear-probing symbol table: Java implementation
Slide 40 / 59

Knuth's parking problem

Slide 40: Knuth's parking problem
Slide 41 / 59

Analysis of linear probing

Slide 41: Analysis of linear probing
Slide 42 / 59

Resizing in a linear-probing hash table

Slide 42: Resizing in a linear-probing hash table
Slide 43 / 59

Deletion in a linear-probing hash table

Slide 43: Deletion in a linear-probing hash table
Slide 44 / 59

ST implementations: summary

Slide 44: ST implementations: summary

Notes

  1. Hashing: constant expected time for search/insert/delete; no ordered operations.

Exam angle

PredictionQ1

Expected cost of search in a well-sized hash table:

Slide 45 / 59

Slide 45

Slide 45: Slide 45
Slide 46 / 59

War story: algorithmic complexity attacks

Slide 46: War story: algorithmic complexity attacks
Slide 47 / 59

Algorithmic complexity attack on Java

Slide 47: Algorithmic complexity attack on Java
Slide 48 / 59

Diversion: one-way hash functions

Slide 48: Diversion: one-way hash functions
Slide 49 / 59

Separate chaining vs. linear probing

Slide 49: Separate chaining vs. linear probing
Slide 50 / 59

Hashing: variations on the theme

Slide 50: Hashing: variations on the theme
Slide 51 / 59

66

Slide 51: 66
Slide 52 / 59

1

Slide 52: 1
Slide 53 / 59

Slide 53

Slide 53: Slide 53
Slide 54 / 59

13

Slide 54: 13
Slide 55 / 59

of uselinear to collisionusing

Slide 55: of uselinear to collisionusing
Slide 56 / 59

13 26

Slide 56: 13 26
Slide 57 / 59

soultion

Slide 57: soultion
Slide 58 / 59

Slide 58

Slide 58: Slide 58
Slide 59 / 59

11

Slide 59: 11