14.2 HashTable Example

We could also choose to save the file list in a hash table. A hash table is typically used to store objects that should be retrieved fast from the table. In order to store an object in a hash table it is necessary to define a hash function that given an element returns a value that can be used in the hash table implementation. A good hash function for our file list could be

hashFunction:: (# (* scan all characters in the filename and compute a value * for the hash function *) do name.scanAll(# do value*100 + ch -> value #); #);

The hashtable can then be defined as follows:

dirTable: @ hashTable (# element:: Text; hashFunction:: (# do e.scanAll(# do value*100 + ch -> value #); #); #);

And the complete program using this hash table:

Program 19: DirTable.bet

ORIGIN '~beta/basiclib/directory'; INCLUDE '~beta/containers/hashTable'; ---program: descriptor--- (# dirTable: @hashTable (# element::< Text; hashFunction:: (# do e.scanAll(# do value*100 + ch->value #); #); #); d: @directory; do (if noOfArguments <> 2 then 'Usage: '->puttext; 1->arguments->puttext; ' path'->putline; stop; if); (* set name of directory *) 2->arguments->d.name; (* print name of directory *) newline; (* initialize table *) dirTable.init; (* scan the entries and append to list *) d.scanEntries (# (* found refers to the current entry *) do found.path->dirTable.insert; #); (* dirTablenow contains all the names of the entries in the * directory *) dirTable.scan (# (* current refers to the current text element *) do current[]->putline; (* print the text *) #); (* print hashtable statistics on screen*) '\nStatistics: '->screen.putline; dirTable.statistics(# do screen[]->print #); #)

Running this program on the current directory gives the following output:

nil% DirTable . StaticAndDynamic.bet FileCount.bet ExploreTypes.bet CountChar2.bet CountChar1.bet CountChar.bet Multiplication3.bet Multiplication2.bet Multiplication1.bet MultiplicationTable.bet DirTable.bet DirTable.ast HelloWorld.bet SaveListDir.bet QuickSort.bet SquareRoot.bet .. . MultipleAssignment.bet DirTable sun4s ListDir.bet SimpleTypes.bet Statistics: Histogram: (0,2,1,3,0,0,0,0,2,3,0,3,2,0,0,2,0,0,0,1,2,2,2,0,1) Maximum Collisions: 3 Minimum Collisions: 0 Average Collisions: 2

More information and more examples using the other containers in this library can be found the Mjølner System manual [MIA 92-22].