How to Use a Hashing Function to Insert Random File Records (73041)

MORE INFORMATION

An arbitrary hashing function is a function that returns a unique record index that is used as a starting record number to search for the next empty record in a random access file. In the program example below, the (arbitrary) hashing function returns the length of the name in each data record. (We could have added ASCII values of the characters within the string, or used any other arbitrary function, to produce a record number as a starting point for where to start searching for the next empty record.)

In the program example below, the hash number used to index the start of the search will be the length of the name in each record. Duplicate hash values are handled by incrementing the hash value by one, and trying to reinsert the record. If the record is unoccupied, the new data (name) is inserted. If the record is occupied, the hash value is once again incremented, and the test for an empty record once again takes place. This continues until an empty record is found and the new record information is inserted. If the hash value goes over 50 while looking for an open record number, the value is reset to 1 and the search continues. A loop counter stops the program if all 50 records in the file are full.

Program Example

' Works in QuickBasic versions 2.0, 2.01, 3.0, 4.0, 4.0b and 4.5;
' Microsoft Basic Compiler 6.0 and 6.0b; and Basic PDS 7.0 and 7.1.

OPEN "test.dat" FOR RANDOM AS #1 LEN = 19             ' open the file
FIELD #1, 15 AS name$, 4 AS recnum$     'FIELD the random file buffer

FOR i = 1 TO 50
  LSET name$ = "unoccupied"       ' Initialize all records in file
  LSET recnum$ = MKS$(i)          ' with the string "unoccupied".
  PUT #1, i
NEXT

FOR i = 1 TO 5
  READ x$          ' Read names one at a time from the DATA statement
  hash% = LEN(x$)               ' Compute hash value
  GET #1, hash%                 ' Get the record at hash%
  WHILE RTRIM$(name$) <> "unoccupied"   ' Check if currently occupied
     count = count + 1
     IF count > 50 THEN
        PRINT "File is full"      ' Stop when file is full
        STOP
     END IF
     IF hash% < 51 THEN     ' Cycle through all possible hash values
        hash% = hash% + 1    ' Increment hash value
     ELSE
        hash% = 1
     END IF
     GET #1, hash%    ' Get next record after incrementing hash value
  WEND
  LSET name$ = x$
  LSET recnum$ = MKS$(hash%)
  PUT #1, hash%  'put data into file at the record pointed to by hash%
NEXT

INPUT "Enter new name: "; n$   ' enter new value to put into file
hash% = LEN(n$)

GET #1, hash%

WHILE RTRIM$(name$) <> "unoccupied"   ' Check if record at hash% is
                                      ' occupied
   hash% = hash% + 1     ' Increment hash%
   GET #1, hash%         ' Get next record and check if occupied
WEND

LSET name$ = n$
LSET recnum$ = MKS$(hash%)

PUT #1, hash%              ' Insert new data at unoccupied record

FOR j = 1 TO 50                  ' print the contents of the file
  GET #1, j
  IF RTRIM$(name$) = "unoccupied" THEN
        PRINT "unoccupied"
  ELSE
        PRINT name$
  END IF
  IF j MOD 20 = 0 THEN SLEEP           ' stop to look at list
                  ' In QB 2.x or 3.0, use INPUT Q$ instead of SLEEP
NEXT
END
DATA Stan Jones, Rick Jones, Phil Jones, Bart Jones, Frank Jones