This class will represent a random hash function that can be used in a hash tabl

Question

This class will represent a random hash function that can be used in a hash table. This class will have following instance variables: a, b, and p and should have following constructors and public methods. HashFunction(int range). Picks the first (positive) prime integer whose value is at least range, and sets the value of p to that prime integer. Then picks two random integers x and y from {0, 1, , p - 1} and sets a as x and b as y. hash (int x) Returns the value of the hash function on x; i.e, returns (ax + b)%p. Accessor methods named get A, getB, getP that respectively return a, b and p. Modifier methods named setA(int x), setB(int y) that change the value of a (resp. b) to x%p (resp. y%p). Modifier method named setP(int x). This method will pick the first (positive) prime whose value is at least x and sets the value of p to that integer.

Explanation / Answer

Hi buddy, please find the below java program.

import java.util.*;
import java.lang.*;
import java.io.*;

class HashFunction{
    private int a,b,p;
  
    //This method calculates the prime number greater than or equal to x
    public static int nextPrime(int x){
        int ans = x;
        for(int i=x;;i++){
            int t = i;
            if(t%2==0){
                continue;
            }
            int e = (int)Math.sqrt(x);
            boolean prime = true;
            for(int j=3;j<=e;j+=2){
                if(t%j==0){
                    prime = false;
                    break;
                }
            }
            if(prime){
                ans = i;
                break;
            }
        }
        return ans;
    }
  
    //This is the constructor
    public HashFunction(int range){
        this.p = nextPrime(range);
        Random r = new Random();
        int x = r.nextInt(this.p);
        int y = r.nextInt(this.p);
        this.a = x;
        this.b = y;
    }
  
    //This method calculates the hash function
    public int hash(int x){
        return (a*x+b)%p;
    }
  
  
    //Getter methods
    public int getA(){
        return a;
    }
    public int getB(){
        return b;
    }
    public int getP(){
        return p;
    }
    //Setter methods
    public void setA(int x){
        this.a = x%p;
    }
    public void setB(int y){
        this.b = y%p;
    }
    public void setP(int x){
        this.p = nextPrime(x);
    }
}
class Main
{
   public static void main (String[] args) throws java.lang.Exception
   {
       HashFunction h = new HashFunction(14);
       System.out.println("A is : "+h.getA());
       System.out.println("B is : "+h.getB());
       System.out.println("P is : "+h.getP());
       int x = 5;
       System.out.println("HashValue of "+x+" is "+h.hash(x));
   }
}

OUTPUT : A is : 1
B is : 4
P is : 17
HashValue of 5 is 9

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---