Geek asks and answers

How to implement the hash function `h (k) = (A · k mod 2 ^ w) >> (wr)` in Java

IMPORTANT NOTICE:

This is not a debatable topic for people who can give me their opinion on hashing. I just need to know how to make this function work in java - an example would be better.

PROBLEM:

Trying to hone my understanding of hash functions for an awaiting interview, I watch two free lectures by MIT computer science professors (http://videolectures.net/mit6046jf05_leiserson_lec08/). Therefore, after the lecture, I try to implement the following hash function in java.

h(k) = (A·k mod 2^w) >> (w – r)
WHERE
r: m, the size of the array, is a power of 2 such that m=2^r
w: the computer has w-bit words, such as 32-bit or 64-bit computer
k: the value I am to find a key for
A: a random odd number (prime would be great) between 2^(w-1) and 2^w

I thought this would be easy to implement in java. But when I do 2 ^ w, where w = 32, I get inaccurate results in Java. In real life 2^32 = 4294967296, but not in java, which truncates the result to 2^31 - 1or 2147483647.

- , , Java?

EDIT:

, 32. , 64-? w = 32, Java?

+3
4

, Java .

A·k mod 2^w

Java , , mod 2^w ( ). , , , .

(w - r) -r Java (w )

private static final int K_PRIME = (int) 2999999929L;

public static int hash(int a, int r) {
   // return (a * K_PRIME % (2^32)) >>> (32 - r);
   return (a * K_PRIME) >>> -r;
}

64-

private static final long K_PRIME = new BigInteger("9876534021204356789").longValue();

public static long hash(long a, int r) {
    // return (a * K_PRIME % (2^64)) >>> (64 - r);
    return (a * K_PRIME) >>> -r;
}

, , BigInteger .;)

public static final BigInteger BI_K_PRIME = new BigInteger("9876534021204356789");
private static long K_PRIME = BI_K_PRIME.longValue();

public static long hash(long a, int r) {
    // return (a * K_PRIME % (2^64)) >>> (64 - r);
    return (a * K_PRIME) >>> -r;
}

public static long biHash(long a, int r) {
    return BigInteger.valueOf(a).multiply(BI_K_PRIME).mod(BigInteger.valueOf(2).pow(64)).shiftRight(64 - r).longValue();
}

public static void main(String... args) {
    Random rand = new Random();
    for (int i = 0; i < 10000; i++) {
        long a = rand.nextLong();
        for (int r = 1; r < 64; r++) {
            long h1 = hash(a, r);
            long h2 = biHash(a, r);
            if (h1 != h2)
                throw new AssertionError("Expected " + h2 + " but got " + h1);
        }
    }

    int runs = 1000000;
    long start1 = System.nanoTime();
    for (int i = 0; i < runs; i++)
        hash(i, i & 63);
    long time1 = System.nanoTime() - start1;

    long start2 = System.nanoTime();
    for (int i = 0; i < runs; i++)
        biHash(i, i & 63);
    long time2 = System.nanoTime() - start2;
    System.out.printf("hash with long took an average of %,d ns, " +
            "hash with BigInteger took an average of %,d ns%n",
            time1 / runs, time2 / runs);
}


hash with long took an average of 3 ns, \
    hash with BigInteger took an average of 905 ns
+4

int, long , , 2 ^ (w-1). BigInteger.

+2

, number % 2^32: 2 ^ 32. 0 2 ^ 32, , 2 ^ 32.

8 32 :

  1000 1000 % 1 0000 0000 = 1000 1000
1 1000 1000 % 1 0000 0000 = 1000 1000

, . , , ++, , unsigned int. 1 , .

java . A * k, , . , , , .

, - . , , .

+1

Java int -2147,483,648 2,147,483,647

.

long int.

0

More articles:


All Articles