THE LINEAR HASH TABLE No. 2 RANDOM KEYS by F.R.A. Hopgood

In 1968, a set of computer animated films produced using GROATS were used in a Compiling Techniques Course at Brunel University and elsewhere to illustrate hash tables and their speed compared with standard table lookup.

The films were originally produced on the Chilton SC4020. In 1974, one of the films was redone using the newer FR80 and with a synchronised soundtrack for a presentation at IFIP74 in Stockholm.

Alan Francis interfaced a VCS3 Synthesiser to the Chilton PDP15 and a program on the PDP15 very similar to the GROATS program controlled the basic sounds from the synthesiser.

The soundtrack itself was output to a sprocketed audio tape. This allowed Peter Hadingham of Swift Films to generate the version with synchronised sound. To add some humour to the soundtrack, Alan added more harmonics interactively as the search paths got longer.

The IFIP 74 Paper, Computer Animation used as a Tool in Teaching Computer Science, received a Best Papers Award at the Conference.

The individual table positions are numbered 1 to 128 (anticlockwise from top left). The hash function generates a position to first try (random numbers generated between 1 and 128). The graph shows the current average length of search. Even with the table at 80% full, the average search length is around 3 compared with approximately 50 for the standard table lookup. An asterisk indicates positions where the search path is of length 1, the number of vertical lines indicate the search length for the other entries. The number above the graph indicates the maximum path length so far. For anybody interested in redoing the animation, the random numbers and the details are given in the table below.

Entry Random Path End Length Average
1 43 43 1 1.00
2 101 101 1 1.00
3 30 30 1 1.00
4 12 12 1 1.00
5 54 54 1 1.00
6 15 15 1 1.00
7 55 55 1 1.00
8 119 119 1 1.00
9 94 94 1 1.00
10 87 87 1 1.00
11 89 89 1 1.00
12 18 18 1 1.00
13 1 1 1 1.00
14 11 11 1 1.00
15 57 57 1 1.00
16 85 85 1 1.00
17 101 102 2 1.06
18 126 126 1 1.06
19 91 91 1 1.05
20 9 9 1 1.05
21 52 52 1 1.05
22 53 53 1 1.05
23 109 109 1 1.04
24 33 33 1 1.04
25 51 51 1 1.04
26 108 108 1 1.04
27 84 84 1 1.04
28 102 103 2 1.07
29 38 38 1 1.07
30 103 104 2 1.10
31 102 105 4 1.19
32 108 110 3 1.25
33 96 96 1 1.24
34 13 13 1 1.24
35 85 86 2 1.26
36 94 95 2 1.28
37 7 7 1 1.27
38 97 97 1 1.26
39 75 75 1 1.26
40 20 20 1 1.25
41 12 14 3 1.29
42 59 59 1 1.29
43 52 56 5 1.37
44 123 123 1 1.36
45 71 71 1 1.36
46 94 98 5 1.43
47 58 58 1 1.43
48 84 88 5 1.50
49 79 79 1 1.49
50 86 90 5 1.56
51 115 115 1 1.55
52 52 60 9 1.69
53 124 124 1 1.68
54 43 44 2 1.69
55 54 61 8 1.80
56 99 99 1 1.79
57 26 26 1 1.77
58 95 100 6 1.84
59 44 45 2 1.85
60 3 3 1 1.83
61 77 77 1 1.82
62 66 66 1 1.81
63 8 8 1 1.79
64 9 10 2 1.80
65 35 35 1 1.78
66 14 16 3 1.80
67 116 116 1 1.79
68 4 4 1 1.78
69 88 92 5 1.83
70 94 106 13 1.99
71 45 46 2 1.99
72 55 62 8 2,07
73 74 74 1 2,05
74 106 107 2 2,05
75 74 76 3 2,07
76 4 5 2 2,07
77 27 27 1 2,05
78 25 25 1 2,04
79 59 63 5 2,08
80 32 32 1 2,06
81 5 6 2 2,06
82 98 111 14 2,21
83 117 117 1 2,19
84 31 31 1 2,18
85 92 93 2 2,18
86 124 125 2 2,17
87 74 78 5 2,21
88 78 80 3 2,22
89 67 67 1 2,20
90 98 112 15 2,34
91 119 120 2 2,34
92 88 113 26 2,60
93 15 17 3 2,60
94 31 34 4 2,62
95 92 114 23 2,83
96 64 64 1 2,81
97 89 118 30 3.09
98 113 121 9 3.15
99 108 122 15 3.27
100 43 47 5 3.29
101 67 68 2 3.28
102 59 65 7 3.31
103 68 69 2 3.30
104 121 127 7 3.34
105 104 128 25 3.54

It was difficult to get exact times so not all are totally correct. The increments along a search were 4 frames per position (0.25secs at 16 frames per sec).

The relevant FORTRAN files if you have a compiler are: