#Help
>> a "hashing" technique
> .. an example or in-depth description?
Here's a brief and very sloppy example. Please try to find a better hashing
algorithm than the one I will suggest.
ASSUME: You expect ot have 200 records or so. Good; I'll has into a table of
512 bytes (notice the planned waste space?)
Before starting, I'll set all hash table entries to zero. Then I will go
through each key string of each record (call it Key$) and calculate:
Hash = 0
FOR J=1 TO LEN(Key$) : Hash = Hash * 7 + ASC(MID$(Key$,J,1))
Hash = Hash MOD 512 (however your Basic does a MOD remainder)
NEXT J
At this point, you have a value for variable Hash that is a muddied up
result of the original string. We need to put it into the hash table, at entry
number (Hash). But suppose that entry has already been used by some other
string that hashed to the same number? In that case, we just move along and
pop the index into the next free spot. (Heaven help you if you didn't allow
waste space). Call our has table HT(), and the number of our current record is
N, so:
WHILE HT(Hash)<>0
Hash = (Hash + 1) MOD 512
WEND
HT(Hash)=N
After we've done this calculation with all our records (and we could save the
hash values on the file or recalculate them each time, we can now look up an
input value in a similar way. Hash to key in exactly the same way as before.
Look up the hash table entry for that value; if it's zero, you have no match.
If it's not zero, compare with the actual record. If it matches, you're there.
If it doesn't match, repeat that Hash=(Hash+1)MOD512 bump and try again until
you get a zero or a match.
A little thought will show you that, in some cases, hashing can be very fast
indeed; your first hit finds the record. And that a near-full table (say, 500
out of 512) can be mighty slow. More, you need to consider that if you have a
few dozen guys called Smith, you might do well to has both first and last
names.
–Jim