CSE 163

Hashing�

Suh Young Choi�

🎶 Listening to: Tom Day

💬 Before Class: What’s your favorite cold food?

Announcements

Project Deliverables open now on Gradescope

• Make sure you have access!
• Also linked in the Project module on Ed
• No late submissions or resubs available!

​

Checkpoint 7 due tonight (last one of the quarter!)

​

Last resubmission window closes tomorrow

• Course evals have 44% completion—it’s getting close!
• Bonus period? Maybe!

2

This Time

• How Hashing Works
• Relevance to Sets and Dictionaries

Previously…

• Data Structures
• Algorithmic Efficiency
• Big-O

3

Runtime Recap

Counting Steps:

​

​

​

​

​

​

​

Think of growth rates in terms of the input size (n)

​

4

• Blocks of code
• Sum of all the lines
• Loops
• Number of steps in body multiplied by number of times loop runs
• Function call
• The number of steps in its body

• Largest term dominates when n is really large

Data Structures

• List: Series of values, each with an index
• list.append(v) O(1)
• v in list O(n)
• list[i] O(1)�
• Set: Collection of unique values, no sense of “order”
• set.add(v) O(1)
• v in set O(1)
• set[i] Not allowed�
• Dictionary: Like a set, but maps distinct keys to values
• dict[k] = v O(1)
• k in dict O(1)
• dict[k] O(1)

5

How can the set/dictionary have run-times that don’t depend on the number of elements in the data structure?

Set of Ints

• Hash Function: h(v) = v % 10

6

nums = set()

nums.add(11) # 11 % 10 == 1

nums.add(49) # 49 % 10 == 9

nums.add(24) # 24 % 10 == 4

nums.add(7) # 7 % 10 == 7

print(49 in nums) # True

print(5 in nums) # False

​

11

7

49

24

Chained Hashing

• If we experience a collision, just store both values at that index
• Under some reasonable assumptions, these buckets will be small compared to the size of the whole set of items
• Care about the load-factor (num items / size of table)
• If the load-factor is too high, these buckets will be big
• Can rehash into a larger table to lower load-factor

7

Hash Functions

• Our hash table can handle collisions, but we still want to keep the number of collisions low (otherwise buckets are large)
• Integers are relatively easy to hash, but what about strings?
• Each object can implement a __hash__ method
• Write code to turn your object into an int for indexing�
• Requirements of hash function
• Needs to return a number
• Be “consistent”
• What makes a good hash function
• Should minimize the number of collisions
• Should “look random” to maximize spread of values

8

Hashing in Practice

• Hashing and equality are deeply related
• If two values are equal, they must hash to same value
• If you implement __eq__ and __hash__,�they need to be consistent
• Generally, people let Python make a good hash function

​

9

class Example:

def __init__(self, a, b, c):

# Initialize _a, _b, _c

def __eq__(self, other):

return self._a == other._a \

and self._b = other._b

def __hash__(self):

return hash((self._a, self._b))

​

Group Work:

Best Practices

When you first working with this group:

• Introduce yourself!
• If possible, angle one of your screens so that everyone can discuss together

​

Tips:

• Starts with making sure everyone agrees to work on the same problem
• Make sure everyone gets a chance to contribute!
• Ask if everyone agrees and periodically ask each other questions!
• Call TAs over for help if you need any!

10

Before Next Time

• Complete Lesson 24
• Remember not for points, but do go towards Checkpoint Tokens
• Checkpoint 7 due tonight
• Project Report/Code/Video due Wednesday
• Fill out the course eval!

Next Time

• Indexing, revisited
• Decision trees, revisited

​

11