Sorry, the example was not intended to be directly related to the 
subject at hand (ie. collections). It was only to reinforce the notion 
that looking very hard at how hash code's are handled can significantly 
affect performance in general.

And yes, one solution to the issue is to create an immutable collection. 
You might want to get fancy and make it so that immutable collections 
can be inside mutable collections so you can represent a tree (or just 
create specialized immutable tree data structure instead).

Either way, the difficulty might be in "enforcing" the immutability of 
the objects in the collection. At the least it could be "programmer 
beware", though it would be nice if it could be a little better.

-joel


Richard A. O'Keefe wrote:

>Joel Shellman <joel at ikestrel.com> wrote:
>	For another example of hash problems:
>	
>	It used to be that in the standard String class in Java, the hashCode 
>	was calculated every time it was called. This led to people recommending 
>	never to use String's as keys in Hashtables, but rather create their own 
>	Key class.
>	
>	Fortunately, they did change String's implementation so it now caches 
>	the hash code.
>	
>Since the only immutable Collection class in Squeak that I can call to mind
>is Interval, it's not clear to me that this example tells us anything useful.
>(Except that having some immutable collections might be a good idea.)
>
>Java has unmodifiable collections.  More precisely, if you ask for an
>unmodifiable version of a collection, you get an unmodifiable *wrapper*
>around the same modifiable collection you started with.  I don't know of
>any Java collections (Strings aren't Collections in Java) that cache their
>hash code.
>
>	That's another handy thing about immutable classes. You can cache the 
>	hash code without worrying about it changing.
>	
>Java's unmodifiable collections don't do this; since they are just
>wrappers around modifiable objects that might be changed by another route,
>I don't believe that they _could_ do this.
>  
>