Мне нужно создать класс в 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;
}
}