Designed by Marcia, Sam, Barry, Lenny, Dick, Mary Lou, Cinda, and Harmony.
This KLA is transcribed from the SIGCSE 2005 Workshop on KLAs.
Overview To KLA
Summary: Demonstrate the efficiencies of various hashing algorithms.
Learning Goals: At the end of this exercise, students will understand how hashing works.
Course And Level: Data structures (CS2)
Planning For KLA
|•||Cards with numbers (hash values) to represent buckets.|
| || |
|—||last digit of date of birth|
As always, read this description carefully and practice the KLA before using it in class!
Execution Of KLA
|•||Post "bucket" cards on wall.|
|•||Select volunteers, a greater number than the number of buckets.|
|•||Choose one person as the hash function.|
|•||Hash person takes each person in sequence, applies hash function, and leads each person to bucket. (Can be done in parallel)|
|•||Have students critique functions.|
|•||Have students suggest better functions for better distribution.|
Variants And Extra Topics:
|•||Ask students to design hash functions.|
|•||Linear probing instead of buckets.|
|•||Motivate with "homework buckets".|
Constraints On KLA
Would your KLA work if your students had the following constraints:
Pitfalls Of KLA
|•||Hard to motivate particular hash functions.|
Feedback And Use Notes
Use Notes: add your use notes here!