Java
1.Ecosystem
Your task in this assignment to
add two new types of Mover to Wanderer/Seeker. It is up to you how these Movers should behave — feel free to get as creative as you want with this one. The only constraint is that they must in some way behave differently from either Wanderers or CloseSeekers.
Provided that you have implemented Wanderer/Seeker v2 correctly, this assignment should be relatively short — in fact, if you’ve implemented Wanderer/Seeker v2 right, you can complete this assignment without changing your classes from that assignment (although, depending on the modifications you make, you may have to add additional methods to your mediator object).
2.Palindrome
Write a method that takes one string as a parameter and returns a boolean indicating whether or not it’s a palindrome. Consult the slides for day 20 for a pseudocode overview.
3.Building a MarkovTable
Create a class named MarkovTable. This class should have a method called readFile that takes a String as a parameter (indicating the name of the file to be opened) and returns a boolean (indicating whether or not the attempt to read a file was successful).
The class should have a private member variable of type HashMap
Here is how you should populate this HashMap:
· Each unique word in the file should be a key in the HashMap.
· Consider any string of non-whitespace characters as one “word” — so for example “Henceforth” “Henceforth,” and “henceforth” are all different words
· The ArrayList associated with each key should store every word that follows that word.
· When you reach the last word in the file, you should treat the first word in the file as its successor.
For example, if the file consisted of the string:
one fish two fish red fish blue fish
your HashMap for it would hold five items:
Key value
one [fish]
two [fish]
red [fish]
blue [fish]
fish [two, red, blue, one]
Notice that one is considered to be a successor of fish, because “fish” is both the first and last word of the file.
Your class should also have a toString method that prints the contents of the HashMap in the format above.
4.Recursive search
Use recursion to implement one of the search algorithms shown in this adorable video
For full credit, implement Slowcoach Slade’s algorithm. For 9 points, implement Speedy Spencer’s algorithm. Please do not implement Bozo’s algorithm for this assignment.
Note: your implementation MUST use recursion
CIS36A day
2
0
Recursion, Hashing, Big O notation
AGENDA
Note: this is probably the “mathiest”
class session of all semester. This
material will be useful regardless of
whichever programming language you
work in.
Computer science isn’t about learning
language syntax. It’s about learning and
applying tools for analysis like the ones
we’ll discuss today.
•
Big O notation
• Recursion in Java
• Fibonacci sequence by
recursion
• Recursive binary search
• More on hashing
• The .hashCode() method
• .equals() / .hashCode() contract
Big O notation
• Consider what it takes to add an item to the front of a sorted array:
4 9 13 31 137 1848 1905 1917 1968 2021
(our sorted array)
1871
Big O notation
(our sorted array)
4 9 13 31 137 1848 1905 1917 1968 20211871
6Say we wanted
to add an item
near the start of
the array…
Big O notation
(our sorted array)
4 9 13 31 137 1848 1905 1917 1968 20211871
6We can see it’s
supposed to go
right here…
Big O notation
(our sorted array)
4 9 13 31 137 1848 1905 1917 1968 20211871
6We can see it’s
supposed to go
right here…
…. but to add it there, we have to shift every other element down.
Big O notation
However many operations it takes to shift one array element, it takes
that number of operations times the number of elements in the array
to shift the entire array.
4 9 13 31 137 1848 1905 1917 1968 202118716
Big O notation
However many operations it takes to shift one array element, it takes
that number of operations times the number of elements in the array
to shift the entire array.
4 9 13 31 137 1848 1905 1917 1968 202118716
Call the number of elements in the array n. In the worst-case scenario (we’re
inserting at the very start of the list) it takes:
n * (however many operations)
to insert an item
Big O notation
• n * (however many operations) isn’t bad when n is small
• In this case, n is 12 – not so bad, not even if it takes a thousand operations
to shift one element (it doesn’t).
• But what if n were 1,000,000,000,000? No matter how few operations it
takes to shift an array element (even just 1), it’s going to take a very long
time to shift the whole array.
4 9 13 31 137 1848 1905 1917 1968 202118716
(assume this array is very long)
Big O notation
• Big O notation is how we represent how the speed of an algorithm
changes as the number of items we’re working on gets large.
• (Or, slightly more formally, as the number of items approaches infinity)
• Say it takes 137 operations to shift one array element. We see that it
takes 137 * n operations to shift the whole array
4 9 13 31 137 1848 1905 1917 1968 202118716
Big O notation
• Say it takes 137 operations to shift one array element. We see that it
takes 137 * n operations to shift the whole array.
• Here is 137 * n as n gets large
Big O notation
• Consider the other data structure we’ve: the LinkedList
4
6
9
13 31
Big O notation
• Each list element consists of the value, plus the address of the next
element in the list.
• Inserting an element at the start of a linked list isn’t dependent upon
the number of items in the list.
4
6
9
13 31
Big O notation
• Inserting an element at the start of a linked list isn’t dependent upon
the number of items in the list.
• Just make the new element’s pointer point to the first element in the list.
• No shifting required!
4
6
9
13 31
2
Big O notation
• Inserting an element at the start of a linked list isn’t dependent upon
the number of items in the list.
• Just make the new element’s pointer point to the first element in the list.
• No shifting required!
4
6
9
13 31
2
Big O notation
• Inserting an element at the start of a linked list isn’t dependent upon
the number of items in the list.
• Just make the new element’s pointer point to the first element in the list.
• No shifting required!
• Because the operation doesn’t depend on the number of items, this
is called a constant time operation.
4
6
9
13 31
2
Big O notation
• Because the operation doesn’t depend on the number of items, this
is called a constant time operation.
• Let’s say our code to change an item’s link were wildly inefficient.
Let’s say it took 10,000 operations to do it.
• (it doesn’t – but let’s pretend it does)
4
6
9
13 31
2
10,000
operations!
Big O notation
• Let’s say our code to change an item’s link were wildly inefficient.
Let’s say it took 10,000 operations to do it.
• (it doesn’t – but let’s pretend it does)
• Let’s graph the time it takes to add an item to a LinkedList vs the
time it takes to add an item to an array, as the number of items
already in the list or array gets large:
The blue line is 137 * n
The red line at the bottom is 10000
Big O notation
• Let’s say our code to change an item’s link were wildly inefficient.
Let’s say it took 10,000 operations to do it.
• (it doesn’t – but let’s pretend it does)
• Let’s graph the time it takes to add an item to a LinkedList vs the
time it takes to add an item to an array, as the number of items
already in the list or array gets large:
Let’s zoom in…
even with a REALLY inefficient
process for adding LinkedList
items, LinkedList head insertion
outperforms the array… even if
the array is only 150 elements
long.
Big O notation
• Let’s say our code to change an item’s link were wildly inefficient.
Let’s say it took 10,000 operations to do it.
• Because constant factors tend to not matter as the size of your data
structure goes, when writing the speed of an algorithm, we totally
ignore them. All we care about is how it behaves in terms of n, the
number of items in the structure.
Big O notation
• Writing Big O notation (finally):
• Ignore all constants. 137 * n is just n. If everything is a constant, reduce it to 1.
• Write what remains after the constants are gone in parentheses after a big O:
Adding to a sorted array is O(n)
Adding to the front of a LinkedList is O(1)
Big O notation
• LinkedLists are good when you need to insert at the start a lot. But
there are some things LinkedLists are really bad at. For example, if
you want to get the last element in the list, you have to look at every
single item in the list.
4
6
9
13 31
2
If we want to read 31, we
have to visit 2, then
follow the link to 4, then
follow the link to 6…
Big O notation
• Reading from a LinkedList takes O(n) time.
4
6
9
13 31
2
If we want to read 31, we
have to visit 2, then
follow the link to 4, then
follow the link to 6…
Big O notation
• Quadratic runtimes:
• Say you had two arrays, each of size n. Say you wanted to compare every
element in the first array to every element in the second. You might write it
like this:
Notice this double
for loop…
Big O notation
• Quadratic runtimes:
• Say you had two arrays, each of size n. Say you wanted to compare every
element in the first array to every element in the second. You might write it
like this:
… if we have n items in each list,
and if it takes 10 operations to do
a comparison this part of the
code takes n * n * 10 operations
to run.
Big O notation
• Quadratic runtimes:
• Say you had two arrays, each of size n. Say you wanted to compare every
element in the first array to every element in the second. You might write it
like this:
When writing big O notation, we
throw out constants. So forget
about the 10. We see that the big
O runtime is O(n * n), or O(n2)
Big O notation
• Quadratic runtimes:
• Let’s add 10 * n2 to our graph from a few slides back:
Big O notation
• Quadratic runtimes:
• Let’s add 10 * n2 to our graph from a few slides back.
• Notice that our O(n2) algorithm takes way more operations, even if we only
have about 40 elements.
recursion
recursion
recursion
recursion
recursion
WHAT IS A RECURSIVE FUNCTION?
• A recursive function is any function that works by calling itself.
• Anything you can do with recursion, you could also do by ordinary
means… but some problems are much easier to write solutions for if
you solve them recursively.
WHAT IS A RECURSIVE FUNCTION?
• Here’s something you could easily do without recursion… but we’re
going to do it recursively, just to get a handle on how it works.
• This method takes a number
and then prints it out vertically.
If our number were 137, it would
print:
1
3
7
WHAT IS A RECURSIVE FUNCTION?
• We’ll talk about how (and why) this works in a second. First, though,
some terminology:
Every recursive function needs to have
at least two cases: at least one base
case, and at least one recursive case.
WHAT IS A RECURSIVE FUNCTION?
• We’ll talk about how (and why) this works in a second. First, though,
some terminology:
The base case is the case where the
function doesn’t call itself again. We
need to hit a base case eventually, or
else our function will never stop making
new copies of itself.
WHAT IS A RECURSIVE FUNCTION?
• We’ll talk about how (and why) this works in a second. First, though,
some terminology:
The recursive case is the case where the
function does call itself. Without this
case, the function wouldn’t be recursive.
Notice how writeVertical() calls itself
again whenever number is greater than
or equal to 10.
WHAT IS A RECURSIVE FUNCTION?
• We’ll talk about how (and why) this works in a second. First, though,
some terminology:
Notice how writeVertical() calls itself
again whenever number is greater than
or equal to 10.
Also notice that each time we call
writeVertical(), the value we pass in gets
smaller. Our recursive case gets us closer
to the base case.
WHAT IS A RECURSIVE FUNCTION?
• We’ll talk about how (and why) this works in a second. First, though,
some terminology:
Question: what happens if the recursive
case doesn’t get us closer to the base
case?
WHAT IS A RECURSIVE FUNCTION?
• We’ll talk about how (and why) this works in a second. First, though,
some terminology:
Question: what happens if the recursive
case doesn’t get us closer to the base
case?
… We have an infinite loop… sad panda
TRACING OUR RECURSIVE FUNCTION
[DEMO ON BOARD]
RECURSIVE FUNCTIONS THAT RETURN VALUES
One classical mathematical sequence is the Fibonacci sequence.
It starts out like this:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…
What’s the pattern here?
RECURSIVE FUNCTIONS THAT RETURN VALUES
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…
Each number in the sequence (after the first two) is the number before it
plus the number two before it.
Slightly more formally, element n in the Fibonacci sequence is
element(n-2) + element(n-1)
This suggests that a recursive solution might be something worth trying,
because each number is defined in terms of previous numbers.
55 is 21 plus 34
RECURSIVE FUNCTIONS THAT RETURN VALUES
[SEE LIVECODING EXERCISE]
[SEE DEMO ON BOARD]
RECURSION EXAMPLE 3: PALINDROME CHECKING
• This one is super fun: checking if a string is a
palindrome using recursion.
• We know a string is a palindrome if it reads the
same forward and backwards.
• It stands to reason that if the first letter and the
last letter of a string aren’t the same, that it is
therefore not a palindrome.
• We know that any string that’s 0 or 1 characters
long is a palindrome.
• Let’s use these facts (and the magic of recursion)
to check if a word is a palindrome.
TACOCAT
RECURSION EXAMPLE 3: PALINDROME CHECKING
Designing the algorithm:
0) Let’s check if a string is only 0 or 1
characters long. If it is, we return true.
1) We know that if a string has different first
and last characters, it is therefore not a
palindrome. So let’s compare them, and
return false if they’re not the same.
TACOCAT
RECURSION EXAMPLE 3: PALINDROME CHECKING
Designing the algorithm:
0) Let’s check if a string is only 0 or 1
characters long. If it is, we return true.
1) We know that if a string has different first
and last characters, it is therefore not a
palindrome. So let’s compare them, and
return false if they’re not the same.
This is definitely longer than one letter…
TACOCAT
RECURSION EXAMPLE 3: PALINDROME CHECKING
Designing the algorithm:
0) Let’s check if a string is only 0 or 1
characters long. If it is, we return true.
1) We know that if a string has different first
and last characters, it is therefore not a
palindrome. So let’s compare them, and
return false if they’re not the same.
Let’s compare the first and last
character… they’re the same!
TACOCAT
RECURSION EXAMPLE 3: PALINDROME CHECKING
Designing the algorithm:
0) Let’s check if a string is only 0 or 1 characters long. If it
is, we return true.
1) We know that if a string has different first and last
characters, it is therefore not a palindrome. So let’s
compare them, and return false if they’re not the same.
2) What do we do if the first and last characters are the
same? Well, we need to keep comparing characters – are
the second character and the second-from-last characters
the same?
How can we do this using recursion?
Let’s compare the first and last
character… they’re the same!
TACOCAT
RECURSION EXAMPLE 3: PALINDROME CHECKING
Designing the algorithm:
0) Let’s check if a string is only 0 or 1 characters long. If it
is, we return true.
1) We know that if a string has different first and last
characters, it is therefore not a palindrome. So let’s
compare them, and return false if they’re not the same.
2) What do we do if the first and last characters are the
same? Well, we need to keep comparing characters – are
the second character and the second-from-last characters
the same?
We cut off the first and last character, then call the
function again!
Let’s compare the first and last
character… they’re the same!
TACOCAT
RECURSION EXAMPLE 3: PALINDROME CHECKING
Designing the algorithm:
0) Let’s check if a string is only 0 or 1 characters long. If it
is, we return true.
1) We know that if a string has different first and last
characters, it is therefore not a palindrome. So let’s
compare them, and return false if they’re not the same.
2) What do we do if the first and last characters are the
same? Well, we need to keep comparing characters – are
the second character and the second-from-last characters
the same?
We cut off the first and last character, then call the
function again!
Same! Let’s do it again…
TACOCAT
RECURSION EXAMPLE 3: PALINDROME CHECKING
Designing the algorithm:
0) Let’s check if a string is only 0 or 1 characters long. If it
is, we return true.
1) We know that if a string has different first and last
characters, it is therefore not a palindrome. So let’s
compare them, and return false if they’re not the same.
2) What do we do if the first and last characters are the
same? Well, we need to keep comparing characters – are
the second character and the second-from-last characters
the same?
We cut off the first and last character, then call the
function again!
Same! Let’s do it again…
TACOCAT
RECURSION EXAMPLE 3: PALINDROME CHECKING
Designing the algorithm:
0) Let’s check if a string is only 0 or 1 characters long. If it
is, we return true.
1) We know that if a string has different first and last
characters, it is therefore not a palindrome. So let’s
compare them, and return false if they’re not the same.
2) What do we do if the first and last characters are the
same? Well, we need to keep comparing characters – are
the second character and the second-from-last characters
the same?
We cut off the first and last character, then call the
function again!
We’re down to one letter… so we return
true. It’s a palindrome!
TACOCAT
RECURSION EXAMPLE 3: PALINDROME CHECKING
Designing the algorithm:
0) Let’s check if a string is only 0 or 1 characters long. If it
is, we return true.
1) We know that if a string has different first and last
characters, it is therefore not a palindrome. So let’s
compare them, and return false if they’re not the same.
2) What do we do if the first and last characters are the
same? Well, we need to keep comparing characters – are
the second character and the second-from-last characters
the same?
We cut off the first and last character, then call the
function again!
We’re down to one letter… so we return
true. It’s a palindrome!
TACOCAT
RECURSION EXAMPLE 3: PALINDROME CHECKING
Let’s try it on a non-palindrome. Here we’re testing
the word “tacocrat,” which refers to a taco-
obsessed dictator
• We check the first and last characters. They’re
the same!
We’re down to one letter… so we return
true. It’s a palindrome!
TACOCRAT
RECURSION EXAMPLE 3: PALINDROME CHECKING
Let’s try it on a non-palindrome. Here we’re testing
the word “tacocrat,” which refers to a taco-
obsessed dictator
• We cut off the first and last characters, then
repeat.
• They’re still the same! We cut off the first and
last characters, then repeat…
We’re down to one letter… so we return
true. It’s a palindrome!
TACOCRAT
RECURSION EXAMPLE 3: PALINDROME CHECKING
Let’s try it on a non-palindrome. Here we’re testing
the word “tacocrat,” which refers to a taco-
obsessed dictator
• We cut off the first and last characters, then
repeat.
• They’re still the same! We cut off the first and
last characters, then repeat…
• … whoops! C and R are not the same. We return
false, because this is not a palindrome.
• (full disclosure: I’d give the tacocrat a taco, even though
tacocrat isn’t a palindrome. he’s so cute!!)
We’re down to one letter… so we return
true. It’s a palindrome!
TACOCRAT
RELEVANT TANGENT
Notice how every recursive step in this process gets us closer to
the base case.
For our palindrome program, each recursive step cuts two letters
off the word – thereby causing us to get just a little bit closer to
our base case (a string of only 0 or 1 characters).
(or, if it’s not a palindrome, it gets us closer to the other base case
– it produces a string that might have different first and last
characters)
WHEN DESIGNING RECURSIVE ALGORITHMS, _ALWAYS_ MAKE
SURE THAT YOUR RECURSIVE CASES GET YOU CLOSER TO A BASE
CASE.
TACOCAT
BINARY SEARCH
• Binary search is a very fast way to find where a value is stored in a
sorted array.
• It’s also fairly intuitive to implement recursively
• See video:
TACTICS:
1) FIGURE OUT WHAT YOUR BASE CASE IS. When do you know you’re
done?
• Whenever this condition is true – whenever you know you’re done – that’s
when you return from the method without doing further recursion
2. Figure out something you can do to get just one small step closer
to the base case. This is what your recursive case will do – just get
you one step closer to the base case.
3. Write your recursive case to keep calling itself – to keep taking
that one small step – until you get to the base case.
4. You generally should not have to use loops within your recursive
functions. The recursion does what you’d ordinarily use loops to
do.
BACK TO HASHING
Hashing, Big O notation, Recursion
• A HashMap is a data structure that associates a key with a value.
Consider the HashMap declared below:
Review: HashMap
• A HashMap is a data structure that associates a key with a value.
Consider the HashMap declared below:
• You add an item to a HashMap by using the .put() method:
firstHashMap.put(137, “Ben”);
Review:
HashMap
• A HashMap is a data structure that associates a key with a value.
Consider the HashMap declared below:
• You add an item to a HashMap by using the .put() method:
firstHashMap.put(137, “Ben”);
Review: HashMap
This is the key
• A HashMap is a data structure that associates a key with a value.
Consider the HashMap declared below:
• You add an item to a HashMap by using the .put() method:
firstHashMap.put(137, “Ben”);
Review: HashMap
This is the value
• A HashMap is a data structure that associates a key with a value. Consider
the HashMap declared below:
• You add an item to a HashMap by using the .put() method:
firstHashMap.put(137, “Ben”);
• You retrieve an item from the HashMap by using the .get() method:
String result = firstHashMap.get(137);
Review: HashMap
returns “Ben”, because that’s the
value associated with the key 137.
Maps and HashMaps
• Just like ArrayList is a derived class from the List base class, HashMap
is a derived class from the Map base class.
so we can (and should)
declare our HashMaps
as just Maps
HashMap
• In the case of an ArrayList, we associate items in the list with an
index – with their location in the array. We can look items up by
index.
• In the case of a HashMap, we associate items in the list with
whatever we want – with a key that we define – and then can look
up items using that key.
• You really can use whatever you want as a key value
HashSet
Another commonly used container is the HashSet. This stores data by
hashing, as in a HashMap.
A HashSet (and Sets in general) are data structures that have the
following features:
• They are unordered (so looking up an element by index makes no
sense)
• They contain no duplicates. (this can be very useful)
Why use hashing?
• The simple answer: It’s fast.
• Okay, but what does it mean for a data structure to be “fast”?
Why use hashing?
• The simple answer: It’s fast.
• Okay, but what does it mean for a data structure to be “fast”?
• One of our main tools for understanding algorithm speed is what’s
called “Big O notation.” Let’s discuss it briefly.
Return to HashMaps
• HashMaps are kind of magic: inserting into a HashMap takes
O(1) time, searching for an element in a HashMap takes O(1) time,
deleting an element takes O(1) time…
or “constant time”
• Here’s an image on
how hashing works,
that I’ve shamelessly
stolen from Wikipedia
Keys, values, and hash functions
• We have a bunch of keys and values. In our stolen example, the
HashMap is being used in a contacts list: the key is the name of a
person, and the value is their phone number.
• Our hash function is any function
that can convert the key into
a numerical index. We store
the value associated with the
key at whatever index the
hash function produces.
Return to HashMaps
• Our hash function is any function that can convert the key into a
numerical index. We store the value associated with the key at
whatever index the hash function produces.
• A good hash function is one
that produces few collisions.
• What’s a collision? That’s when
two keys happen to hash to
the same value.
Return to HashMaps
• In this case, the names John Smith and Sandra Dee both happen to
hash to the value 152. They can’t both be stored in the exact same
space, so we have a problem.
Collision!
Return to HashMaps
• In this case, the names John Smith and Sandra Dee both
happen to hash to the value 152. They can’t both be stored in
the exact same space, so we have a problem.
• We resolve this problem by
having each bucket store a
linked list.
• We try to avoid collisions…
but if we do, we can store
two elements in a list in one
bucket.
Return to HashMaps
• In this case, the names John Smith and Sandra Dee both
happen to hash to the value 152. They can’t both be stored in
the exact same space, so we have a problem.
• We resolve this problem by having
each bucket store a linked list.
• We try to avoid collisions… but if
we do, we can store two elements
in a list in one bucket.
• … and if we have too many
collisions, we can just increase the
number of buckets.
Return to HashMaps
• Because looking up an element just requires putting the key
through a hash function, lookup doesn’t depend on the
number of items in the HashMap: it’s O(1)
• Likewise deleting an element
just requires putting the key
through the hash function
and deleting the value stored
in the bucket. O(1)
• Adding an item is similar. O(1)
Return to HashMaps
• In short: HashMaps are really really really fast.
• Arrays are fast at retrieving items. LinkedLists are good at adding items
to the start… but HashMaps are good at (nearly) everything.
(even if your hash function
takes a lot of operations
to run).
The .hashCode() method
• The .hashCode() method is used by HashMap and HashSet to determine
where to store hashed values
• One way to make a hashCode() meethod is to autogenerate it.
• On the next slide is a recipe for writing a reliable hashCode() method.
This isn’t something you need to memorize – the point is that:
1. The .hashCode() method returns an int that should be (relatively) unique for
each object
2. The hashCode() method should produce this int in a way that relies upon all of
the member variables that are tested by the .equals() method
One strategy for the .hashCode() method
1.Create a int result and assign a non-zero value.
2.For every field f tested in the equals() method, calculate a hash code c by:
1. If the field f is a boolean: calculate (f ? 0 : 1);
2. If the field f is a byte, char, short or int: calculate (int)f;
3. If the field f is a long: calculate (int)(f ^ (f >>> 32));
4. If the field f is a float: calculate Float.floatToIntBits(f);
5. If the field f is a double: calculate Double.doubleToLongBits(f) and handle the
return value like every long value;
6. If the field f is an object: Use the result of the hashCode() method or 0 if f ==
null;
7. If the field f is an array: see every field as separate element and calculate the
hash value in a recursive fashion and combine the values as described next.
3.Combine the hash value c with result:
4.result = 37 * result + c
5.Return result
originally from
the book
Effective Java –
I believe this is
the algorithm
that IntelliJ’s
autogenerator
uses, though I
haven’t tested
everything
.hashCode()/.equals() contract
• It is expected that every object that overrides .equals() should have its own
.hashCode() method.
• (for the purposes of this class, it is totally fine to use an autogenerated one produced
by your IDE)
• This is the .hashCode()/.equals() contract: if a pair of objects are considered
equal by the .equals() method, the results of their .hashCode() methods
should also be equals.
• Repeat: if two objects are .equals(), they should have the same hash code.
• However, this doesn’t work the other way around. Just because the
.hashCode() methods of two objects return the same value doesn’t necessarily
mean that they’re equal.
• This is because hash collisions occur
.hashCode()/.equals() contract
• This is because hash collisions occur:
In this case there’s a
hash collision between
John Smith and
Sandra Dee. That’s
fine! A hash function
can return the same
value for two objects
without those objects
actually being equals.