After scanning an item at a cash register, the number of steps required to find the price is constant:

1. Hash the bar code value and get the hash table location.

2. Go to that location in the hash table, and traverse the linked list until the item is found.

3. Return the price.

The number of steps in this algorithm is constant. The hashing scheme tells the program exactly where to look in the hash table; therefore, this type of search is independent of the amount of data stored. We categorize this type of algorithm as constant time, or O(1).

If the linked lists get lengthy, this could add a few undesirable extra steps to the process. A good hashing scheme will minimize the length of the longest list.

An interesting alternative to linked lists is the use of ordered binary trees to deal with collisions. For example, the hash table could consist of 10,000 potential binary trees, each ordered by a key field.

Remember that determining the order of an algorithm is only a categorization, not an exact calculation of the number of steps. A hashing scheme will always take more than one step, but the number of steps is independent of the size of the data set, hence it is called O(1).