CSE332 Section 4

Hashing!

Warm-Up

public AVLTree fillUniqueTree(List lst){

AVLTree avl = AVLTree();

for(int i = 0; i < lst.size(); i++){

avl.insert(lst.get(i), lst.get(i));

}

return avl;

}

​

What is the running time if the all elements in lst are unique?

What is the running time if all elements in lst are the same?

O(nlogn)

O(n)

Announcement

• Midterm: Wednesday, July 22, 2026, lecture time (9:40-10:40)
• Content: Everything up to AVL Trees (no hashing and sorting)
• Check the bottom of the Tasks section of the course website for Exam info and past exams
• Come to office hours if you have questions about anything!
• CC00: Getting to know each other
• Q4 credit by at latest July 17th (tomorrow!)
• Review session:

Monday July 20 at 5:00pm, Sieg 134

Hashing!!!

Hash Tables Review

Use a small array to store key-value pairs.

Hash function: converts key into an index of the array

• Hash functions should “scatter” the keys, behaving as if the keys are randomly assigned to indices
• What makes a good hash function?
• consistent, uniform, effective, efficient (remember what these mean?)

Store key at index given by the hash function

If two keys map to the same place (should be a very rare occurrence), we must do a collision resolution!

Good Hash Function Properties - Review

Each subproblem below describes a symptom of a hash function missing one of these properties. Write which missing property best explains the behavior described. (Recall: consistent, uniform, effective, efficient )

• No matter how many items I insert into my hash table, no key ever maps to index 7 : Uniform
• I inserted a key value pair into my hash table, then later did a find on that key. The find came back as unsuccessful even though I never called remove: Consistent
• My key objects have a field called name and a field called title. I find that regardless of the title field, two keys with the same name always map to the same index : Effective

​

Collision Resolution

Collision Resolution

A collision occurs when two keys map onto the same location in a hash table.

Impossible to eliminate since the number of possible keys exceeds table size.

1. Separate Chaining

All elements with keys that map to the same table location are kept in a linked list.

• Open Addressing

If the slot is occupied, we probe the next slot.

On the ith probe, we check the slot with index (h(key) + f(i)) % TableSize.

Linear Probing: f(i) = i

Quadratic Probing: f(i) = i^2

Double Hashing: f(i) = i ᐧ g(key)

There are multiple ways to resolve conflicts:

Problem 1a

• Linear Probing
• ith probe: (h(key) + i) % TableSize

​

Problem 1a: insertion

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

Linear Probing

ith probe: (h(key) + i) % TableSize

Problem 1a: insert 7

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

(h(7) + 0) % 10 = 7

​

​

​

Linear Probing

ith probe: (h(key) + i) % TableSize

Problem 1a: insert 9

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

(h(9) + 0) % 10 = 9

​

​

​

Linear Probing

ith probe: (h(key) + i) % TableSize

Problem 1a: insert 48

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

(h(48) + 0) % 10 = 8

​

​

​

​

Linear Probing

ith probe: (h(key) + i) % TableSize

Problem 1a: insert 8

Insert 7, 9, 48, 8, 37, 57 into an empty table.

(h(8) + 0) % 10 = 8

​

​

​

​

(h(8) + 1) % 10 = 9

​

​

(h(8) + 2) % 10 = 0

​

​

​

​

Linear Probing

ith probe: (h(key) + i) % TableSize

Problem 1a: insert 37

(h(37) + 3) % 10 = 0

(h(37) + 2) % 10 = 9

(h(37) + 1) % 10 = 8

(h(37) + 0) % 10 = 7

(h(37) + 4) % 10 = 1

​

​

​

​

Insert 7, 9, 48, 8, 37, 57 into an empty table.

Linear Probing

ith probe: (h(key) + i) % TableSize

Problem 1a: insert 57

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

(h(57) + 0) % 10 = 7

Linear Probing

ith probe: (h(key) + i) % TableSize

