Thu Feb 1 05:03:00 GMT 2001
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
More information about the Java