Skip to main content
ICT
Lesson AB32 - Hash-Coded Data Storage
 
Main   Previous Next
 

AB32 Introduction page 1 of 9

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). 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 frequently occurs in schools, when students line up into 26 lines, each line representing the first letter of their last name. Another example occurs when one large group or list of student schedules is broken down into smaller groupings or lists, often by grade level, for easier distribution. This is what hash-coded data storage is about - breaking up and reorganizing one big list into many smaller lists.

The key topics for this lesson are:

  1. Hashing Schemes
  2. Computing Hash Codes
  3. Dealing with Collisions
  4. Order of a Hash-Coded Data Search
  5. HashSet and HashMap

 

Main   Previous Next
Contact
 © ICT 2006, All Rights Reserved.