如何使我的线性探测哈希表正确地增加探测次数?

huangapple go评论68阅读模式
英文:

how do i get my linear probing hash table to increment the number of probe properly?

问题

I've translated the non-code part of your message:

我被要求计算权重,以优化将特定姓名列表插入哈希表中的线性探测过程。当我尝试在 void 和 int 值之间使用 "+=" 时遇到问题。有人能告诉我我的代码哪里出错了,因为 hashTable.insert 方法是 void:

以下是 hashTable.insert 方法,该方法是 void:

我尝试了上面的代码,但它一直给我报错,说我在 "+=" 中使用了 void 和 int 类型。我还尝试过仅递增 probeCount 然后插入哈希表,但它给我错误的 leastNumProbes 和 numWeightCombinations 值。

以下是 mydata.txt 数据集,其中包含我要进行线性探测的用户名:

使用 Optimize.java 生成的结果是:
12 1953125

英文:

I'm meant to be computing weights that optimise the insertion of a specific list of names into a hash table using linear probing. I ran into a problem when trying to use "+=" with a void and int value. Can anyone help with letting me know where my code went wrong as the hashTable.insert method is a void :

public class Optimize {

    public static void main(String[] args) throws IOException {

        String fileName = "mydata.txt";
        String[] names = readCustomList(fileName);
        
        int numNames = names.length;
        int[] weights = new int[9];
        int numWeightCombinations = 0;
        int leastNumProbes = Integer.MAX_VALUE;

        for (int w0 = 0; w0 <= 4; w0++) {
            weights[0] = w0;

            for (int w1 = 0; w1 <= 4; w1++) {
                weights[1] = w1;

                for (int w2 = 0; w2 <= 4; w2++) {
                    weights[2] = w2;

                    for (int w3 = 0; w3 <= 4; w3++) {
                        weights[3] = w3;

                        for (int w4 = 0; w4 <= 4; w4++) {
                            weights[4] = w4;

                            for (int w5 = 0; w5 <= 4; w5++) {
                                weights[5] = w5;

                                for (int w6 = 0; w6 <= 4; w6++) {
                                    weights[6] = w6;

                                    for (int w7 = 0; w7 <= 4; w7++) {
                                        weights[7] = w7;

                                        for (int w8 = 0; w8 <= 4; w8++) {
                                            
                                            weights[8] = w8;
                                            LPHashTable hashTable = new LPHashTable(37);
                                            hashTable.setWeights(weights);
                                            int numProbes = 0;

                                            for (String name : names) {
                                                numProbes += hashTable.insert(name);
                                            }

                                            if (numProbes < leastNumProbes) {
                                                leastNumProbes = numProbes;
                                                numWeightCombinations = 1;
                                            } 
                                            
                                            else if (numProbes == leastNumProbes) {
                                                numWeightCombinations++;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        System.out.println(leastNumProbes + " " + numWeightCombinations);
    }



    /**
     * Reads usernames from data text file and inserts them into 
     * an ArrayList.
     */
    private static String[] readCustomList(String filename) throws IOException {

        BufferedReader reader = new BufferedReader(new FileReader(filename));
        String line;
        StringBuilder sb = new StringBuilder();

        while((line = reader.readLine()) != null) {

            sb.append(line);

        }

        reader.close();
        String[] names = sb.toString().split("\\s+");
        return names;

    }


}

And here is the hashTable.insert method which is a void :

   public void insert(String key) {
        int index = findIndex(key);
        if (index==-1) {
            // Table is full, time to rehash.
            this.rebuild();
        }

        if (table[index]==null) {
            table[index]= key;
            this.entries++;
        }
    }

I tried this code above but it kept giving me the error of using a void and int types for the "+=". I also tried just incrementing the probeCount and then inserting to the hash table but it gave me the wrong values for leastNumProbes and numWeightCombinations.

Here is the dataset of mydata.txt which is the usernames im meant to be linear probing :

dfferi001
abdibr008
esnchr001
cmpcla004
phlzwi002
gngjoa003
zndkho003
krnnen001
njkabo001
blmjoh007
brcros003
tgdmoe001
ndlzan021
dlkdim001
pthkis001
mtlmar020
mshrum006
ntlasa006
ndzmas002
rsbtsh001
chtkea005
rnbluk001
mdzwav001
ngqabo003
strrac002
cbxlis001
schpie019
chtsha051
ersand012
mgtlut001
mssoli002
mdxnde001
vlnsha004
krnern002
krrfar003
rppkei001

and using Optimize.java it produces :
12 1953125

答案1

得分: 1

运算符+=对于参数类型int、void在Optimize.main(Optimize.java:58)处未定义。

该错误是编译时错误。由于您未包含LPHashTable,我只能猜测。看起来您正在执行以下操作:

numProbes += hashTable.insert(name);

如果insert方法声明为public void insert(String name),它不返回任何内容(void返回声明),因此无法添加到numProbes。编译器知道这一点并发出警告。应该声明为public int insert(String name),以便返回一个int值。

另一个建议是,您不需要所有嵌套循环。您可以通过使用一个简单的方法从右到左“递增”数组,我将其设计得相当通用,以便您可以指定控制每个位置的最大值的限制数组。

int[] limits = {4, 4, 4, 4, 4, 4, 4, 4, 4};
int[] weights = new int[9];
for (int i = 0; i < 2000; i++) {
    System.out.println(Arrays.toString(weights));
    increment(weights, limits);
}

public static void increment(int[] weights, int[] limits) {
    for (int i = weights.length - 1; i >= 0; i--) {
        if (weights[i] < limits[i]) {
            weights[i]++;
            return;
        }
        weights[i] = 0;
    }
    return;
}

输出:

[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 0, 0, 0, 0, 4]
[0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 1, 2]
[0, 0, 0, 0, 0, 0, 0, 1, 3]
[0, 0, 0, 0, 0, 0, 0, 1, 4]
[0, 0, 0, 0, 0, 0, 0, 2, 0]
...
...
[0, 0, 0, 0, 3, 0, 4, 3, 3]
[0, 0, 0, 0, 3, 0, 4, 3, 4]
[0, 0, 0, 0, 3, 0, 4, 4, 0]
[0, 0, 0, 0, 3, 0, 4, 4, 1]
[0, 0, 0, 0, 3, 0, 4, 4, 2]
[0, 0, 0, 0, 3, 0, 4, 4, 3]
[0, 0, 0, 0, 3, 0, 4, 4, 4]
英文:

> The operator += is undefined for the argument type(s) int, void at Optimize.main(Optimize.java:58)" .

The error is a compile time error.
And since you didn't include the LPHashTable I can only guess. It appears you are doing the following:

numProbes += hashTable.insert(name);

If the insert method is declared as public void insert(String name) it isn't returning anything (void return declaration) so it can't add to numProbes. The compiler knows this and complains. It should be declared as public int insert(String name) so it returns an int value.

And here is another suggestion. You don't need all the nested loops. You can &quot;increment&quot; an array from right to left by using a simple method. I made it fairly general so you can specify an array of limits to control each location's maximum value.

int[] limits = {4,4,4,4,4,4,4,4,4};
int[] weights = new int[9];
for (int i = 0; i &lt; 2000; i++) {
    System.out.println(Arrays.toString(weights));
    increment(weights, limits);
} 
    
public static void increment(int[] weights, int[] limits) {
    for (int i = weights.length-1; i &gt;= 0; i--) {
        if (weights[i] &lt; limits[i]) {
            weights[i]++;
            return;
        }
        weights[i] = 0;
    }
    return;
}

prints

[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 0, 0, 0, 0, 4]
[0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 1, 2]
[0, 0, 0, 0, 0, 0, 0, 1, 3]
[0, 0, 0, 0, 0, 0, 0, 1, 4]
[0, 0, 0, 0, 0, 0, 0, 2, 0]
...
...
[0, 0, 0, 0, 3, 0, 4, 3, 3]
[0, 0, 0, 0, 3, 0, 4, 3, 4]
[0, 0, 0, 0, 3, 0, 4, 4, 0]
[0, 0, 0, 0, 3, 0, 4, 4, 1]
[0, 0, 0, 0, 3, 0, 4, 4, 2]
[0, 0, 0, 0, 3, 0, 4, 4, 3]
[0, 0, 0, 0, 3, 0, 4, 4, 4]


</details>



huangapple
  • 本文由 发表于 2023年5月14日 00:47:47
  • 转载请务必保留本文链接:https://go.coder-hub.com/76243895.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定