java - Java - 哈希函数

问题描述

我必须在 java 中创建一个类来计算具有 17021 个条目的表的哈希函数的冲突。单词列表

这是哈希函数

“a”是 33、37、39 或 41。

x_0 是字符串的第一个字符，x_k-1 是最后一个字符。

这是我的程序

不幸的是，我总是得到一个大于 17021 的数字。但这是不可能的。我不知道为什么它不起作用。

我有点绝望，因为我已经尝试了很长时间来寻找失败，但我无法找到它。

如果你们中的一个知道我的错误是什么，那就太好了。我现在已经学习了 5 个月的 Java，所以你知道我的技能水平有多大。

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;
    }

}

标签： javaarrayshashhash-function

java - Java - 哈希函数

问题描述

解决方案

推荐阅读