An even better (nonmagical) dictionary

[luser- -droog]

I'm starting to think about moving up to level 2, and one of
the major hurdles is the expanded powers of dictionaries.
Now they have to be growable. And you can undefine things.

So my idea is a hybrid hashtable/search-tree. If two keys
collide in the table, that table entry is labelled as a
collisiontype and the value slot is set to hold a pointer
to the root of a little search tree to resolve the keys.
If I use ternary trees, I can implement the string-name
conversion on top of it.

The downside is that save/restore might have more
work to do, traversing and copying all those nodes.

One corollary of all this is that the declared size of the
dict becomes significant for performance reasons. You
can dial-in the hash-vs-tree speedup by keeping your
dicts about half-full. You could even optimize further
by rounding up to a prime or some such nonsense.

Any thoughts?