[Oberon] How to mimic an associative array

[Stauber Sven Philipp]

Hi Duke,

I'm somewhat confused because of the term "hashing". I guess what you want is something like:

TYPE

String = ARRAY <someSize> OF CHAR; (* in case you can live with fixed size strings *)

Dictionary = OBJECT
(* somehow store <key, value> pairs *)

	(* Get <value> associated with <key> *)
	PROCEDURE Get(key : String) : String;

	(* Put association <key, value> pair into dictionary *)
	PROCEDURE Put(key, value : String);

END Dictionary;

PROCEDURE foo(d : Dictionary)
VAR value : String;
BEGIN
	value := d.Get("blablah");
END foo;

The term "hashing" refers to the way of how the mapping of keys to values is implemented.

The Dictionary object above could, for example, store the <key, value> pairs in a linked list. The drawback would be that the lookup time grows linear with the number of <key, value> pairs.

A hashing-based implementation would compute a hash table index based on the value of key to avoid many key comparisons.

Example:

CONST
	HashTableSize = 128;

TYPE
	Entry = POINTER TO RECORD
		key, value : String;
		next : Entry;
	END;

	HashTable = ARRAY HashTableSize OF Entry;

VAR
	hashTable : HashTable; (* Initialize somewhere... *)	

PROCEDURE ComputeHash(key : String) : LONGINT;
VAR hash : LONGINT;
BEGIN
	hash := ORD(key[0]) MOD HashTableSize; (* simple hash function ;-) *)
	ASSERT((0 <= hash) & (hash < HashTableSize)); (* "documentation" *)
	RETURN hash;
END ComputeHash;

PROCEDURE Get(key : String) : String;
VAR entry : Entry; value : String;
BEGIN
	entry := hashTable[ComputeHash(key)];
	(* since multiple keys can result in the same hash value, there can be more than one entry per key (hash collision) or the entries' key is not equal to the key used for the hash value computation (needs to be compared!) *)
	WHILE (entry # NIL) & (entry.key # key) DO entry := entry.next; END; 
	IF (entry # NIL) THEN
		value := entry.value;
	ELSE
		value := "";
	END;
	RETURN value;
END Get;

Finally, this enables constant lookup time (not dependent on number of <key, value> pairs) in absence of hash collisions and linear lookup time in case of collisions (in the worst case, all keys map to the same hash value and you end up with a traversing linked list...).

If you don't worry about performance, an unsorted linked list implementation is the simplest you can do. If you can live with fixed size strings, the ARRAY <Size> OF CHAR representation does the job quite well (doesn't require dynamic memory for key & value, but wastes some space for strings shorter than the fixed size).
An interesting  compromise could be to have a fixed size key (enables idiom d.Get("blah")) but to make the values dynamic (POINTER TO ARRAY OF CHAR). This works well if you consider the values immutable (never change them) - otherwise you would have to allocate a new dynamic string for every lookup to avoid corruption of the dictionary.

Best,
Sven


-----Ursprüngliche Nachricht-----
Von: Duke Normandin [mailto:dukeofperl at ml1.net] 
Gesendet: Mittwoch, 1. Dezember 2010 18:23
An: oberon
Betreff: [Oberon] How to mimic an associative array

Hello list...

Given that Oberon-2 does not natively support associative arrays (aka hash; map - in other languages), I need to come up with a tailor-made equivalent. Still very much the Oberon/Modula/Pascal noob, I thinking that maybe a Record like:

     TYPE
        myHash = RECORD
             key : ARRAY <someLength> OF CHAR;
             value : ARRAY <someLength> OF CHAR;
        END;

Would that work? Is there a better solution? I'm going to test the above, of course, but I just thought that I'd get your input, before spinning my wheels too much. There tires/tyres and head are already bald enough. :)

--
Duke

--
Oberon at lists.inf.ethz.ch mailing list for ETH Oberon and related systems https://lists.inf.ethz.ch/mailman/listinfo/oberon