Hash tables in Algol 68
last modified November 14, 2026
A hash table turns a key into a slot number and stores the value there, so a lookup costs one arithmetic step plus the probes that collisions add. Algol 68 has the two pieces the structure needs, a row for the slots and procedures for the hash and the probes, and its rows make the slot count and the load factor easy to compute.
This article builds a table with linear probing and string keys, handles collisions, grows the table when it fills, counts the words of a sentence, and explains why deletion is the one operation left out.
Slots and a hash function
Each slot holds a key, a value, and a flag that says whether the slot has ever been used. The flag separates an empty slot from one whose key is the empty string, and it is what stops a search at the first gap. The table itself holds the row of slots and the number of keys stored.
MODE ENTRY = STRUCT (STRING key, INT value, BOOL used);
MODE TABLE = STRUCT (REF FLEX [] ENTRY slots, INT count);
PROC new table = (INT size) TABLE:
(
REF FLEX [] ENTRY slots = HEAP FLEX [0:size - 1] ENTRY;
FOR i FROM LWB slots TO UPB slots DO
slots[i] := ("", 0, FALSE)
OD;
(slots, 0)
);
PROC hash = (STRING key, INT size) INT:
(
INT h := 0;
FOR i FROM LWB key TO UPB key DO
h := (h * 31 + ABS key[i]) MOD size
OD;
h
);
BEGIN
[]STRING names = ("one", "three", "four", "two");
FOR i TO UPB names DO
print((names[i], " -> ", whole(hash(names[i], 8), 0), newline))
OD;
TABLE t := new table(8);
print((whole(UPB slots OF t + 1, 0), " slots", newline))
END
The row is allocated on the heap with bounds 0 to size - 1,
because the hash produces a remainder in that range. The hash itself is a
polynomial: each character multiplies the running value by 31 and adds its
code, and the result is reduced modulo the table size at every step so that it
never overflows.
The demo hashes four words into a table of eight slots. Three of them land on slot 6, which is the collision that the next section has to handle, and the fourth lands on slot 4.
$ a68g hash1.a68 one -> 6 three -> 6 four -> 6 two -> 4 8 slots
Insert and find
Insertion computes the starting slot and then probes forward, one slot at a time, wrapping around at the end. It stops at the first empty slot, where the key is stored, or at a slot that already holds the same key, where the value is replaced. The probe is bounded by the table size, so a full table ends the search instead of looping forever.
MODE ENTRY = STRUCT (STRING key, INT value, BOOL used);
MODE TABLE = STRUCT (REF FLEX [] ENTRY slots, INT count);
PROC new table = (INT size) TABLE:
(
REF FLEX [] ENTRY slots = HEAP FLEX [0:size - 1] ENTRY;
FOR i FROM LWB slots TO UPB slots DO
slots[i] := ("", 0, FALSE)
OD;
(slots, 0)
);
PROC hash = (STRING key, INT size) INT:
(
INT h := 0;
FOR i FROM LWB key TO UPB key DO
h := (h * 31 + ABS key[i]) MOD size
OD;
h
);
PROC insert = (REF TABLE t, STRING key, INT value) VOID:
(
REF FLEX [] ENTRY slots = slots OF t;
INT size = UPB slots - LWB slots + 1;
INT start = hash(key, size);
BOOL placed := FALSE;
FOR step TO size WHILE NOT placed DO
INT j = (start + step - 1) MOD size;
BOOL fresh = NOT (used OF slots[j]);
IF fresh OR key OF slots[j] = key THEN
slots[j] := (key, value, TRUE);
IF fresh THEN count OF t +:= 1 FI;
placed := TRUE
FI
OD
);
PROC find = (REF TABLE t, STRING key, REF INT result) BOOL:
(
REF FLEX [] ENTRY slots = slots OF t;
INT size = UPB slots - LWB slots + 1;
INT start = hash(key, size);
BOOL found := FALSE;
BOOL stop := FALSE;
FOR step TO size WHILE NOT stop DO
INT j = (start + step - 1) MOD size;
IF NOT (used OF slots[j]) THEN
stop := TRUE
ELIF key OF slots[j] = key THEN
result := value OF slots[j];
found := TRUE;
stop := TRUE
FI
OD;
found
);
PROC show = (REF TABLE t) VOID:
(
REF FLEX [] ENTRY slots = slots OF t;
FOR i FROM LWB slots TO UPB slots DO
IF used OF slots[i] THEN
print((whole(i, 0), ": ", key OF slots[i], " = ",
whole(value OF slots[i], 0), newline))
FI
OD
);
BEGIN
TABLE t := new table(8);
insert(t, "one", 1);
insert(t, "three", 3);
insert(t, "four", 4);
insert(t, "two", 2);
INT v;
IF find(t, "three", v) THEN
print(("three is ", whole(v, 0), newline))
ELSE
print(("three is missing", newline))
FI;
IF find(t, "five", v) THEN
print(("five is ", whole(v, 0), newline))
ELSE
print(("five is missing", newline))
FI;
show(t);
print((whole(count OF t, 0), " keys", newline))
END
The search uses the same probe sequence as the insertion, and stops either at
an empty slot, which proves that the key is absent, or at the key itself. The
FOR step TO size clause bounds the walk, so a table with no empty
slot cannot hang the program: the loop simply ends and the key is not found.
$ a68g hash2.a68 three is 3 five is missing 0: four = 4 4: two = 2 6: one = 1 7: three = 3 4 keys
Collisions
The three words that hash to 6 show how the probe sequence fills the table.
one takes slot 6, three finds it occupied and moves
to 7, and four finds both occupied and wraps to 0. A later
search for three starts at 6, sees a used slot with a different
key, and moves to 7, where it finds the key.
"one" hashes to 6, slot 6 is empty -> store at 6
"three" hashes to 6, slot 6 holds "one" -> store at 7
"four" hashes to 6, slot 6 holds "one",
slot 7 holds "three" -> store at 0
"two" hashes to 4, slot 4 is empty -> store at 4
Linear probing keeps the table dense, which is good for the cache, but it tends to build runs of occupied slots that get longer as the table fills. The cost of a lookup is therefore related to the load factor, the ratio of stored keys to slots, and not only to the quality of the hash.
Growing the table
A table that never grows becomes slow and then full. When the next insertion would take the load above three quarters, the table allocates a row twice as large, reinserts every used entry, and continues. The row is flexible, so the field can be given a row with different bounds.
MODE ENTRY = STRUCT (STRING key, INT value, BOOL used);
MODE TABLE = STRUCT (REF FLEX [] ENTRY slots, INT count);
PROC new table = (INT size) TABLE:
(
REF FLEX [] ENTRY slots = HEAP FLEX [0:size - 1] ENTRY;
FOR i FROM LWB slots TO UPB slots DO
slots[i] := ("", 0, FALSE)
OD;
(slots, 0)
);
PROC hash = (STRING key, INT size) INT:
(
INT h := 0;
FOR i FROM LWB key TO UPB key DO
h := (h * 31 + ABS key[i]) MOD size
OD;
h
);
PROC size of = (TABLE t) INT:
UPB slots OF t - LWB slots OF t + 1;
PROC insert = (REF TABLE t, STRING key, INT value) VOID:
(
REF FLEX [] ENTRY slots = slots OF t;
INT size = UPB slots - LWB slots + 1;
INT start = hash(key, size);
BOOL placed := FALSE;
FOR step TO size WHILE NOT placed DO
INT j = (start + step - 1) MOD size;
BOOL fresh = NOT (used OF slots[j]);
IF fresh OR key OF slots[j] = key THEN
slots[j] := (key, value, TRUE);
IF fresh THEN count OF t +:= 1 FI;
placed := TRUE
FI
OD
);
PROC grow = (REF TABLE t) VOID:
(
REF FLEX [] ENTRY old = slots OF t;
INT new size = 2 * (UPB old - LWB old + 1);
REF FLEX [] ENTRY fresh = HEAP FLEX [0:new size - 1] ENTRY;
FOR i FROM LWB fresh TO UPB fresh DO
fresh[i] := ("", 0, FALSE)
OD;
slots OF t := fresh;
count OF t := 0;
FOR i FROM LWB old TO UPB old DO
IF used OF old[i] THEN
insert(t, key OF old[i], value OF old[i])
FI
OD
);
PROC put = (REF TABLE t, STRING key, INT value) VOID:
(
IF (count OF t + 1) * 4 > size of(t) * 3 THEN
grow(t)
FI;
insert(t, key, value)
);
BEGIN
TABLE t := new table(8);
FOR i TO 9 DO
put(t, "key" + whole(i, 0), i);
print((whole(size of(t), 0), " slots, ", whole(count OF t, 0), " used", newline))
OD
END
The order matters: grow calls insert, so
insert is declared first, and the load check lives in
put, which calls both. Reusing the old entries through
insert recomputes their hash against the new size, which is the
whole point of a rehash: a key that sat in slot 6 of eight lands in slot 6 or
14 of sixteen.
$ a68g hash3.a68 8 slots, 1 used 8 slots, 2 used 8 slots, 3 used 8 slots, 4 used 8 slots, 5 used 8 slots, 6 used 16 slots, 7 used 16 slots, 8 used 16 slots, 9 used
Counting words
A word count is the classic use of the structure: every word is a key, and the value is how many times it has been seen. The text is scanned twice per word, once to skip spaces and once to find the end of the word, and each word is looked up and either incremented or inserted.
MODE ENTRY = STRUCT (STRING key, INT value, BOOL used);
MODE TABLE = STRUCT (REF FLEX [] ENTRY slots, INT count);
PROC new table = (INT size) TABLE:
(
REF FLEX [] ENTRY slots = HEAP FLEX [0:size - 1] ENTRY;
FOR i FROM LWB slots TO UPB slots DO
slots[i] := ("", 0, FALSE)
OD;
(slots, 0)
);
PROC hash = (STRING key, INT size) INT:
(
INT h := 0;
FOR i FROM LWB key TO UPB key DO
h := (h * 31 + ABS key[i]) MOD size
OD;
h
);
PROC insert = (REF TABLE t, STRING key, INT value) VOID:
(
REF FLEX [] ENTRY slots = slots OF t;
INT size = UPB slots - LWB slots + 1;
INT start = hash(key, size);
BOOL placed := FALSE;
FOR step TO size WHILE NOT placed DO
INT j = (start + step - 1) MOD size;
BOOL fresh = NOT (used OF slots[j]);
IF fresh OR key OF slots[j] = key THEN
slots[j] := (key, value, TRUE);
IF fresh THEN count OF t +:= 1 FI;
placed := TRUE
FI
OD
);
PROC find = (REF TABLE t, STRING key, REF INT result) BOOL:
(
REF FLEX [] ENTRY slots = slots OF t;
INT size = UPB slots - LWB slots + 1;
INT start = hash(key, size);
BOOL found := FALSE;
BOOL stop := FALSE;
FOR step TO size WHILE NOT stop DO
INT j = (start + step - 1) MOD size;
IF NOT (used OF slots[j]) THEN
stop := TRUE
ELIF key OF slots[j] = key THEN
result := value OF slots[j];
found := TRUE;
stop := TRUE
FI
OD;
found
);
PROC count word = (REF TABLE t, STRING word) VOID:
(
INT n;
IF find(t, word, n) THEN
insert(t, word, n + 1)
ELSE
insert(t, word, 1)
FI
);
PROC count words = (REF TABLE t, STRING text) VOID:
(
INT i := LWB text;
WHILE i <= UPB text DO
BOOL skipping := TRUE;
WHILE skipping DO
IF i > UPB text THEN
skipping := FALSE
ELIF text[i] = " " THEN
i +:= 1
ELSE
skipping := FALSE
FI
OD;
INT start := i;
BOOL reading := TRUE;
WHILE reading DO
IF i > UPB text THEN
reading := FALSE
ELIF text[i] = " " THEN
reading := FALSE
ELSE
i +:= 1
FI
OD;
IF start < i THEN
count word(t, text[start:i - 1])
FI
OD
);
PROC report = (REF TABLE t) VOID:
(
REF FLEX [] ENTRY slots = slots OF t;
REF FLEX [] ENTRY list = HEAP FLEX [1:count OF t] ENTRY;
INT n := 0;
FOR i FROM LWB slots TO UPB slots DO
IF used OF slots[i] THEN
n +:= 1;
list[n] := slots[i]
FI
OD;
FOR i FROM 2 TO n DO
ENTRY e = list[i];
INT j := i - 1;
BOOL moving := TRUE;
WHILE moving DO
IF j < 1 THEN
moving := FALSE
ELIF key OF list[j] > key OF e THEN
list[j + 1] := list[j];
j -:= 1
ELSE
moving := FALSE
FI
OD;
list[j + 1] := e
OD;
FOR i TO n DO
print((key OF list[i], " ", whole(value OF list[i], 0), newline))
OD
);
BEGIN
TABLE t := new table(64);
count words(t, "the quick brown fox jumps over the lazy dog the fox");
report(t);
print((whole(count OF t, 0), " distinct words", newline))
END
The report collects the used entries into a row, sorts them by key with an insertion sort, and prints them. Without the sort the words would appear in slot order, which is the hash order and looks arbitrary to a reader. The table is created with 64 slots for a sentence of nine words, because a table that is sized for the expected input never has to grow while it is being filled.
$ a68g words.a68 brown 1 dog 1 fox 2 jumps 1 lazy 1 over 1 quick 1 the 3 8 distinct words
Deleting entries
Deletion is left out of the table above, and not because it is difficult to write. Clearing a slot would break every search whose probe sequence passed through it: a later key that had been pushed past the deleted slot would find an empty slot first and be reported as absent, although it is still stored.
The usual repair is a tombstone, a third state that marks a slot as deleted but not empty. A search probes past a tombstone, an insertion may reuse it, and the table is rebuilt when the tombstones outnumber the live keys. The entry mode then needs two flags instead of one, and the load factor has to count both live entries and tombstones.
The cost of the table
A lookup costs one hash, which is proportional to the length of the key, plus the probes. With a good hash and a load factor below three quarters the average number of probes is small and constant, so the table gives the usual average constant-time insert and find. The worst case is a run of keys that all hash to the same slot, and then a lookup walks the whole run.
The polynomial hash is not cryptographic: two different keys can be made to collide deliberately, and the multiplier 31 is a common choice rather than a strong one. For a dictionary of words, a symbol table in an interpreter, or a cache, that is enough. The searching article compares the table with binary search, and the structures article explains the field selection that the entry mode uses.
Source
Revised Report on the Algorithmic Language Algol 68
In this article we hashed string keys with a polynomial, stored entries in a row of slots, probed linearly for collisions, grew the table at a load factor of three quarters, counted the words of a sentence, and explained why deletion needs tombstones.
Author
List all Algol 68 tutorials.