c++语言怎么实现hash表

前言

哈希表（hash table）是一种常用的数据结构，用于快速存储和查找数据。它通过将键映射到数组中的一个位置来实现高效的数据访问。C++提供了不同的哈希表实现，我们将使用开放地址法来展示一种常见的哈希表实现。

实现哈希表

我们将使用C++来实现一个简单的哈希表。首先，我们需要定义一个合适的数据结构来表示哈希表中的节点。每个节点应该包含键和值，以及一个指向下一个节点的指针。以下是一个示例节点类的定义：

  class Node {
  public:
      int key;
      int value;
      Node* next;
      
      Node(int k, int v) : key(k), value(v), next(nullptr) {}
  };
  

接下来，我们需要定义一个哈希函数来将键映射到数组索引。一个简单的哈希函数是将键的ASCII码相加，并对数组长度取余。以下是一个示例的哈希函数：

  int hash(int key, int arraySize) {
      return key % arraySize;
  }
  

现在我们可以定义哈希表类，并在其中实现插入、查找和删除操作。哈希表类应该包含一个数组来存储节点，并设定合适的大小。以下是一个示例的哈希表类的定义：

  class HashTable {
  private:
      int size;
      Node** array;
      
  public:
      HashTable(int tableSize) : size(tableSize) {
          array = new Node*[size];
          for (int i = 0; i < size; i++) {
              array[i] = nullptr;
          }
      }
      
      // 插入操作
      void insert(int key, int value) {
          int index = hash(key, size);
          Node* newNode = new Node(key, value);
          
          if (array[index] == nullptr) {
              array[index] = newNode;
          } else {
              Node* current = array[index];
              while (current->next != nullptr) {
                  current = current->next;
              }
              current->next = newNode;
          }
      }
      
      // 查找操作
      int find(int key) {
          int index = hash(key, size);
          Node* current = array[index];
          
          while (current != nullptr) {
              if (current->key == key) {
                  return current->value;
              }
              current = current->next;
          }
          
          return -1; // 未找到键对应的值
      }
      
      // 删除操作
      void remove(int key) {
          int index = hash(key, size);
          Node* current = array[index];
          Node* previous = nullptr;
          
          while (current != nullptr) {
              if (current->key == key) {
                  if (previous == nullptr) {
                      array[index] = current->next;
                  } else {
                      previous->next = current->next;
                  }
                  delete current;
                  return;
              }
              previous = current;
              current = current->next;
          }
      }
  };
  

总结

在本文中，我们使用C++实现了一个基于开放地址法的哈希表。我们定义了节点类来表示哈希表中的每个节点，并使用简单的哈希函数将键映射到数组索引。通过实现插入、查找和删除操作，我们展示了如何使用哈希表来存储和查找数据。