Løsningsforslag 7, gruppe 4

package oppgavesett7;

import java.util.HashSet;
import java.util.Iterator;

public class Person2 {
    private String navn;

    public Person2(String navn) {
        this.navn = navn;
    }

    public String toString() {
        return "" + navn;
    }

    public boolean equals(Object obj) {
        Person2 p = (Person2)obj;
        return navn == p.navn;
    }

    // Overstyrer hashCode fra klassen Object:

    public int hashCode() {
        // tja hva skal man si var jo denne logaritmen beskrevet i boka
        return navn.toCharArray()[0]%32;
    }


    public static void main(String[] args) {
        
        Person2[] p = new Person2[8];
        p[0] = new Person2("Ann");
        p[1] = new Person2("Dough");
        p[2] = new Person2("Elizabeth");
        p[3] = new Person2("Hal");
        p[4] = new Person2("Mary");
        p[5] = new Person2("Tim");
        p[6] = new Person2("Walter");
        p[7] = new Person2("Young");

        HashSet<Person2> h = new HashSet<Person2>();
        for (int i = 0; i < p.length; i++) {
            h.add(p[i]);
        }

        Person2 test = new Person2("Andrew");

        // Andrew blir lagt inn i den lenkede lista
        h.add(test);

        if (h.contains(test))
            System.out.println("" + test + " finnes!");
        else
            System.out.println("" + test + " finnes ikke!");

        for (int i = 0; i < p.length; i++) {
            if (h.contains(p[i]))
                System.out.println("" + p[i] + " finnes!");
            else
                System.out.println("" + p[i] + " finnes ikke!");
        }
        
        System.out.print("\nHashtabellen inneholder : ");
        Iterator it = h.iterator();
        while (it.hasNext()) System.out.print(it.next()+" ");

    }
}

package oppgavesett7;

import java.util.Random;


/*
 *  Skriv et program som teller opp antall kollisjoner i en lang random sekvens
 *  av insettinger i hashtabeller med åpen adressering når lineær søk,
 *  kvadratisk søk og dobbel hashing benyttes.
 *  Kjør programmet med forskjellige verdier for tabellens lengde
 *  (primtall/ikke primtall). Gjør en oppsummering av resultatene
 *
 *  (Du trenger kun å beregne posisjonene til elementene i tabellene,
 *  oppgaven forutsetter altså ikke at du har implementert forskjellige
 *  varianter av hashtabellene).
 */
public class Collisions {
    static int antall_tall=10;
    static int max_tall=100;
    static int tabell_lengde=81;
    
    public Collisions() {
    }
    
    public static void openLinear(int[] tallrekke){
        int[] hashTabel = new int[tabell_lengde];
        int total_collision = 0;
        
        for (int i=0;i<antall_tall;i++){
            hashTabel[tallrekke[i]%tabell_lengde]++;
        }
        
        System.out.println("\n### Open linear ###\nAntall kollisjoner pr plass i hashtabellen");

        for (int i=0;i<tabell_lengde;i++){
            System.out.print(i+"-"+hashTabel[i]+" ");
            if (hashTabel[i]>1) total_collision += hashTabel[i]-1;
        }
        
        System.out.println("\nDet var totalt "+total_collision+" kollisjoner");
    }
    
    public static void openQuadratic(int[] tallrekke){
        int[] hashTabel = new int[tabell_lengde];
        int total_collision = 0;
        
        for (int h=0;h<tallrekke.length;h++){
            int i = 1;
            while(i<tabell_lengde)
            {
                if (hashTabel[i]<1) {
                    hashTabel[i]++;System.out.print(i+" ");
                    i=tabell_lengde;
                }
                
                double p = (int)Math.pow((double)i,2.0);
                i = (int)p+i;
                //
                   
            }
        }
             
        System.out.println("\n### Open Quadratic ###\nAntall kollisjoner pr plass i hashtabellen");

        for (int j=0;j<tabell_lengde;j++){
            System.out.print(j+"-"+hashTabel[j]+" ");
            if (hashTabel[j]>1) total_collision += hashTabel[j]-1;
        }
        
        System.out.println("\nDet var totalt "+total_collision+" kollisjoner");
    }
    
    public void openDouble(int[] tallrekke){
    
    }

    public static void main(String[] args) {
        Collisions collisions = new Collisions();
        
        Random generator = new Random();
        int[] tallrekke = new int[antall_tall];
        
        // Lager en tilfeldig tallrekke
        for (int i=0;i<antall_tall;i++){
            tallrekke[i] = generator.nextInt(max_tall);
            System.out.print(tallrekke[i]+" ");
        }
        
        System.out.println();
        openLinear(tallrekke);
        openQuadratic(tallrekke);
        
    }
    
}