CODEWITHSUNDEEP
java
MATH000
MATH000

Reputation: 1103

Faster hashCode() alternative?

Is there any way to make hashCode() faster? Of course I understand that this will probably result in more collisions, but I am OK with this trade off.

Does java have a way to "get the memory address of an Object, like C++ does?

edit: To be clear: I understand that hashCode() is fast. My goal is to make a hash function that is as fast as some C++ hash functions.

The type of item I will be hashing is not known.

Upvotes: 0

Views: 1137

Answers (3)

Peter Lawrey
Peter Lawrey

Reputation: 533432

Is there any way to make hashCode() faster?

Yes, many ways but it depends on what you are hashing.

Note: the built in Object.hashCode() takes around 40 ns.

Does java have a way to "get the memory address of an Object, like C++ does?

Yes, you can use Unsafe to do this, however this is a bad idea as the address of an object can change at any time making it useless as a hash.

This program triggers the re-calcuation of Object.hashCode().

Note: this is very hacky and might not work on all JVM or future JVMs. It is for education purposes only.

public class HashCodePerf {
    static int keep;

    public static void main(String[] args) {
        Object o = new Object();
        int runs = 20_000_000;
        for (int t = 0; t < 5; t++) {
            long start = System.nanoTime();
            for (int i = 0; i < runs; i++) {
                UNSAFE.putInt(o, 1L, 0); // reset the memory which stores the hashCode
                keep = o.hashCode(); // compute a new hashCode
            }
            long time = System.nanoTime() - start;
            System.out.printf("Object.hashCode takes %,d ns on average%n", time / runs);
        }
    }

    static final Unsafe UNSAFE;

    static {
        try {
            Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");
            theUnsafe.setAccessible(true);
            UNSAFE = (Unsafe) theUnsafe.get(null);
        } catch (Exception e) {
            throw new AssertionError(e);
        }
    }
}

prints on my Ultra-book

Object.hashCode takes 79 ns on average
Object.hashCode takes 43 ns on average
Object.hashCode takes 48 ns on average
Object.hashCode takes 43 ns on average
Object.hashCode takes 42 ns on average

Creating a very simple hash which is adding to counter.

static int keep, keep2;
static int counter;

public static void main(String[] args) {
    Object o = new Object();
    Object o2 = new Object();
    int runs = 100_000_000;
    for (int t = 0; t < 5; t++) {
        long start = System.nanoTime();
        for (int i = 0; i < runs; i+=2) {
            UNSAFE.putOrderedInt(o, 1L, (counter += 0x5bc80bad) & 0x7FFFFFFF);
            UNSAFE.putOrderedInt(o2, 1L, (counter += 0x5bc80bad) & 0x7FFFFFFF);
            keep = o.hashCode(); // reload the hashCode
            keep2 = o2.hashCode(); // reload the hashCode
        }
        long time = System.nanoTime() - start;
        System.out.printf("Object.hashCode takes %,d ns on average%n", time / runs);
    }
}

prints

Object.hashCode takes 5 ns on average
Object.hashCode takes 8 ns on average
Object.hashCode takes 5 ns on average
Object.hashCode takes 4 ns on average
Object.hashCode takes 4 ns on average

Note: normally the address of an object changes, but it's hashCode doesn't. In this case we have the objects with changing hashCode but with the same address.

Upvotes: 4

assylias
assylias

Reputation: 328568

If you want something similar to the object's address, you can use:

System.identityHashCode(obj);

If the hascode method is called many times, you can also cache/pre-calculate the result (assuming the object is immutable or at least that its hashcode does not change after construction).

class CashHashcode {
  private final int hash;
  CacheHashcode(...) {
    hash = computeHashFromArgs(...);
  }
  public int hashCode() { return hash; }
}

Upvotes: 0

Lukas Eder
Lukas Eder

Reputation: 220752

Is there any way to make hashCode() faster? Of course I understand that this will probably result in more collisions, but I am OK with this trade off.

The best answer for this particular question is:

public int hashCode() {
     return 0;
}

It is correct for any Object, it is as fast as it gets, and it will provide you with tons of collisions, which you are OK with.

Upvotes: 1

Related Questions