1

我正在为java中的哈希表编写一个类...请确保我到目前为止做得正确。

我需要在其中存储 StudentRecord 对象....我正在根据 long 类型的学生 ID 计算哈希值...

package proj3;

import java.util.LinkedList;

public class HashTable {

    LinkedList<StudentRecord> [] buckets;
    int size;

    public HashTable(){
            size = 10;
            initialize();       
    }

    public HashTable(int initialSize){
        size = initialSize;
        initialize();
    }

    private void initialize(){
        for(int i=0; i<size; i++){
            buckets[i] = new LinkedList<StudentRecord>();
        }
    }
    /** for testing only
    private int calculateHashString(String s){
        int hash = 0;
        for(int i=0; i<s.length(); i++){
            hash += s.charAt(i);
        }
        return hash % size;
    }
    **/

    private int calculateHash(long l){
        return (int) (l % size);
    }


    public boolean contains(StudentRecord sr){
        int hash = calculateHash(sr.studentID);
        LinkedList<StudentRecord> l = buckets[hash];
        if(l.contains(sr)){
            return true;
        }
        return false;
    }

    public void put(StudentRecord sr){
        int hash = calculateHash(sr.studentID);
        LinkedList<StudentRecord> l = buckets[hash];
        if(!l.contains(sr)){
            buckets[hash].add(sr);
        }
    }

}
4

5 回答 5

8

我认为您可能想要编写单元测试来验证其实际功能，而与您的 f(r)iendly SO 专家是否健全检查无关。

除了简单的测试用例之外，一件好事是将实现的功能与标准 JDK HashMap 进行比较；生成随机键和/或值，插入、删除并检查两个实现之间的状态是否相同（在它们应该相同的程度上）。

于 2009-05-02T03:26:34.210 回答
3

buckets似乎永远不会被初始化。当你尝试这样做时，编译器应该给你一个警告。坚持集合优先于数组（原语除外）。

通过调用另一个构造函数 ( ) 可以更简单地实现您的无参数构造函数this(10。

出于多个原因，(int) (l % size)即使带有正数，表达式也可能返回负数。size

编码

public boolean contains(StudentRecord sr){
    ...
    if(l.contains(sr)){
            return true;
    }
    return false;
}

可以更清楚地写成

public boolean contains(Student student) {
    ...
    return list.contains(student);
}
于 2009-05-02T09:28:08.227 回答
2

看起来不错。

于 2009-05-02T03:23:25.497 回答
0

汤姆是对的，您需要将存储桶初始化为新的 LinkedList [大小]。

我认为您希望将大小设为最终值，并从更大的值开始，例如 256。如果您在将项目添加到表后调整大小，则需要将它们全部移动到新的存储桶中（来自更改后的哈希算法） .

另一方面，10 有利于测试 - 同一个桶上有很多碰撞！

为了节省内存，您不必在开始时初始化所有这些新的 LinkedList()，您可以将它们保留为空。您可以等待创建每个列表对象，直到新项目实际命中空存储桶。当然，这将意味着需要额外的代码，以检查您尝试读取的存储桶是否为空，如果是，则假设它是一个空列表。

于 2009-05-02T09:30:35.363 回答
0

您也必须重写 equals 和 hashCode 方法。

于 2009-05-22T16:25:31.113 回答