Recently Viewed: Home > Hash Functions
 Hash Functions

Hash Functions

 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)

 Preparation Time: 2 mins

 Execution Time: 10 mins

Planning For KLA

 Materials:
 • Cards with numbers (hash values) to represent buckets.
 • People as data.

 Preparation:
 • Plan hash functions:

 — first digit of age

 — last digit of age

 — last digit of date of birth

 As always, read this description carefully and practice the KLA before using it in class!

Execution Of KLA

 Description:
 • 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

 • Limited Vision:
 • Limited Hearing:
 • Limited Mobility:
 • Trouble Speaking:
 • Touch Aversion:
 • Other:

Pitfalls Of KLA
 • Hard to motivate particular hash functions.

Feedback And Use Notes