CS210 · Annotated SlidesHashing — Hash Tables

Hashing · Annotated slides

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.

59 slides
0 asked in real exams
0 related to real exam questions
4 practice questions

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up

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

Exam weight Low

Slide 2: Hashing: basic plan

Exam weight Low

Hashing: compute an array index from the key; handle collisions.

Slide 3: Slide 3

Exam weight Low

Slide 4: Slide 4

Exam weight Low

Slide 5: Computing the hash function

Exam weight Low

Slide 6: Java’s hash code conventions

Exam weight High

Java: if x.equals(y) then x.hashCode() == y.hashCode().

🎯 How this can come up · 1 question

True / False

Two objects with the same hashCode must be equal.

Slide 7: Slide 7

Exam weight Low

Slide 8: Slide 8

Exam weight Low

Slide 9: Slide 9

Exam weight Low

Slide 10: Slide 10

Exam weight Low

Slide 11: Implementing hash code: integers, booleans, and doubles

Exam weight Low

Slide 12: Implementing hash code: strings

Exam weight Low

Slide 13: Implementing hash code: strings

Exam weight Low

Slide 14: Implementing hash code: user-defined types

Exam weight Low

Slide 15: Hash code design

Exam weight Low

Slide 16: Modular hashing

Exam weight Low

Modular hashing: (key.hashCode() & 0x7fffffff) % M.

Slide 17: Uniform hashing assumption

Exam weight Low

Slide 18: Uniform hashing assumption

Exam weight Low

Slide 19: Slide 19

Exam weight Low

Slide 20: Collisions

Exam weight Low

Collision: two keys hash to the same index.

Slide 21: Slide 21

Exam weight Low

Slide 22: Ian soso.am sswy www.oiwoi.is

Exam weight Low

Slide 23: Separate-chaining symbol table

Exam weight High

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

🎯 How this can come up · 1 question

MCQ

In separate chaining, colliding keys are stored:

Slide 24: Slide 24

Exam weight Low

Slide 25: Separate-chaining symbol table: Java implementation

Exam weight Low

Slide 26: Separate-chaining symbol table: Java implementation

Exam weight Low

Slide 27: Analysis of separate chaining

Exam weight Low

Slide 28: Resizing in a separate-chaining hash table

Exam weight Low

Slide 29: Deletion in a separate-chaining hash table

Exam weight Low

Slide 30: Slide 30

Exam weight Low

Slide 31: Symbol table implementations: summary

Exam weight Low

Slide 32: Slide 32

Exam weight Low

Slide 33: Collision resolution: open addressing

Exam weight High

Open addressing / linear probing: on collision, try the next slot (i + 1) until empty.

🎯 How this can come up · 1 question

MCQ

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

Slide 34: Slide 34

Exam weight Low

Slide 35: Linear-probing hash table demo

Exam weight Low

Slide 36: of collisions 6

Exam weight Low

Slide 37: Linear-probing hash table summary

Exam weight Low

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

Slide 38: Linear-probing symbol table: Java implementation

Exam weight Low

Slide 39: Linear-probing symbol table: Java implementation

Exam weight Low

Slide 40: Knuth's parking problem

Exam weight Low

Slide 41: Analysis of linear probing

Exam weight Low

Slide 42: Resizing in a linear-probing hash table

Exam weight Low

Slide 43: Deletion in a linear-probing hash table

Exam weight Low

Slide 44: ST implementations: summary

Exam weight High

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

🎯 How this can come up · 1 question

MCQ

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

Slide 45: Slide 45

Exam weight Low

Slide 46: War story: algorithmic complexity attacks

Exam weight Low

Slide 47: Algorithmic complexity attack on Java

Exam weight Low

Diversion: one-way hash functions

One-way hash function. "Hard" to find a key that will hash to a desired value (or two keys that hash to same value).

Ex. MD4, MD5, SHA-0, SHA-1, SHA-2, WHIRLPOOL, RIPEMD-160, ....

known to be insecure

String password = args[0]; MessageDigest sha1 = MessageDigest.getInstance("SHA1"); byte[] bytes = sha1.digest(password); /* prints bytes as hex string */

Applications. Digital fingerprint, message digest, storing passwords.

Caveat. Too expensive for use in ST implementations.

48

Exam weight Low

Slide 49: Separate chaining vs. linear probing

Exam weight Low

Slide 50: Hashing: variations on the theme

Exam weight Low

Slide 51: 66

Exam weight Low

Slide 52: 1

Exam weight Low

Slide 53: Slide 53

Exam weight Low

Slide 54: 13

Exam weight Low

Slide 55: of uselinear to collisionusing

Exam weight Low

Slide 56: 13 26

Exam weight Low

Slide 57: soultion

Exam weight Low

Slide 58: Slide 58

Exam weight Low

11

59

Exam weight Low