Princeton University
COS 217: Introduction to Programming Systems

Precept 10: Review

Purpose

Review for midterm exam 1

Give overview of Assignment 3

Review for Midterm Exam 1

Fall 2001 exam

Fall 2001 exam answer sheet

Fall 2000 exam

Fall 2000 exam answer sheet

Assignment 3 Overview

Purpose: Composition of ADTs and performance analysis

Part 1: Create a Table ADT that is implemented as a hash table

Each bucket of the hash table should be a Set

Also create an associated TableIter ADT

Part 2: Use given test program and gprof to analyze the performance of the Table ADT

Hash Tables

Data structure

A hash table is an array

Each element of the array is a bucket

Each bucket is a set of bindings

Could be implemented as a singly linked list

Could be implemented using the Set ADT from Assignment 2 -- that's what you'll do

Each binding is a key/value pair

Each key uniquely identifies its node

Each value can be any arbitrary data that is somehow related to its key

Fundamental algorithms (informally)

See Hash Table Fundamental Algorithms handout

hash function

Given a key and bucketcount, returns some integer in the range 0...bucketcount-1

Doesn't matter what the integer is, except...

When subsequently called with the same key, must return the same integer

Example:
Assume
BUCKET_COUNT = 7
hash("Ruth", 7) = 4
hash("Gehrig", 7) =  1
hash("Mantle", 7) =  5
hash("Jeter", 7) = 1
On board, show results of:
put("Ruth", "RF");
put("Gehrig", "1B");
put("Mantle", "CF");
put("Jeter", "SS");
getValue("Mantle"):
remove("Mantle");

Performance of fundamental algorithms

Each fundamental algorithm is O(1) -- as long as there aren't too many collisions

Ideal hash function returns integers that yield remainders that are uniformly distributed

Worst hash function returns same integer for any given key

Best for BUCKET_COUNT to be a prime number

Note: User must not be allowed to change a key

Doing so would corrupt the hash table

(See use of "const" in ADTs to prevent user from changing keys)

The Table Interface

Almost identical to Set

Table_new must accept a pointer to a hash function

Table_map need not traverse bindings in any particular order

The Table Implementation

Very straightforward

Key idea: the Table ADT is a user/client of the Set ADT

Table_new must allocate array, and fill each element with an empty Set

Each Table function uses hash function to find correct Set, and then delegates the work to that Set

The TableIter Interface

Identical to SetIter, except need not traverse bindings in any particular order

The TableIter Implementation

TableIter must store pointer to its Table, current bucket, SetIter for current bucket

Informally describe TableIter_selectFirst, TableIter_selectNext

Princeton University COS 217: Introduction to Programming Systems