c++ - 如何最好地在 C++ 中为哈希表创建链式方法？

Question

我正在尝试使用链式方法实现哈希表，但我面临着一个选择。它要么是动态指针数组，要么是每个单元格中带有链表的数组，作为 LinkedList 类的对象。

这就是第一个有条件的方法的样子

template <typename T, typename V>
class Node {
public:
    T key;
    V value;
    Node* next;
    Node(T key, V value) {
        this->key = key;
        this->value = value;
        this->next = nullptr;
    }
};

template <typename T, typename V>
class HashTable {
private:
    int size;
    int count;
    Node<T, V>** table;
    //...
public: //...
};

我应该使用它，还是创建链接列表作为对象并将它们添加到表格单元格中？如何让内存更安全？

Answer 1

Should I use it, or create linked lists as objects and add them to the table cells already? How will it be safer for memory?

后者，即您应该创建一个链表类并拥有一个链表对象的 vector (或其本地版本)。原因是，通过创建类来封装链表和 vector 的功能，您就拥有了可以独立测试的干净抽象，并且您的哈希表实现可以基于它们的 API 处于更高的级别，而不是参与它们的实现。

如果您的最终目标是了解哈希表，您可以首先使用 std::vector<std::list<std::pair<Key, Value>>> 来实现它们。 - 首先让它工作，然后 - 如果你有时间 - 替换 std::vector和std::list使用您自己的版本，坚持相同的 API。

我不确定你所说的“内存更安全”是什么意思，但清晰、结构化、更可测试的代码往往可以避免损坏内存或从非预期位置读取的编程错误。

相比之下，您的 Node类只是准备插入链表的单个链接，而不是管理像 push_back 这样的整体链表操作的正确位置。或push_front 。让哈希表具有与链表类型类似的功能是混合职责，这是糟糕的软件设计。