// // Test hash clashes // size = 101 NUMFORMAT (5, 0) DIM words$(100000) DIM hsh(100000) wordFd = OPEN ("words") i = 0 WHILE NOT EOF (wordFd) CYCLE INPUT# wordFd, x$ // IF LEN (x$) = 1 THEN CONTINUE i = i + 1 words$(i) = x$ hsh(i) = HASH (x$, size) REPEAT wCount = i PRINT "Read in "; wCount; " words." PRINT "Sorting..."; UPDATE PROC sort(hsh()) PRINT "Done" PRINT // i = 1 WHILE i < wCount CYCLE clashes = 0 h1 = hsh(i) j = i + 1 WHILE hsh(j) = h1 CYCLE clashes = clashes + 1 j = j + 1 REPEAT i = j REPEAT PRINT "Clashes: "; clashes NUMFORMAT (0, 0) PRINT "Clash probability for modulo "; size; " = "; NUMFORMAT (5, 2) PRINT clashes / wCount * 100; "%" END // // PROC sort: // Sort an array of numbers // DEF PROC sort(a()) LOCAL i, j, k, l, m m = wCount DIV 2 WHILE m > 0 CYCLE j = m WHILE j < wCount CYCLE i = j - m WHILE i >= 0 CYCLE k = i + m IF a(k) < a(i) THEN // swap (a(i),a(k)) tmp = a(i) a(i) = a(k) a(k) = tmp ELSE BREAK ENDIF i = i - m REPEAT j = j + 1 REPEAT m = m DIV 2 REPEAT ENDPROC