(h(57) + 1) % 10 = 8

(h(57) + 2) % 10 = 9

(h(57) + 3) % 10 = 0

(h(57) + 4) % 10 = 1

(h(57) + 5) % 10 = 2

Problem 1a: deletion

Delete 37, 7, 57 from the table.

Linear Probing

ith probe: (h(key) + i) % TableSize

Problem 1a: delete 37

(h(37) + 0) % 10 = 7

​

Linear Probing

ith probe: (h(key) + i) % TableSize

Delete 37, 7, 57 from the table.

(h(37) + 1) % 10 = 8

(h(37) + 2) % 10 = 9

(h(37) + 3) % 10 = 0

(h(37) + 4) % 10 = 1

Problem 1a: delete 7

(h(7) + 0) % 10 = 7

​

Linear Probing

ith probe: (h(key) + i) % TableSize

Delete 37, 7, 57 from the table.

Problem 1a: delete 7

(h(57) + 0) % 10 = 7

Linear Probing

ith probe: (h(key) + i) % TableSize

Delete 37, 7, 57 from the table.

(h(57) + 1) % 10 = 8

(h(57) + 2) % 10 = 9

(h(57) + 3) % 10 = 0

(h(57) + 4) % 10 = 1

(h(57) + 5) % 10 = 2

Experiment on 1a

What happens if we now try to remove a

non-existent element (e.g. 17) from the table?

Experiment: delete 17

(h(17) + 0) % 10 = 7

Linear Probing

ith probe: (h(key) + i) % TableSize

Delete 17 from the table.

(h(17) + 1) % 10 = 8

​

(h(17) + 2) % 10 = 9

(h(17) + 3) % 10 = 0

(h(17) + 4) % 10 = 1

(h(17) + 5) % 10 = 2

(h(17) + 6) % 10 = 3

We have reached an empty slot, but have not encountered 17. Therefore, it must not exist.

Problem 1b

• Quadratic Probing
• ith probe: (h(key) + i²) % TableSize

​

Problem 1b: insertion

Insert 7, 9, 48, 8, 37, 57 into an empty table.

Quadratic Probing

ith probe: (h(key) + i²) % TableSize

Problem 1b: insert 7

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

(h(7) + 0²) % 10 = 7

​

​

​

Quadratic Probing

ith probe: (h(key) + i²) % TableSize

Problem 1b: insert 9

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

(h(9) + 0²) % 10 = 9

​

​

​

Quadratic Probing

ith probe: (h(key) + i²) % TableSize

Problem 1b: insert 48

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

(h(48) + 0²) % 10 = 8

​

​

​

​

Quadratic Probing

ith probe: (h(key) + i²) % TableSize

Problem 1b: insert 8

Insert 7, 9, 48, 8, 37, 57 into an empty table.

(h(8) + 0²) % 10 = 8

​

​

​

​

(h(8) + 1²) % 10 = 9

​

​

(h(8) + 2²) % 10 = 2

​

​

​

​

Quadratic Probing

ith probe: (h(key) + i²) % TableSize

Problem 1b: insert 37

(h(37) + 2²) % 10 = 1

(h(37) + 1²) % 10 = 8

(h(37) + 0²) % 10 = 7

Insert 7, 9, 48, 8, 37, 57 into an empty table.

Quadratic Probing

ith probe: (h(key) + i²) % TableSize

Problem 1b: insert 57

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

(h(57) + 0²) % 10 = 7

Quadratic Probing

ith probe: (h(key) + i²) % TableSize

(h(57) + 1²) % 10 = 8

(h(57) + 2²) % 10 = 1

(h(57) + 3²) % 10 = 6

Problem 1c

• Separate Chaining
• Use a linked list for each slot

Problem 1c: insertion

Insert 7, 9, 48, 8, 37, 57 into an empty table.

Separate Chaining

Use a linked list for each slot

​

Problem 1c: insert 7

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

Separate Chaining

Use a linked list for each slot

​

(h(7) + 0) % 10 = 7

​

​

​

Problem 1c: insert 9

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

Separate Chaining

Use a linked list for each slot

​

(h(9) + 0) % 10 = 9

​

​

​

Problem 1c: insert 48

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

Separate Chaining

Use a linked list for each slot

​

(h(48) + 0) % 10 = 8

​

​

​

Problem 1c: insert 8

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

Separate Chaining

Use a linked list for each slot

​

(h(8) + 0) % 10 = 8

​

​

​

Problem 1c: insert 37

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

Separate Chaining

Use a linked list for each slot

​

(h(37) + 0) % 10 = 7

​

​

​

Problem 1c: insert 57

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

​

Separate Chaining

Use a linked list for each slot

​

(h(57) + 0) % 10 = 7

​

​

​

Problem 2

• Consistent: equal keys hash to the same integer
• Effective: the selection of an integer should behave has if it was done at random

​

For each hash function, determine which property it lacks and describe why it doesn’t have that property.

​

Problem 2a

Missing Property? Effective

Justification: changing only accountNum would result in a different object that hashes to the same value.

Problem 2b

Missing Property: Effective

Justification: swapping routingNum and accountNum would result in a different object that hashes to the same value.

​

Problem 2c

Missing Property: Consistent

Justification: balance is not relevant for determining equivalence (based on the equals() method), so we may have equal objects that hash to different values.

Problem 3

Problem 3a

• On the ith probe, we check the slot with index �(h(key) + i ᐧ g(key)) % TableSize.
• The first hash function h determines the location where we initially try to place the item.
• If there is a collision, then the second hash function g determines the probing step size �(i.e. 1 ᐧ g(key), 2 ᐧ g(key), … distance away from the initial location).

Describe double hashing.

​

Problem 3b

• Double Hashing
• ith probe: (h(key) + i ᐧ g(key)) % TableSize

Problem 3b: insertion

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

h(k) = k % 10

g(k) = 1 + (k % 9)

​

Double Hashing

ith probe: (h(key) + i * g(key)) % TableSize

Problem 3b: insert 7

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

h(k) = k % 10

g(k) = 1 + (k % 9)

​

Double Hashing

ith probe: (h(key) + i * g(key)) % TableSize

Problem 3b: insert 9

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

h(k) = k % 10

g(k) = 1 + (k % 9)

​

Double Hashing

ith probe: (h(key) + i * g(key)) % TableSize

Problem 3b: insert 48

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

h(k) = k % 10

g(k) = 1 + (k % 9)

​

Double Hashing

ith probe: (h(key) + i * g(key)) % TableSize

Problem 3b: insert 8

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

h(k) = k % 10

g(k) = 1 + (k % 9)

​

Double Hashing

ith probe: (h(key) + i * g(key)) % TableSize

Problem 3b: insert 37

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

h(k) = k % 10

g(k) = 1 + (k % 9)

​

Double Hashing

ith probe: (h(key) + i * g(key)) % TableSize

Problem 3b: insert 57

Insert 7, 9, 48, 8, 37, 57 into an empty table.

​

h(k) = k % 10

g(k) = 1 + (k % 9)

​

Double Hashing

ith probe: (h(key) + i * g(key)) % TableSize

Problem 3c

• If the table is more than half full (i.e. load factor > 0.5), then we are not guaranteed to find a location to insert an item.
• Suffers from secondary clustering since items that initially hash to the same location resolve the collision identically.

List two disadvantages of quadratic probing.

​

​

​

Describe how double hashing fixes one of these disadvantages.

​

• A good second hash function prevents secondary clustering since items that initially hash to the same location will likely resolve the collision differently.
• Items that have the same value for the first hash function f, will likely have different values for the second hash function g, leading to different probing step sizes.

Problem 3d

Compare open addressing with separate chaining.

Thank You!