A better hash function for an Equivalence?

Question

The following is an implementation of Guava's Equivalence for Jackson's JsonNode for the needs of JSON Schema: in certain situations, all JSON numbers need to be compared mathematically (ie, 1.0 is equal to 1) but JsonNode (accurately) considers them non equal.

So, instead of extending JsonNode, I use this code, which works:

public final class JsonNodeEquivalence
    extends Equivalence<JsonNode>
{
    // snip

    @Override
    protected boolean doEquivalent(final JsonNode a, final JsonNode b)
    {
        /*
         * If both are numbers, delegate to appropriate method
         */
        if (a.isNumber() && b.isNumber())
            return numEquals(a, b);

        final NodeType typeA = NodeType.getNodeType(a);
        final NodeType typeB = NodeType.getNodeType(b);

        /*
         * If they are of different types, no dice
         */
        if (typeA != typeB)
            return false;

        /*
         * For all other primitive types than numbers, trust JsonNode
         */
        if (!a.isContainerNode())
            return a.equals(b);

        /*
         * OK, so they are containers (either both arrays or objects due to the
         * test on types above). They are obviously not equals if they do not
         * have the same number of elements/members.
         */
        if (a.size() != b.size())
            return false;

        /*
         * Delegate to the appropriate method according to their type.
         */
        return typeA == NodeType.ARRAY ? arrayEquals(a, b) : objectEquals(a, b);
    }

    @Override
    protected int doHash(final JsonNode t)
    {
        /*
         * If this is a numeric node, we want the same hashcode for the same
         * mathematical values. Go with double, its range is good enough for
         * 99+% of use cases.
         */
        if (t.isNumber())
            return Double.valueOf(t.doubleValue()).hashCode();

        /*
         * If this is a primitive type (other than numbers, handled above),
         * delegate to JsonNode.
         */
        if (!t.isContainerNode())
            return t.hashCode();

        /*
         * The following hash calculations work, yes, but they are poor at best.
         * And probably slow, too.
         *
         * TODO: try and figure out those hash classes from Guava
         */
        int ret = 0;

        /*
         * If the container is empty, just return
         */
        if (t.size() == 0)
            return ret;

        /*
         * Array
         */
        if (t.isArray()) {
            for (final JsonNode element : t)
                ret = 31 * ret + doHash(element);
            return ret;
        }

        /*
         * Not an array? An object.
         */
        final Iterator<Map.Entry<String, JsonNode>> iterator = t.fields();

        Map.Entry<String, JsonNode> entry;

        while (iterator.hasNext()) {
            entry = iterator.next();
            ret = 31 * ret
                + (entry.getKey().hashCode() ^ doHash(entry.getValue()));
        }

        return ret;
    }

    private static boolean numEquals(final JsonNode a, final JsonNode b)
    {
        /*
         * If both numbers are integers, delegate to JsonNode.
         */
        if (a.isIntegralNumber() && b.isIntegralNumber())
            return a.equals(b);

        /*
         * Otherwise, compare decimal values.
         */
        return a.decimalValue().compareTo(b.decimalValue()) == 0;
    }

    private boolean arrayEquals(final JsonNode a, final JsonNode b)
    {
        /*
         * We are guaranteed here that arrays are the same size.
         */
        final int size = a.size();

        for (int i = 0; i < size; i++)
            if (!doEquivalent(a.get(i), b.get(i)))
                return false;

        return true;
    }

    private boolean objectEquals(final JsonNode a, final JsonNode b)
    {
        /*
         * Grab the key set from the first node
         */
        final Set<String> keys = Sets.newHashSet(a.fieldNames());

        /*
         * Grab the key set from the second node, and see if both sets are the
         * same. If not, objects are not equal, no need to check for children.
         */
        final Set<String> set = Sets.newHashSet(b.fieldNames());
        if (!set.equals(keys))
            return false;

        /*
         * Test each member individually.
         */
        for (final String key: keys)
            if (!doEquivalent(a.get(key), b.get(key)))
                return false;

        return true;
    }
}

