Article Preview
Buy Now
| Print: | |
| PDF: |
Algorithms
Hashing
Pigeonhole Your Data
Issue: 1.4 (February/March 2003)
Author: Matt Neuburg
Author Bio: Matt Neuburg is the author of
Article Description: No description available.
Article Length (in bytes): 10,644
Starting Page Number: 34
RBD Number: 1417
Resource File(s):
1417.sit Updated: Friday, October 17, 2003 at 12:20 PM
Related Link(s): None
Known Limitations: None
Excerpt of article text...
Here's a problem that arises frequently in computing: You're going to be handed a lot of items of data, and then shown a new item and asked whether you've already been handed one identical to it, and if so, where you put it. This is a problem that arises in real life, and we can use real-life reasoning to analyze it. Suppose, for example, that you are a doctor with two or three hundred patients. You've got a file of information on each patient; when a patient comes in for an appointment you'd like to lay your hands on that patient's file. How do you store the files?
You could just have a room where all the files are thrown helter-skelter on the floor; but this would not be very efficient. It guarantees that all the files are in one place, but you might have to examine every single file in order to find the one you want. A better answer is, of course, a filing cabinet. For purposes of discussion, let's imagine a filing cabinet with 26 drawers. If each drawer is labelled with a letter of the alphabet, in order, then we could use the first letter of a patient's last name to tell us where to put that patient's file -- and where to find it again later. Instead of a big room containing all the files we've now got 26 little rooms, each containing just a few files.
...End of Excerpt. Please purchase the magazine to read the full article.
Article copyrighted by REALbasic Developer magazine. All rights reserved.
|
