At a local level, I would expect that a good hash table implementation
will give the most consistent performance. However, you might be able
to improve on it with an array or linked list for some operations, or
in some inernal classes. If you really want to find out which is
better, then implement both and compare the runtime performance. There
are just too many variables in this case to know which will be faster
overall.

Hash tables, alists, red/black trees, splay trees, etc., all have
different performance based on the number of keys to be compared, cost
of key comparison, balance of read vs. write operations, etc. It's
probably best to implement the clean, naive version (i.e., hash
tables), and then tweak the performance from there.

Lennon