Java - хэш-функция - PullRequest
       41

Java - хэш-функция

0 голосов
/ 22 мая 2018

Мне нужно создать класс в Java, чтобы вычислить коллизию хеш-функции для таблицы с 17021 записями. список слов

это хеш-функция

"a" равно 33, 37, 39 или 41.

x_0 - первый символ строки, а x_k-1 - последний символ.

Это моя программа

К сожалению, я всегда получаю число, которое большечем 17021 как результат.Но это невозможно.Я не знаю, почему это не работает.

Я немного отчаялся, потому что долгое время пытался найти ошибку, но не могу ее найти.

Было бы здорово, если бы кто-нибудь из вас, ребята, знал, в чем моя ошибкаЯ изучаю Java уже 5 месяцев, чтобы вы знали, насколько большим может быть мой уровень квалификации.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

/**
 * This class calculates the hash value of strings.
 * 
 * @author Chris
 *
 */
public class ZeichenkettenHashfunktion {

    /**
     * Counts how often the same hash value is calculated
     * 
     * @return
     * @throws IOException
     */
    public int berechneKollisionen() throws IOException {

        // Implement the data
        FileReader reader = new FileReader("F:\\eclipse\\eclipse-workspace\\Info 2 Aufgabe 19\\words.txt");
        // Create a Buffer
        BufferedReader inBuffer = new BufferedReader(reader);

        // Set Variables
        int hashwert = 0;
        int kollisionen = 0;
        int i = 0;
        int[] hashwerte = new int[17021];

        // fill in the field up to 17020
        while (i < 17021) {
            hashwerte[i] = i;

            i += 1;

        }

        // takes the first string of the list
        String line = inBuffer.readLine();

        // calculates his hash value
        hashwert = this.berechneHashwert(line, 33);

        // delete the number of the hash value
        hashwerte[hashwert] = 1000000;

        // Check, whether it works
        System.out.println(hashwerte[hashwert]);

        // go step by step over the array
        while (line != null) {
            line = inBuffer.readLine();

            // to exclude the last line
            if (line != null) {
                // calculate the hash value of the current line
                hashwert = this.berechneHashwert(line, 40);

                // if there is 1000000 on the place of the hash value, then raise the collision
                // counter by 1
                if (hashwerte[hashwert] == 1000000) {
                    kollisionen += 1;
                    System.out.println(" " + kollisionen);
                }

                // if there is the hash value on the place of the hash value, then replace it by
                // 1000000
                if (hashwerte[hashwert] == hashwert) {
                    hashwerte[hashwert] = 1000000;
                }
            }

        }

        inBuffer.close();
        reader.close();

        return kollisionen; // return collision counter

    }

    /**
     * Calculates the hash value of a string
     * 
     * @param eingabe
     * @param zahl
     * @return
     */
    public int berechneHashwert(String eingabe, int zahl) {

        // Set variables
        int laenge = eingabe.length();
        char[] zerteilung = new char[laenge];
        int hashwert = 0;
        int a = zahl;

        // breaks the string down into chars
        while (laenge != 0) {
            zerteilung[laenge - 1] = eingabe.charAt(laenge - 1);
            laenge -= 1;
        }
        // Set laenge back to the length
        laenge = eingabe.length();

        // calculates the hash value
        hashwert = this.berechneHashwertIntern(zerteilung, laenge, hashwert, a) % 17021;

        return hashwert;
    }

    /**
     * auxiliary function to calculate the hash value
     * 
     * @param zerteilung
     * @param laenge
     * @param hashwert
     * @param a
     *            a is a number, which is called as good for hash functions by
     *            scientist
     * @return
     */
    private int berechneHashwertIntern(char[] zerteilung, int laenge, int hashwert, int a) {

        // calculate the last part of the formula
        hashwert = (a * zerteilung[laenge - 1]) % 17021;
        laenge -= 2;

        // calculate the formula from the end to the beginning
        while (laenge != 0) {
            hashwert = (a * (zerteilung[laenge] + hashwert)) % 17021;

            laenge -= 1;

        }

        return hashwert;
    }

}

1 Ответ

0 голосов
/ 22 мая 2018

Я не совсем понимаю вашу проблему.У вас есть входной файл около 45 000 строк, который вы пытаетесь сопоставить с HashMap из 17021 записей.Таким образом, по определению, даже если вы вставили каждую запись, используя «предыдущую позицию + 1» (т. Е. Без хеширования, как если бы это был список), у вас будет около 28000 коллизий.Вы уверены, что размер вашей хеш-таблицы имеет (любой) смысл, учитывая размер входных данных?Поскольку ваша функция исправлена, я на самом деле получаю 29778 столкновений.

...