HW：创建我自己的哈希表 - 不确定如何在其中使用链表

Question

我有一项作业正在处理，我们正在制作我们自己的哈希表。今天去了一个AI，他说我的代码是"on the right track but I should use linked lists"，我有点不明白他的意思。

请提示我遗漏了什么。

class HashSeparateChaining extends HashTable {

    int size = 0;
    HashFunction hf;
    List<Integer> arrayList = new ArrayList<>();

    public HashSeparateChaining(int size, HashFunction hf) {

        size = this.size;
        hf = this.hf;

        for(int i = 0; i < size; i++) {
            arrayList.add(null);
        }

    }

    @Override
    void insert(int key) throws TableFullE {
        arrayList.set(key, key);

    }

    @Override
    void delete(int key) {
        arrayList.set(key, null);
    }

    @Override
    boolean search(int key) {
        for(int z = 0; z < arrayList.size(); z++)
            if(arrayList.get(z) == key)
                return true;

        return false;
    }

}

那么 AI 是否意味着我应该使用这样的东西？

List<LinkedList<Integer, String>> list = new LinkedList<>();

Answer 1

我不确定 SO 是一个家庭作业帮助网站，但可以快速搜索 google https://www.geeksforgeeks.org/hashing-set-2-separate-chaining/ 这应该会给你一个想法。

您的基础实现可能是 ArrayList 个 List。

插入：将 HashFunction 应用到键上可以为您提供 ArrayList 中的索引。然后将键添加到存储在该索引处的列表的后面。（需要阐明 table 已满意味着什么，以便您知道何时抛出 TableFullE 异常）。

删除：与插入一样，将您的 HashFunction 应用于键以找出我们搜索的列表。不妨使用 List 的方法来删除项目。

搜索：类似于删除，除了使用 List 的 contains() 来回答搜索查询

很多可能的优化，但首先尝试让它工作。

HW：创建我自己的哈希表 - 不确定如何在其中使用链表

HW: Creating my own hashtable - Unsure of how to use a linkedlist in it

java

hashtable