Hash lab

Learning Objective(s)

1. Expand knowledge about organizing and searching data to hashing
2. See the implications of Big O on real data, esp. on large amounts of data
3. Learn to write a quality report analyzing amount of work.

Overview of the problem

Specifics

• Implement a hash table (including add and find methods).
• Compares are the number of times an element in the hash table is accessed.
• The hash function should be more complex than just mod'ing by table size
• The data is in similar format to previous lab. Use first file to build the hash table. Use the second file to look for numbers in the hash table.
• The integer is the key.
• You may pick any collision handling method you wish.
• Run the tasks on a decent number of cases including:
  • data that is almost in order
  • data that is almost in reverse order
  • data that is in random order
  • tiny amount of data in the first file (< 100)
  • small amount of data in the first file
  • medium amount of data in the first file
  • large amount of data in the first file
  • a few numbers in the second file
  • a medium number of numbers in the second file
  • a large number of numbers in the second file
• Number of classes

Report

• Run enough examples of each type to get a good set of data points. (3 or 4 data points per type is not enough!)
• Plot them on a graph (with the horizontal axis being the size of the data and the vertical being the number of comparisons and/or swaps)
• Compare the generated results to the expected Big O results
• Discuss the following:
  • How each algorithm compared to its Big O
  • When sorting first then searching is better than just searching
  • A comparisons of the sorts with each other
• It is recommended that you use graphs in a spreadsheet to visualize the data

Optional improvements

• Compare results with different sizes of the table (related to the size of the input)
• Compare different hashing routines
• Compare different collision handling routines