Re: String hashCode

[Tom Tromey <tromey at redhat dot com>]

>> 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.

Per> There are hash algorithms that grow the table gradually.  Search
Per> for "dynamic hashing".  ACM Computing Surveys (June 88) has an
Per> overview article.  So I don't think rehashing is a justification
Per> to replace hashing by red-black trees.  The only reason to drop
Per> hashing is you don't believe in statistics.

I don't agree that that is the only reason.

For instance, one other reason might be that I had a limited amount of
time to change the implementation, and while I had a ready-made
implementation of red-black tress, I didn't have an implementation of
a dynamic hash table.

I actually don't see what believing in statistics has to do with
anything.  In my situation I'm concerned with worst case performance.
In the worst case the existing hash table code is clearly worse,
time-wise, than a red-black tree.

Per> Frankly, I think dropping hashing is a mistake.  The intern table
Per> will probably take a lot more space when using a tree than when
Per> using a hash table.

It will take more space, true.  I don't know if it is "a lot" more.
But then, I don't even know how heavily interning is typically used.

In my case the customer I wrote this for is using a third party
library that apparently calls intern() on every String in sight.  So
they are very concerned about resizing the table, but apparently not
as concerned about table overhead.

Per> And I think the need for this change is questionable.  This is
Per> only needed for "hard real-time" - do we really think libgcj is
Per> ready for such uses?

I think this is an argument for the change, and not an argument
against it.  libgcj will never be ready unless we make changes to make
it ready.

Tom