RefHashTable resize may be inefficient
--------------------------------------
Key: XERCESC-1398
URL: http://issues.apache.org/jira/browse/XERCESC-1398
Project: Xerces-C++
Type: Improvement
Components: Utilities
Versions: 2.6.0
Reporter: Gareth Reakes
Comment by David Bertoni [25/Feb/05 03:14 AM]
I've also noticed that many places in the code, people have been careful to
provide a prime number as the bucket count for hash tables, presumably for
better distribution. However, when the table grows, we multiply the initial
hash by 2, which means the bucket count is no longer a prime number. Should we
be concerned?
I can think if a couple of other choices:
1. choose the first prime number that's less than the original bucket count * 2
(or the first that's greater).
2. extend the HasherBase class to provide the new bucket count.
Comment by Gareth Reakes [25/Feb/05 10:28 AM]
I committed that patch David. For your next problem, is there any nice way of
finding the nearest prime? I know its not possible except through brute force,
but would most of the time do. For example, I found this
In each 30 integers, for N >= 1, the numbers that might be prime are
N*30+1,
N*30+7,
N*30+11,
N*30+13,
N*30+17,
N*30+19,
N*30+23,
N*30+29
how often does that hold? Could we just ensure the next number is divisable by
30 and add 1 and say thats OK most of the time? Otherwise we could populate a
structure with some primes during startup. How big is the table likely to get?
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
If you want more information on JIRA, or have a bug to report see:
http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
