C++数据结构哈希表详解

哈希表（Hash Table）是一种非常重要的数据结构，用于实现字典等各种应用。哈希表将关键字映射到一个固定大小的数据集合中，以支持常数时间复杂度的插入、查找和删除操作。哈希表的核心思想是将关键字通过哈希函数（Hash Function）映射到数据集合中的一个索引位置，哈希函数需要满足良好的散列性质，使得关键字能够均匀地散布在数据集合中。

哈希表的数据结构

哈希表的数据结构包含一个数组和一个哈希函数。数组用于存储数据，哈希函数用于将关键字映射到数组的索引位置。数组大小可以根据需要进行动态调整，以提高哈希表的空间利用率。

template <typename KeyType, typename ValueType>
class HashTable {
public:
  // 哈希表的构造函数
  HashTable();

  // 哈希表的析构函数
  ~HashTable();

  // 插入一个键值对
  void insert(const KeyType& key, const ValueType& value);

  // 查找一个键值对
  const ValueType* find(const KeyType& key) const;

  // 删除一个键值对
  void remove(const KeyType& key);
private:
  // 哈希表的节点结构体
  struct Node {
    KeyType key;         // 键
    ValueType value;     // 值
    Node* next;          // 指向下一个节点的指针
    Node(const KeyType& k, const ValueType& v)
        : key(k), value(v), next(nullptr) {}
  };

  std::vector<Node*> table_;          // 存储数据的数组
  int size_;                          // 哈希表中键值对的个数
  int capacity_;                      // 哈希表的容量
  const int kDefaultCapacity = 10;    // 默认的哈希表容量

  // 哈希函数，将关键字映射到一个索引位置
  int hash(const KeyType& key) const;
};

哈希函数的设计

一个好的哈希函数需要满足以下几个条件：

1. 一致性：对于相同的输入，哈希函数总是生成相同的输出。

2. 散列性：哈希函数需要将输入均匀地散布到输出范围内，以减少哈希冲突（Hash Collision）的发生。

3. 易计算：哈希函数应该快速计算，以确保查找、插入和删除操作的时间复杂度为常数级别。

常用的哈希函数包括取模法、乘法哈希等，其中取模法是最简单、最常用的哈希函数之一。具体实现可以参考如下代码：

template <typename KeyType, typename ValueType>
int HashTable<KeyType, ValueType>::hash(const KeyType& key) const {
  std::hash<KeyType> hash_func;
  return hash_func(key) % capacity_;
}

哈希冲突的解决方法

哈希冲突是指将两个不同的关键字映射到同一个索引位置的情况，解决哈希冲突的方法有多种，常用的方法包括链地址法、开放地址法等。

链地址法（Chaining）是最简单也是最常用的哈希冲突解决方法，它将哈希表中每个索引位置视为一个链表的头结点，当出现哈希冲突时，只需要在对应的链表中插入新的节点即可。具体实现如下：

template <typename KeyType, typename ValueType>
void HashTable<KeyType, ValueType>::insert(const KeyType& key, const ValueType& value) {
  int index = hash(key);
  Node* node = table_[index];
  while (node != nullptr) {
    if (node->key == key) {
      node->value = value;
      return;
    }
    node = node->next;
  }
  Node* new_node = new Node(key, value);
  new_node->next = table_[index];
  table_[index] = new_node;
  ++size_;
}

示例说明1：计算单词出现频率

哈希表的应用非常广泛，下面以计算文本中每个单词出现频率为例。具体实现过程如下：

1. 遍历文本中的每个单词，以单词为键，出现频率为值，插入哈希表中。

2. 遍历哈希表的每个键值对，输出单词和出现频率。

void word_count() {
  std::string text =
      "This is a test of word count. This is only a test. word count is "
      "important.";
  std::istringstream iss(text);
  std::string word;
  std::unordered_map<std::string, int> freq;
  while (iss >> word) {
    ++freq[word];
  }
  for (const auto& kv : freq) {
    std::cout << kv.first << ": " << kv.second << std::endl;
  }
}

示例说明2：对数列进行去重

哈希表的另一个常见应用是对数列进行去重。具体实现过程如下：

1. 遍历数列中的每个元素，以元素值为键，插入哈希表中。

2. 遍历哈希表的每个键，输出去重后的数列。

void unique_numbers() {
  std::vector<int> nums = {1, 3, 2, 4, 3, 5, 1, 3};
  std::unordered_set<int> unique_nums;
  for (int num : nums) {
    unique_nums.insert(num);
  }
  for (int num : unique_nums) {
    std::cout << num << " ";
  }
}

以上是C++数据结构哈希表的详细攻略，其中涉及到了哈希表的数据结构、哈希函数的设计、哈希冲突的解决方法等核心内容。同时，给出了两条示例说明哈希表的应用场景。