CIS 29 - Notes for Thursday, 2/18

Announcements and Reminders


One More Class Template Example

Example 13-12 - A Generic Linked List


Hash Tables

  • A hash table is an abstract data type like an array
  • A hash table uses a function that converts a key value into an index that is used with an array of values
  • The hash table function should be simple and fast to execute
  • Two different hash table keys may produce the same index.  That is referred to as a collision.  Collisions may be resolved programmatically or not.
  • Hash tables are usually very fast for look-ups


Example 14-1 - First Hash Table Example

Example 14-2 - Use a hash table to store a dictionary and play a game                  Unscramble

Hash Table Questions

  1. What makes one hash table better than another?
  2. How do you design a good hash table?
  3. Suppose you are going to use a hash table to manage a data base application, such as DeAnza student data.  How would you design the hash?