Hash Table

What is hashing? What is a hash table? Well, a hash table is a data structure that allows one to store data for both fast insert and fast find. Each piece of data has a unique place in a table.

A Hashing function derives a number from the data that is from 1 to N, where N is the size of the table.

The number is where the data is to be stored in the table. Some pieces of data may have the same hash number. This means that two pieces of data may try to be in one place in the table. This is where a collision routine comes in.

A collision routine decides how to find an empty place in the table. The collision routine in the program listed below looks at the next highest place until an empty place is found. This is not a good collision routine, but it will do as an example.

The collision routine is also used when trying to find data in the table. When the wrong data is found at a place where something else should be, the collision routine searches the next highest place until the proper data is found. If an empty place is found first, then the data wanted is not in the table.

The hash routine used in the program takes the first and last characters in the string, adds them, and performs a MOD 31 to get a number between 1 and 31. Hope this can be of use to you. If you have any questions feel free to ask.

  100 REMark declare hash table 
  110 CLS 
  120 DIM a$(31,10)
  130 REMark initialise hash table 
  140 FOR x=1 TO 31 
  150 LET a$ (x)="" 
  160 NEXT X 
  170 PRINT "DO you want to " 
  180 PRINT A)dd " 
  190 PRINT F)ind" 
  200 INPUT X$ 
  210 IF x$="A" OR x$="a" THEN GO TO 240 
  220 IF x$="F" OR x$="f" THEN GO TO 550 
  230 GO TO 170 
  240 PRINT "Input string to enter to table" 
  250 PRINT " Enter 0 to end" 
  260 INPUT in$ 
  270 IF in$="0" THEN GO TO 170 
  280 LET count=0 
  290 IF LEN(in$)>10 THEN GO TO 260 
  300 REMark find place in hash table 
  310 LET length=LEN (in$)
  320 LET first=CODE (in$ (1))-32 
  330 LET last = CODE (in$ (length) )-32 
  340 LET hash=first+last 
  350 REMark find hash MOD 31 
  360 LET hash=hash/31 
  370 LET hash=hash-INT (hash) 
  380 LET hash=hash*31 
  390 REMark is the place in the table empty 
  400 IF a$(hash)<>"" THEN GO TO 460 
  410 REMark yes, put string here 
  420 LET a$(hash)=in$ 
  430 PRINT in$;" entered at #"; hash 
  440 GO TO 240 
  450 REMark no, so move down table 
  460 LET hash=hash+1
  470 LET count=count+1 
  480 REMark reached end, go to beginning 
  490 IF hash>31 THEN LET hash=1 
  500 REMark is table full? 
  510 IF count>=31 THEN GO TO 530 
  520 GO TO 400 
  530 PRINT "Hash Table is full" 
  540 GO TO 170 
  550 PRINT "Enter string to find" 
  560 INPUT in$ 
  570 LET count=0 
  580 REMark find place in table 
  590 LET length=LEN (in$) 
  600 LET first=CODE (in$ (1))-32 
  610 LET last = CODE (in$ (length) )-32 
  620 LET hash=first+last 
  630 REMark find hash MOD 31 
  640 LET hash=hash/31 
  650 LET hash=hash-INT (hash) 
  660 LET hash=hash*31 
  670 REMark is it found? 
  680 IF a$ (hash)<›in$ THEN GO TO 730
  690 PRINT in$;" found at location #"; hash 
  700 GO TO 170 
  710 REMark when we reach a empty loc 
  720 REMark then not found 
  730 IF a$ (hash) <>'" THEN GO TO 760 
  740 PRINT in$;" not found at all" 
  750 GO TO 170 
  760 LET count=count+1 
  770 LET hash=hash+1 
  780 REMark we have searched entire table 
  790 IF hash 31 THEN LET hash=1 
  800 IF count>=31 THEN GO TO 690 
  810 GO TO 680