order independent hash?

[Chris Angelico]

On Sat, Dec 10, 2011 at 3:51 AM, Hrvoje Niksic <hniksic at xemacs.org> wrote:
> The case of dicts which require frequent access, such as those used to
> implement namespaces, is different, and more interesting.  Those dicts
> are typically quite small, and for them the difference between O(log n)
> and O(1) is negligible in both theory (since n is "small", i.e. bounded)
> and practice.  In fact, depending on the details of the implementation,
> the lookup in a small tree could even be marginally faster.

This is something where, I am sure, far greater minds than mine
delve... but, would a splay tree be effective for name lookups? In
most cases, you'll have a huge puddle of names of which you use the
tiniest fraction; and a splay tree would, in effect, automatically
optimize itself to handle tight loops.

ChrisA