[Oberon] How to mimic an associative array

[Yaroslav Romanchenko]

Simple implementation of string hash.

MODULE StringHash;

IMPORT

	Strings, Commands;

CONST

	(* Prime number for hash table *)
	PRIME = 977;

TYPE

	HashTable  = ARRAY PRIME OF
		RECORD
			key, value: Strings.String;
		END;

VAR
	hash: HashTable;
	nCollisions: LONGINT;

	PROCEDURE hashSearch(bAddAllowed: BOOLEAN; CONST key: ARRAY OF CHAR; VAR value: Strings.String): BOOLEAN;
	VAR
		d: INTEGER;
		i, h: LONGINT;
		bFound, bExit: BOOLEAN;
	BEGIN

		bExit := FALSE;
		bFound := FALSE;
		d := 1;

		(* simple hash function *)
		h := 0;
		FOR i := 0 TO Strings.Length(key) - 1 DO
			h := (h + ORD(key[i])) MOD PRIME
		END;

		WHILE ~(bFound OR bExit) DO
			IF hash[h].key = NIL THEN (* new entry *)
				bExit := TRUE;
				IF bAddAllowed THEN
					hash[h].key := Strings.NewString(key);
					hash[h].value := value
				END
			ELSIF hash[h].key^ = key THEN (* match *)
				bFound := TRUE;
				value := hash[h].value
			ELSE (* collision *)

				INC(nCollisions);

				h := h + d; d := d + 2;
				IF h >= PRIME THEN h := h - PRIME END;

				(* Table owerflow! *)
				IF d = PRIME THEN
					bExit := TRUE;
					ASSERT(d # PRIME)
				END

			END
		END;

		RETURN bFound

	END hashSearch;
	
PROCEDURE Test*(context: Commands.Context);
VAR
	b: BOOLEAN;
	s: Strings.String;
BEGIN
	(* Add entries *)
	s := Strings.NewString("Duke");
	b := hashSearch(TRUE, "name", s);
	s := Strings.NewString("63");
	b := hashSearch(TRUE, "age", s);
	
	context.out.Ln;
	(* Try to find entries *)
	IF hashSearch(FALSE, "name", s) THEN
		context.out.String(s^); context.out.Ln
	END;
	IF hashSearch(FALSE, "age", s) THEN
		context.out.String(s^); context.out.Ln
	END;
	
END Test;

PROCEDURE HashStat*(context: Commands.Context);
VAR
	i, n: INTEGER;
BEGIN
	n := 0;
	FOR i := 0 TO PRIME - 1 DO
		IF hash[i].key # NIL THEN
			INC(n)
		END
	END;
	IF n = 0 THEN
		context.out.Ln;
		context.out.String("Hash table not yet initialized.");
		context.out.Ln
	ELSE
		context.out.Ln;
		context.out.Int(n, 1);
		context.out.String(" of ");
		context.out.Int(PRIME, 1);
		context.out.String(" hash table cells used. Ratio: ");
		context.out.Float(n / PRIME, 20);
		context.out.Ln;
		context.out.String("Number of collisions: ");
		context.out.Int(nCollisions, 1);
		context.out.Ln
	END
END HashStat;


PROCEDURE Init;
VAR
	i: INTEGER;
BEGIN
	FOR i := 0 TO PRIME - 1 DO
		hash[i].key := NIL;
		hash[i].value := NIL;
	END
END Init;

BEGIN
	Init
END StringHash.

StringHash.Test ~
StringHash.HashStat ~

SystemTools.Free StringHash~


---
Cheers, SAGE
http://sage.com.ua/