[
https://issues.apache.org/jira/browse/LUCENE-977?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Yonik Seeley resolved LUCENE-977.
---------------------------------
Resolution: Fixed
committed.
> internal hashing improvements
> -----------------------------
>
> Key: LUCENE-977
> URL: https://issues.apache.org/jira/browse/LUCENE-977
> Project: Lucene - Java
> Issue Type: Improvement
> Reporter: Yonik Seeley
> Attachments: hash.patch
>
>
> Internal power-of-two closed hashtable traversal in DocumentsWriter and
> CharArraySet could be better.
> Here is the current method of resolving collisions:
> if (text2 != null && !equals(text, len, text2)) {
> final int inc = code*1347|1;
> do {
> code += inc;
> pos = code & mask;
> text2 = entries[pos];
> } while (text2 != null && !equals(text, len, text2));
> The problem is that two different hashCodes with the same lower bits will
> keep picking the same slots (the upper bits will be ignored).
> This is because multiplication (*1347) only really shifts bits to the left...
> so given that the two codes already matched on the right, they will both pick
> the same increment, and this will keep them on the same path through the
> table (even though it's being added to numbers that differ on the left). To
> resolve this, some bits need to be moved to the right when calculating the
> increment.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
