英文:
How best to make a chain method for a hash table in c++?
问题
我正在尝试使用链式方法实现哈希表，我面临一个选择。要么它将是一个指针的动态数组，要么是一个数组，每个单元格中都有一个链表，作为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: //...
};
我应该使用它，还是创建链表作为对象并将它们添加到表格单元格中？从内存安全性角度来看，哪种方式更安全？
英文:
I am trying to implement a hash table using the chain method and I am faced with a choice. Either it will be a dynamic array of pointers, or an array with a linked list in each cell, as an object of the LinkedList class.
This is how the first method looks conditionally
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: //...
};
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?
答案1
得分: 2
> 我们应该使用它，还是创建链表作为对象并将它们添加到表格单元中？这样对内存会更安全吗？
后者，也就是说你应该创建一个链表类并拥有一个向量（或你自己实现的版本）的链表对象。原因是通过创建类来封装链表和向量的功能，你可以获得干净的抽象，可以独立进行测试，你的哈希表实现可以在更高的层次上基于它们的 API 进行，而不必涉及它们的具体实现。
如果你的最终目标是学习哈希表，你可以首先使用 std::vector<std::list<std::pair<Key, Value>>> 来实现它们 - 先让它工作，然后 - 如果你有时间的话 - 用你自己的版本替换 std::vector 和 std::list，但保持相同的 API。
我不确定你所说的“对内存更安全”是什么意思，但清晰、结构化、更具可测试性的代码通常可以避免程序错误，这些错误可能会破坏内存或从意外的位置读取数据。
相比之下，你的 Node 类只是一个准备插入到链表中的单个链接，而不是管理整个链表操作（如 push_back 或 push_front）的正确位置。让哈希表拥有像这样针对链表类型的函数是混合责任的做法，这是糟糕的软件设计。
英文:
> 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?
The latter, i.e. you should create a linked list class and have a vector (or your home-grown version thereof) of linked list objects. The reason is that by creating classes to encapsulate the functionality of linked lists and vectors, you then have clean abstractions that can be tested independently, and your hash table implementation can be at a higher level based on their APIs, rather than being involved with their implementations.
If you ultimate goal is to learn about hash tables, you could start by implementing them using a std::vector<std::list<std::pair<Key, Value>>> - get that working first, then - if you have time - replace std::vector and std::list with your own versions, sticking to the same API.
I'm not sure what you mean by "safer for memory", but clear, structured, more testable code tends to avoid programming errors that corrupt memory or read from unintended places.
By way of contrast, your Node class is only a single link ready to be inserted into a linked list, and not the right place to manage overall linked list operations like push_back or push_front. Having the hash table have functions like that for the linked list type is mixing responsibilities, which is bad software design.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论