However, I am dissatisfied with doHash()'s calculation for JSON arrays and objects. I cannot judge of its distribution quality, but most of all, since this can be called quite often in some situations, I'd like to make it faster.

As explained above, the requirement is that all numeric nodes will equal mathematical values have the same hash code.

What do you propose?

EDIT: since then I have figured out how to use Guava's hashing functions, so I attempted to use them and compare performance. To use it, you need to create a Funnel for your object class and inject it into a Hasher issued from a HashFunction.

So I wrote the funnel and tried and used a .goodFastHash(32) (since the result is ultimately a hash code). But it was three times slower than the already existing code. To do better, I guess I'd have to calculate the hash while parsing the JSON itself, but it kind of defeats the purpose of using an external JSON library to begin with :/

Answer 1

Working through your code i Have found very few things to criticise....

1. I like the way you are using final.
2. I like the general layout and structure
3. using compareTo on the BigDecimals is the right thing to do.

If I have one complaint about your 'style', it is that your comments are too verbose...

As for your question about the hashCode of Collection-like data members....

I have inspected the source code for both ObjectNode and ArrayNode.

In each case they implement reasonable hashes given some constraints.

You need to answer three questions:

1. do you know these are static data members (you are not changing their internal values)?
2. The arrays may contain numbers just so long as the result for the array is consistent?
3. do you trust the array members to have reasonably-well distributed hash values?

If you feel like you should implement your own hash, then consider the following:

    // start the hash off with a value that's unique to the size.
    int ret = t.size();

    /*
     * If the container is empty, just return
     */
    if (ret == 0)
        return 1;

    /*
     * Array
     */
    if (t.isArray()) {
        // prime-number tricks like *31 are to ensure distributions.
        // we don't really care too much.... but we can shift easily...
        // 13 and 19 are prime numbers that add to 32 -- making a relatively
        // long loop-around time.
        // rotate the hash 19 bits, and XOR with the next element.
        for (final JsonNode element : t)
            ret = ((ret >>> 13) | (ret << 19)) ^ doHash(element);
        return ret;
    }

    /*
     * Not an array? An object.
     */
    final Iterator<Map.Entry<String, JsonNode>> iterator = t.fields();

    while (iterator.hasNext()) {
        final Map.Entry<String, JsonNode> entry = iterator.next();
        ret ^= entry.getKey().hashCode();
        ret =  ((ret >>> 13) | (ret << 19)) ^ doHash(entry.getValue()));
    }

    return ret;

Messing with bitwise functions vs. *31 is a JVM-dependant fix. I have had successes and failures with it....

... to clarify what I mean here, I have one specific example in mind:

consider the difference between (ret * 31) ^ hash and ((ret << 5) - ret) ^ hash. I have known the second one to be both significantly faster, and significantly slower.....

Edit: Discussion about prime-number shifts:

public static void main(String[] args) {

    // sorted array of 1-bit integer values
    int[] bitsets = new int[32];
    for (int i = 0; i < bitsets.length; i++) {
        bitsets[(i + 1) % 32] = 1 << i;
    }

    int[] cnt = new int[32];
    int val = 1;
    for (int i = 0; i < 1000; i++) {
        val = (val >>> 13) | (val << 19);
        int pos = Arrays.binarySearch(bitsets, val);
        cnt[pos]++;
    }
    System.out.println("Bit Distributions: " + Arrays.toString(cnt));
}

The above code results in:

Bit Distributions: [32, 31, 31, 31, 31, 31, 32, 32, 31, 31, 31, 31, 31, 32, 31, 31, 31, 31, 31, 32, 32, 31, 31, 31, 31, 32, 32, 31, 31, 31, 31, 31]

What this means, is that by shifting with relatively large primes, it takes a while for the same bit-pattern to repeat, and also, the coverage of the entire bit range is comprehensive. This is like the Cicada 17-year cycles and 13-year cycles, etc. making sure that no two species of cicada are (often) emerging in the same years.

It means that the each bit in each input hash is used to affect every other bit in subsequent hash values as much as possible (and it affects itself as little as possible because an XOR with yourself is always 0).