Oppgavesett 7

Fra Hiofwiki

Oppgavesett 7

Her er en løsning på 7.3. Litt skeptisk til kvadratisk søk men....

import java.util.Random;
import java.util.*;

public class KollisjonTeller {

    
    private static int ant;
    private static int tablengde;
    
    static boolean[] KollisjonTab;
    static int koll = 0;
        
    
    public static int hash1(int n){        
        return n%tablengde;
    }
    
    public static int hash2(int n){        
       
        int res = (int) ((n % tablengde) * 1.5);
        
        return res%2; 
    }
   
    public static void setFalse(boolean[] tab){
        
        for(int i = 0; i < tab.length; i++){
            
            tab[i]= false;
        }
        
    }
    
    
    public static int LagRandom(int n){
        
        Random generator = new Random();
        int element = (generator.nextInt(n))+1; 
    
        return element;
    }
    
    public static int getLinear(int tall){
        
        int i = hash1(tall);
        while(KollisjonTab[i])
        {
            koll++;
            i++;
            
            if(i == tablengde)
                i=0;               
        }
             
        KollisjonTab[i] = true;
        
        return i;
    }

	public static int pow(int num, int pow)
	{
		for(int i=0; i<pow; i++)
			num *= num;
		return num;
	}
    
    public static int getKvadratisk(int tall){
       
        int hash = hash1(tall);
		int i = hash;
		int help = 1;
        while(KollisjonTab[i] && help < tablengde)
        {
            koll++;
			help++;
            i = (hash + pow(-1, (help - 1)) * pow((help+1)/2, 2)) % tablengde;
			if(i < 0)
				i += tablengde;

        }
             
        KollisjonTab[i] = true;
        
        return i;
    }
    
    public static int getDoubleHash(int tall){
        
       int hash = hash1(tall);
	   int i = hash;
	   int help = 0;
       while(KollisjonTab[i]){
           koll++;

           i = (hash + help++ + hash2(tall)) % tablengde;

       }
       
       KollisjonTab[i] = true;
       
       return i;
    }
    
    public static void main(String[] args) {
        
        ant = Integer.parseInt(args[0]);
        tablengde = Integer.parseInt(args[1]);
		KollisjonTab = new boolean[tablengde];
        
        ArrayList<Integer> random = new ArrayList<Integer>();
        for(int i=0; i<tablengde; i++)
            random.add(LagRandom(ant));
       
        
       int k =0;
       
       setFalse(KollisjonTab);
       koll = 0;

	   

	   // Test Linear
       for(int j=0; j<random.size(); j++){
           
           k = getLinear(random.get(j));
           
           System.out.print(k + ", " );
       } 
      
        System.out.println("\nAntall kollisjoner ved lineærsøk: " + koll);
        
        setFalse(KollisjonTab);
       	koll = 0;
        
        for(int j=0; j<random.size(); j++){
           
           k = getKvadratisk(random.get(j));
           
           System.out.print(k + ", " );
       } 
      
        System.out.println("\nAntall kollisjoner ved kvadratisk søk: " + koll);
       
       setFalse(KollisjonTab);
       koll = 0;
        
       for(int j=0; j<random.size(); j++){
           
           k = getDoubleHash(random.get(j));
           
           System.out.print(k + ", " );
       } 
      
        System.out.println("\nAntall kollisjoner ved DoubleHash: " + koll);
        
        
    }

}