Class 49: Hash Tables

Held: Monday, 2 May 2011

Summary: We consider one of the more important ADTs, the dictionary, and an equally important implementation of dictionaries, the hash table.

Related Pages:

• EBoard.
• Lab: Hash Tables..
• Reading: K&R 6.5 and 6.6.

Notes:

• Happy Chenille Stem Week!
• Preregistration issues.
• I've answered some of your questions on the reading. Please try to avoid the ones that can be answered with man and more careful reading.
• Reading for tomorrow: Wikipedia on Stacks and Queues.
• CS Picnic (probably) rescheduled.
• Please continue to send questions on the exam through Piazzza (general) and email (specific).
• EC for Grinnell Prize Announcement, Thursday, 11 a.m., Herrick. [academic]
• EC for Thursday extra (HCI, I think). [academic]
• EC for final CS table of the year. [academic]
• EC for Psychologist Talks (tbd). [academic]

Overview:

• ADTs and Data Structures.
• Reading commonalities.
• The Dictionary ADT.
• Implementing Dictionaries with Association Lists.
• BST's.
• Hash Tables.
• Lab.
• Reflection.

ADTs and Data Structures

• As you've started to see, in our algorithm design, different ways of organizing data give you different advantages and disadvantages.
• For example, in CSC151 you learned about arrays and lists. You've also learned about files.
  • Both provide a way of grouping data.
  • Lists are easy to extend and shrink.
  • Arrays are mutable.
  • Arrays provide fast access to individual elements.
  • Files provide persistent storage.
• It's time to start looking at other mechanisms for organizing data.
• In designing structures, we may look at three related issues:
  • The high-level overview of what operations the structure provides. We often refer to this as the abstract data type or ADT.
  • The high-level details of the implementation of the ADT. We often refer to this as the data structure. One ADT may have many corresponding data structures.
  • The low-level details of the implementation of the data structure. (E.g., do we implement it with an array, or a bunch of pairs, or ....)
• Note: While we will often start with the ADT and work down to the implementing data structure, the history of CS suggests the reverse: People designed data structures and then later realized that they should generalize.

The Dictionary ADT

• The Dictionary is one of everyone's favorite ADT's. A dictionary stores key/value pairs and typically provides the following basic operations.
  • Add a key/value pair to the dictionary.
  • Given a key, look up the corresponding value in the dictionary.
• Sometimes we add additional operations
  • Delete a key/value pair
  • Given a value, find one (all) of the corresponding keys.
  • Do something for each key/value pair
  • Determine whether a key appears in the dictionary
  • ...
• In a typed language like C, we often limit the type of the key and value (e.g., to strings).
• Dictionaries have many other names: I have seen them referred to as Maps, Tables, Hashes, and Associative Arrays

Association Lists

• You've already seen one implementation of dictionaries: Association lists.
• Association lists are easy to implement and use.
• But they are slow.

Binary Search Trees

• Binary search trees are another common mechanism for implementing dictionaries.
• Idea: At each node in the tree, you have the key, a value, and pointers to the left and right subtrees.
• The left subtree contains smaller keys.
• The right subtree contains larger keys.
• Relatively fast.
• Easy to grow.

Hash Tables

• Hash tables are one of the most common mechanisms for implementing dictionaries.
• Hash tables are fast (Expected time: A constant number of steps.)
• Key idea: Arrays are fast. So turn the key into a number that you can use to index the array.
• We use a hash function to turn keys into integers. We then mod the integer by the size of the table.
• A hash function must always give the same integer for the same key.
• A hash function should give different integers for different keys. (Counting suggests that this is not always possible.)
• What do we do about collisions? Ah, that's the rub.
  • We can repeatedly add some constant and look elsewhere in the table until we find a free spot.
  • We can store a list/array of values at each integer.

Lab

• Do the lab.
• Be prepared to reflect.