This is the mail archive of the java@gcc.gnu.org mailing list for the Java project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: String hashCode


Tom Tromey <tromey@redhat.com> writes:

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

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

Frankly, I think dropping hashing is a mistake.  The intern table
will probably take a lot more space when using a tree than when
using a hash table.  And I think the need for this change is
questionable.  This is only needed for "hard real-time" - do we
really think libgcj is ready for such uses?

> Anyway, the new data structure uses String.compareTo and not the hash
> code.  So speeding it up won't help intern().

How about using comparing hashCodes instead of Strings?  It is obviously
much faster to compare int (assuming they are pre-computed) instead
of lexicographically comparing Strings.  Of course you need a fall-back
for Strings that have the same hashCode - in those cases compare
lexicographically.
-- 
	--Per Bothner
per@bothner.com   http://www.bothner.com/~per/

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]