C++进阶：哈希

**C++进阶：哈希**

哈希（Hash）是一种常见的数据结构，用于快速查找、插入和删除元素。它通过将键值映射到一个固定长度的索引值来实现高效的存储和检索。

在 C++ 中，哈希表通常使用 `std::unordered_map` 或 `std::hash_map` 来实现。然而，在本文中，我们将重点讨论自定义哈希表的实现，以及一些常见的哈希函数。

### 哈希函数哈希函数是将键值映射到索引值的过程。它应该满足以下条件：

* **一致性**：对于相同的键值，哈希函数始终返回相同的索引值。
* **散列性**：不同的键值应有不同的索引值。

常见的哈希函数包括：

####1. 直接取模法

cppint hash(int key) {
 return key %10; // 取模为0-9 之间的整数}

这种方法简单易行，但可能导致冲突（多个键值映射到同一个索引值）。

####2. 位运算法

cppint hash(int key) {
 int result =0;
 while (key !=0) {
 result ^= key &1; // 异或运算 key >>=1; // 右移一位 }
 return result;
}

这种方法可以有效地减少冲突的可能性，但可能导致计算量较大。

####3. 乘法法

cppint hash(int key) {
 int prime =31; //选择一个质数作为乘数 int result =1;
 while (key !=0) {
 result = (result * prime + key % prime) % (prime -1); // 乘法和取模运算 key >>=3; // 右移三位 }
 return result;
}

这种方法可以有效地平衡冲突的可能性和计算量。

### 哈希表实现下面是一个简单的哈希表实现，使用链式存储结构来解决冲突：

cpp#include <iostream>
#include <list>

class HashTable {
private:
 int size; // 哈希表大小 std::list<int>* table; // 哈希表数组public:
 HashTable(int size) : size(size), table(new std::list<int>[size]) {}

 ~HashTable() { delete[] table; }

 void insert(int key, int value) {
 int index = hash(key); // 计算索引值 table[index].push_back(value); // 插入链式结构中 }

 int* search(int key) {
 int index = hash(key); // 计算索引值 for (auto& value : table[index]) { // 遍历链式结构 if (value == key) return &value; // 查找匹配的键值 }
 return nullptr;
 }

private:
 int hash(int key) {
 return key % size; // 使用直接取模法计算索引值 }
};

这个实现使用链式存储结构来解决冲突，插入和搜索操作都有较好的性能。

### 总结哈希表是一种常见的数据结构，用于快速查找、插入和删除元素。通过选择合适的哈希函数，可以有效地减少冲突的可能性并提高性能。在 C++ 中，可以使用 `std::unordered_map` 或自定义实现来构建哈希表。

本文介绍了哈希函数的基本概念，包括直接取模法、位运算法和乘法法。同时，提供了一个简单的哈希表实现，使用链式存储结构来解决冲突。

希望这篇文章能够帮助你更好地理解哈希表及其应用！