In the labs in previous lessons you have searched a data file containing ID and inventory information in a variety of ways. Of the search algorithms studied, the fastest search algorithm was O(log2N) for a binary tree or binary search of an ordered array. It is possible to improve on these algorithms, reducing the order of searching to O(1), or linear function of file size. The data structure used to accomplish this is called a hash table, and the O(1) search is referred to as hashing.
An example of hashing could occur on the first day of school. When distributing student schedules, one long line is usually broken up into smaller lines, often by grade level. This concept could be extended to 26 lines. Students line up according to the first letter of their last name. This is what hash-coded data storage is about - breaking up and reorganizing one big list into many little lists.
The key topics for this lesson are:
