You are viewing a plain text version of this content. The canonical link for it is here.
Posted to c-dev@xerces.apache.org by "Gareth Reakes (JIRA)" <xe...@xml.apache.org> on 2005/04/05 10:43:16 UTC
[jira] Created: (XERCESC-1398) RefHashTable resize may be inefficient
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: xerces-c-dev-unsubscribe@xml.apache.org
For additional commands, e-mail: xerces-c-dev-help@xml.apache.org