C++【哈希表的完善及封装】

**哈希表的完善及封装**

哈希表（Hash Table）是一种常见的数据结构，它通过将键值对映射到一个固定大小的数组中来实现快速查找、插入和删除操作。然而，哈希表也存在一些问题，如冲突、散列函数选择等。在本文中，我们将讨论如何完善哈希表，并且封装它以使其更易于使用。

###1. 哈希表的基本实现首先，让我们来看一下一个简单的哈希表实现：

cppclass HashTable {
private:
 int size; // 哈希表大小 struct Node { // 节点结构 int key;
 int value;
 Node* next; // 下一个节点指针 };
 Node** table; // 哈希表数组public:
 HashTable(int size) : size(size), table(new Node*[size]) {
 for (int i =0; i < size; ++i) {
 table[i] = nullptr;
 }
 }

 ~HashTable() {
 for (int i =0; i < size; ++i) {
 delete[] table[i];
 }
 delete[] table;
 }

 int hash(int key) { // 散列函数 return key % size;
 }

 void insert(int key, int value) {
 int index = hash(key);
 if (table[index] == nullptr) {
 table[index] = new Node{key, value};
 } else {
 Node* node = table[index];
 while (node->next != nullptr && node->key != key) {
 node = node->next;
 }
 if (node->key == key) {
 node->value = value;
 } else {
 node->next = new Node{key, value};
 }
 }
 }

 int get(int key) {
 int index = hash(key);
 Node* node = table[index];
 while (node != nullptr && node->key != key) {
 node = node->next;
 }
 return node == nullptr ? -1 : node->value;
 }

 void remove(int key) {
 int index = hash(key);
 Node* node = table[index];
 if (node != nullptr && node->key == key) {
 delete[] table[index];
 table[index] = nullptr;
 return;
 }
 while (node->next != nullptr && node->next->key != key) {
 node = node->next;
 }
 if (node->next != nullptr && node->next->key == key) {
 Node* nextNode = node->next;
 delete[] table[index];
 table[index] = nextNode;
 return;
 }
 }
};

cppclass HashTable {
private:
 int size; // 哈希表大小 struct Node { // 节点结构 int key;
 int value;
 Node* next; // 下一个节点指针 };
 Node** table; // 哈希表数组public:
 HashTable(int size) : size(size), table(new Node*[size]) {
 for (int i =0; i < size; ++i) {
 table[i] = nullptr;
 }
 }

 ~HashTable() {
 for (int i =0; i < size; ++i) {
 delete[] table[i];
 }
 delete[] table;
 }

 int hash(int key) { // 散列函数 return key % size;
 }

 void insert(int key, int value) {
 int index = hash(key);
 if (table[index] == nullptr) {
 table[index] = new Node{key, value};
 } else {
 Node* node = table[index];
 while (node->next != nullptr && node->key != key) {
 node = node->next;
 }
 if (node->key == key) {
 node->value = value;
 } else {
 node->next = new Node{key, value};
 }
 }
 }

 int get(int key) {
 int index = hash(key);
 Node* node = table[index];
 while (node != nullptr && node->key != key) {
 node = node->next;
 }
 return node == nullptr ? -1 : node->value;
 }

 void remove(int key) {
 int index = hash(key);
 Node* node = table[index];
 if (node != nullptr && node->key == key) {
 delete[] table[index];
 table[index] = nullptr;
 return;
 }
 while (node->next != nullptr && node->next->key != key) {
 node = node->next;
 }
 if (node->next != nullptr && node->next->key == key) {
 Node* nextNode = node->next;
 delete[] table[index];
 table[index] = nextNode;
 return;
 }
 }

 void resize(int newSize) { // 动态调整哈希表大小 int oldSize = size;
 size = newSize;
 Node** newTable = new Node*[size];
 for (int i =0; i < size; ++i) {
 newTable[i] = nullptr;
 }
 for (int i =0; i < oldSize; ++i) {
 Node* node = table[i];
 while (node != nullptr) {
 int newIndex = hash(node->key);
 if (newTable[newIndex] == nullptr) {
 newTable[newIndex] = node;
 } else {
 Node* newNode = newTable[newIndex];
 while (newNode->next != nullptr && newNode->key != node->key) {
 newNode = newNode->next;
 }
 if (newNode->key == node->key) {
 newNode->value = node->value;
 } else {
 newNode->next = node;
 }
 }
 Node* nextNode = node->next;
 delete[] table[i];
 node->next = nullptr;
 node = nextNode;
 }
 }
 delete[] table;
 table = newTable;
 }

 void openAddressing(int key, int value) { // 开放寻址 int index = hash(key);
 while (table[index] != nullptr && table[index]->key == key) {
 Node* node = table[index];
 table[index] = node->next;
 delete[] node;
 index = (index +1) % size;
 }
 if (table[index] == nullptr) {
 table[index] = new Node{key, value};
 } else {
 Node* node = table[index];
 while (node->next != nullptr && node->key != key) {
 node = node->next;
 }
 if (node->key == key) {
 node->value = value;
 } else {
 node->next = new Node{key, value};
 }
 }
 }

 void linkedHashing(int key, int value) { // 链式散列 int index = hash(key);
 if (table[index] == nullptr) {
 table[index] = new Node{key, value};
 } else {
 Node* node = table[index];
 while (node->next != nullptr && node->key != key) {
 node = node->next;
 }
 if (node->key == key) {
 node->value = value;
 } else {
 node->next = new Node{key, value};
 }
 }
 }
};

cppclass HashTableWrapper {
private:
 HashTable* table; // 哈希表实例public:
 HashTableWrapper(int size) : table(new HashTable(size)) {}

 ~HashTableWrapper() { delete table; }

 int get(int key) { return table->get(key); }

 void insert(int key, int value) { table->insert(key, value); }

 void remove(int key) { table->remove(key); }

 void resize(int newSize) { table->resize(newSize); }

 void openAddressing(int key, int value) { table->openAddressing(key, value); }

 void linkedHashing(int key, int value) { table->linkedHashing(key, value); }
};