imperative / Java
Analogy
Collected by Colleen Lewis — Own practice
Explains need for hashCode() and equals() methods when using HashSet
PL | NM |
---|---|
HashSet | Box of hanging folders |
bucket | Single file folder |
key | Piece of paper in a file folder |
value | N/A (HashSet, not HashMap) |
add(key) method | Find correct folder, check if the folder already contains the key by comparing the key to all contents of the folder |
Need for .hashCode() and .equals(Object o) methods
Teaching students to use the built-in HashSet Java library class
Used in class for ~10 minutes, but requires having a file folder bin
Instructional Context: I teach a post-secondary course in which students learn about data structures and learn to program in Java and Racket. My lectures are twice a week for 75 minutes. My enrollment ranges from 50 to 150 students in each lecture section. I typically lecture for 5 to 10 minutes and then have students work in pairs to try to apply the newly introduce idea.
Use Why: I find that students think Hash Tables are baffling. It isn't that they have trouble using them, but they report not understanding them. I don't have a perfect explaination for what they think they don't understand, but since I've started using this technique, I've stopped getting the complaints that "Hash Tables make no sense!" Maybe the problem was just that I wasn't explaining them very well before!
Learning Goal: This explanation is focused on helping students to understand why we need to provide a hashCode()
and equals(Object o)
when they work with the library class HashSet
in Java. In getting at why we need these it also introduces how a HashSet
in Java works (assuming chaining), but I don't test students on how a HashSet
works.
Why HashSet and not HashMap?: I just start with HashSet
because it is simpler. I find that students don't have trouble translating what they learned to understand HashMap
in Java.
Instructional Sequence Overview: I trace through what would happen with the following code that attempts to add 7 Strings
to a HashSet
. First, the code will add 3 String
s ("Bear" "Zebra" "Tiger"
) that each go in different buckets (i.e., folders). Second, we'll try to add something that's already in the HashSet
. Finally, then we'll add three String
s ("Orange" "Dog" "Zoo"
) that all go in the same bucket (i.e., folder). This allows students to see a collision where the item is .equals
and two where they are not.
import java.util.HashSet; public class FileFolderHashSet { public static void main(String[] args) { HashSetfolders = new HashSet (); folders.add("Bear"); folders.add("Zebra"); folders.add("Tiger"); folders.add("Bear"); folders.add("Orange"); folders.add("Dog"); folders.add("Zoo"); } }
Tracing one call to the add
method: This involves going through the following numbered steps. The first time I trace add
I say all of the bullets under each step. Tracing through the add
method after the first time, I still do each step, but I don't say all of the bullets.
FileFolderHashSet
above (e.g., folders.add("Bear");
).
HashSet
named folder
and someone wants to add the String "Bear"
.String
on a piece of paper.
String
that I need to store, but I need a reliable way to remember where I put it.hashCode()
returns for the String "Bear"
.HashCodeTest
below (e.g., String s = "Bear";
).
add
method in the HashSet
class always calls hashCode()
on the object it was passed.HashCodeTest
class to figure out what hashCode()
would return for the String "Bear"
.HashCodeTest
to get a value for the call to hashCode()
.
hashCode of "Bear" is 2066388
"String "Bear"
, but I need to remember where I put it. hashCode
to decide what folder to put it in."Bear"
).
String "Bear"
here, but I need to make sure I haven't already stored the String "Bear"
.String
written on it.
.equals
with it to see if I have already added it. If it’s no already there, I add the new paper.public class HashCodeTest { public static void main(String[] args) { String s = "Bear"; System.out.println("hashCode of \"" + s + "\" is " + s.hashCode()); } }
HashCode
values Here are the values returned for each String
as printed by the class HashCodeTest
:
hashCode of "Bear" is 2066388
hashCode of "Zebra" is 86223590
hashCode of "Tiger" is 80806047
hashCode of "Orange" is -1924984242
hashCode of "Dog" is 68892
hashCode of "Zoo" is 90042
Do you have feedback on this notional machine? Did you find a mistake, or do you have a request for improvement? You can create an Issue on GitHub, where the description is hosted. This way we can see your feedback and address it.
For this, you need a GitHub account. Then follow this link to see the source file of this page. In there, click the ... left of the highlighted line, then pick "Reference in a new issue".