Re: String hashCode

[Andrew Haley <aph at redhat dot com>]

Bryce McKinlay writes:
 > Tom Tromey wrote:
 > 
 > > FYI I've been planning to change the data structure used for
 > > String.intern.  I have a patch to do this already; I'll check it in
 > > after the branch is made.
 > >
 > > The new data structure is an STL map<> (a red-black tree).  I chose
 > > this because it has better worst-case performance than the existing
 > > hash table and is therefore better for real-time usage.  The hash
 > > table is bad because rehashing makes the worst case expensive.
 > 
 > Tom, I'm not sure that a btree-based structure is the best choice for the
 > intern table. Its easy to imagine  situations where a bunch of Strings
 > would be interned in lexographical order, in which case the tree would
 > perform poorly.

Well, even in that case a red-black tree guarantees all operationa in
O(lg n) time.  Sure, it's a compromise, but not such a bad one.  I
guess the real issue is the ratio of insertions to lookups; I wonder
if there's a typical figure that might help us to make a decision
based on something solid.

 > Also, by using an STL structure you're adding a dependency on libstdc++

I wondered about this.  Tom assures me that this dependency exists
only during compilation, and that libstdc++.so is not required at
runtime.

Andrew.