[jira] [Created] (LUCENE-6793) NumericRangeQuery.hashCode() produces frequent collisions

["J.B. Langston (JIRA)" <ji...@apache.org>]

J.B. Langston created LUCENE-6793:
-------------------------------------

             Summary: NumericRangeQuery.hashCode() produces frequent collisions
                 Key: LUCENE-6793
                 URL: https://issues.apache.org/jira/browse/LUCENE-6793
             Project: Lucene - Core
          Issue Type: Bug
    Affects Versions: 5.3, 4.6
            Reporter: J.B. Langston


We have a user who is developing a Solr plugin and needs to store NumericRangeQuery objects in a hash table.  They found that NumericRangeQuery.hashCode() produces extremely frequent collisions.  I understand that the contract for hashCode doesn't (and can't) guarantee unique hash codes for every value, but the distribution of this method seems particularly bad with an affinity for the hash value 897548010. Out of a set of 31 ranges, hashCode returned 897548010 14 times. This is going to result in very inefficient distribution of the objects in the hash table. The standard "times 31" hash function recommended by Effective Java fares quite a bit better, although it still produces quite a few collisions.  Here's a test case that compares the results of the current hashCode function with the times 31 method.  An even better method, like Murmur3 might be found here: http://floodyberry.com/noncryptohashzoo/

{code}
package com.company;

import org.apache.lucene.search.NumericRangeQuery;

public class Main {

    public static int betterHash(NumericRangeQuery query) {
        final int prime = 31;
        int result = 1;
        result = prime * result + Float.floatToIntBits(query.getBoost());
        result = prime * result + query.getRewriteMethod().hashCode();
        if (query.getField() != null) result = prime * result + query.getField().hashCode();

        result = result * prime + query.getPrecisionStep();
        if (query.getMin() != null) result = result * prime + query.getMin().hashCode();
        if (query.getMax() != null) result = result * prime + query.getMax().hashCode();
        result = result * prime + Boolean.valueOf(query.includesMin()).hashCode();
        result = result * prime + Boolean.valueOf(query.includesMax()).hashCode();
        return result;
    }

    public static void main(String[] args) {
        long previous = Long.MIN_VALUE;
        long[] list = {
                -9223372036854775798L,
                -8608480567731124078L,
                -7993589098607472357L,
                -7378697629483820637L,
                -6763806160360168916L,
                -6148914691236517196L,
                -5534023222112865475L,
                -4919131752989213755L,
                -4304240283865562034L,
                -3689348814741910314L,
                -3074457345618258593L,
                -2459565876494606873L,
                -1844674407370955152L,
                -1229782938247303432L,
                -614891469123651711L,
                10L,
                614891469123651730L,
                1229782938247303451L,
                1844674407370955171L,
                2459565876494606892L,
                3074457345618258612L,
                3689348814741910333L,
                4304240283865562053L,
                4919131752989213774L,
                5534023222112865494L,
                6148914691236517215L,
                6763806160360168935L,
                7378697629483820656L,
                7993589098607472376L,
                8608480567731124097L,
                Long.MAX_VALUE
        };

        for (long current : list) {
            NumericRangeQuery<Long> query =  NumericRangeQuery.newLongRange("_token_long", 8, previous, current, true, true);
            System.out.println("[" + previous + " TO " + current + "]: " + query.hashCode() + " / " + betterHash(query));
            previous = current + 1;
        }
    }
}
{code}



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org