【C++进阶】哈希表

**哈希表（Hash Table）**

哈希表是一种常见的数据结构，用于快速查找、插入和删除元素。它通过使用散列函数将键值映射到一个特定的索引中，从而实现高效的存储和检索。

### 哈希表的基本概念哈希表由两个主要组成部分组成：

1. **散列函数（Hash Function）**：用于将键值转换为一个整数索引。
2. **桶数组（Bucket Array）**：用于存储实际数据，根据散列函数计算出的索引进行组织。

### 哈希表的优点哈希表具有以下优点：

* **快速查找和插入**：平均时间复杂度为 O(1)，即使在大量元素的情况下也能保持高效。
* **内存占用低**：由于使用散列函数将键值映射到一个特定的索引中，因此哈希表通常比其他数据结构（如链表或树）占用的内存少。

### 哈希表的缺点然而，哈希表也有一些缺点：

* **冲突**：当两个不同的键值散列到同一索引时，就会发生冲突。这可能导致查找、插入和删除操作变得缓慢。
* **散列函数选择困难**：选择一个合适的散列函数非常重要，因为它直接影响哈希表的性能。

### 哈希表的应用场景哈希表广泛用于以下场景：

* **快速查找和插入**：例如，缓存、计数器等。
* **集合或映射操作**：例如，集合中的元素数量、键值对的数量等。

### C++实现哈希表下面是一个简单的C++实现哈希表的例子：

cpp#include <iostream>
#include <vector>

// 哈希表类定义class HashTable {
private:
 // 桶数组大小 int bucketSize;
 // 散列函数 int hashFunction(int key) {
 return key % bucketSize;
 }
public:
 // 构造函数 HashTable(int size) : bucketSize(size), data(bucketSize, std::vector<int>()) {}

 // 插入元素 void insert(int key, int value) {
 int index = hashFunction(key);
 if (data[index].empty()) {
 data[index].push_back(value);
 } else {
 for (int i =0; i < data[index].size(); ++i) {
 if (data[index][i] == value) return;
 }
 data[index].push_back(value);
 }
 }

 // 查找元素 int find(int key) {
 int index = hashFunction(key);
 for (int i =0; i < data[index].size(); ++i) {
 if (data[index][i] == key) return key;
 }
 return -1; // 未找到 }

private:
 std::vector<std::vector<int>> data;
};

// 测试哈希表类int main() {
 HashTable hashTable(10);
 hashTable.insert(5,10);
 hashTable.insert(15,20);

 int result = hashTable.find(5);
 if (result != -1) std::cout << "Found: " << result << std::endl;
 else std::cout << "Not found" << std::endl;

 return0;
}