import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
public class ZeichenkettenHashfunktion {

    public ZeichenkettenHashfunktion() {
    }
    /**
     * Berechnet den Hashwert fuer einen String mit der Polynomiellen Hashfunktion
     * @param eingabe String, dessen Hashwert berechnet werden soll.
     * @param a Parameter zur Hashwertberechnung
     * @return Hashwert des Strings.
     */
    public int berechneHashwert(String eingabe, int a) {
        if(a >17020) {
            throw new IllegalArgumentException("a darf maximal |T|-1 sein");
        }
        if(eingabe == null) {
            throw new IllegalArgumentException("eingabe darf nicht null sein");
        }
        char[] eingabeChar = new char[eingabe.length()];

        for(int i = 0; i<eingabe.length();i++) {
            eingabeChar[i] = eingabe.charAt(i);
        }
        int hashwert = eingabeChar[eingabeChar.length - 1];
        for (int i = eingabeChar.length - 2; i >= 0; i--){

            hashwert = (((hashwert %17021) * (a %17021)%17021) + (eingabeChar[i] % 17021))%17021;
        }




        return hashwert;
    }
    /**
     *
     * @param a Parameter fuer die Hashfunktion.
     * @throws FileNotFoundException Falls words.txt nicht gefunden wird.
     */
    protected void berechneKollisionen(int a) throws FileNotFoundException {
        Scanner s = new Scanner(new File("words.txt"));
        int kollisionen = 0;
        boolean[] table = new boolean[17021];
        int eintraege = 0;

        //Scanner durchlaufen lasse, falls Array an der Stelle des Hashs leer ist, einfügen.
        //Falls vorhanden, Kollison++
        while(s.hasNext()) {
            String next = s.next();
            eintraege++;

            int hash = this.berechneHashwert(next, a);
            //  System.out.println("next: " + next + " Hash: " + hash);
            if(table[hash] == false) {
                table[hash] = true;
            } else {
                kollisionen++;
            }
        }

        System.out.println("Es gibt " + kollisionen + " Kollisionen für "
                + "a = "+a+ " und " + eintraege + " Einträge in words.txt");
        s.close();

    }



}