CODEWITHSUNDEEP
javahashcomputer-scienceuniversal-hashing
Jan Lauber
Jan Lauber

Reputation: 11

Universal Hash Function Implementation for Strings in Java

I have some troubles understanding the implementation of a universal hash function in Java. The hash function (ax + b) mod p should be implemented in base of H_1. Also this implementation should work for strings.

I recently worked on this:

public class UniversalHashing {
    // the hash function is a linear function (h(x) = (ax + b) mod p)
    // where a and b are chosen randomly
    // p is a prime number

    private int a;
    private int b;
    private int p;

    public UniversalHashing(int a, int b, int p) {
        this.a = a;
        this.b = b;
        this.p = p;
    }

    public int hash(String string) {
        int hash = 0;
        for (int i = 0; i < string.length(); i++) {
            hash = (hash * a + string.charAt(i)) % p;
        }
        return (hash + b) % p;
    }

    public static void main(String[] args) {
        UniversalHashing h = new UniversalHashing(5, 3, 11);
        System.out.println(h.hash("hello"));
        System.out.println(h.hash("world"));
        System.out.println(h.hash("hello"));
        System.out.println(h.hash("world"));
    }
}

Is this implementation correct or am I on the completely wrong path to implement a universal hash function for String.

thanks for helping me out for this greez

Upvotes: 0

Views: 544

Answers (1)

Jan Lauber
Jan Lauber

Reputation: 11

Or something like this?

import java.math.BigInteger;

public class UniversalHashing {
    private final BigInteger a,b;
    private final long p = 1000000007;

    public UniversalHashing(long m) {
        a = BigInteger.valueOf((long) (Math.random() * p));
        b = BigInteger.valueOf((long) (Math.random() * (p - 1L)));
    }

    public int hashCode(String string) {
        BigInteger hash = BigInteger.valueOf(0);
        for (int i = 0; i < string.length(); i++) {
            hash = hash.add(BigInteger.valueOf(string.charAt(i)).multiply(a.pow(i)));
        }
        return (int) (hash.mod(BigInteger.valueOf(p)).add(b).mod(BigInteger.valueOf(p)).longValue());
    }

    public static void main(String[] args) {
        UniversalHashing uh = new UniversalHashing(1000000007);
        System.out.println(uh.hashCode("abc"));
        System.out.println(uh.hashCode("abcd"));
        System.out.println(uh.hashCode("abcde"));
    }
}

Upvotes: 0

Related Questions