C++ 哈希表：简单易懂的手动实现

想要学习如何不使用容器创建C++哈希表？答案就在这里！本文将带你逐步了解如何利用数组和哈希函数创建一个简单的哈希表。

什么是哈希表？

哈希表是一种高效的数据结构，它使用哈希函数将键映射到特定的索引位置，从而实现快速的数据访问。

C++代码示例

以下代码展示了如何使用数组构建一个基本的哈希表：cpp#include

const int TABLE_SIZE = 10; // 哈希表的大小

struct HashNode { int key; std::string value;};

class HashTable {private: HashNode* table[TABLE_SIZE];

public: HashTable() { // 初始化哈希表 for (int i = 0; i < TABLE_SIZE; i++) { table[i] = nullptr; } }

int hashFunction(int key) {        // 哈希函数：将键映射到索引位置        return key % TABLE_SIZE;    }

void insert(int key, std::string value) {        int index = hashFunction(key);  // 计算插入的索引位置

    if (table[index] == nullptr) {            // 如果索引位置没有元素，直接插入            HashNode* newNode = new HashNode;            newNode->key = key;            newNode->value = value;            table[index] = newNode;        } else {            // 如果索引位置已经有元素，使用链表法解决冲突            HashNode* currentNode = table[index];            while (currentNode->next != nullptr) {                currentNode = currentNode->next;            }            HashNode* newNode = new HashNode;            newNode->key = key;            newNode->value = value;            currentNode->next = newNode;        }    }

std::string search(int key) {        int index = hashFunction(key);  // 计算搜索的索引位置

    HashNode* currentNode = table[index];        while (currentNode != nullptr) {            if (currentNode->key == key) {                return currentNode->value;            }            currentNode = currentNode->next;        }        return '';  // 如果没有找到，返回空字符串    }};

int main() { HashTable hashTable;

// 向哈希表中插入元素    hashTable.insert(1, 'Alice');    hashTable.insert(2, 'Bob');    hashTable.insert(3, 'Charlie');

// 在哈希表中搜索元素    std::cout << hashTable.search(2) << std::endl;  // 输出 'Bob'

return 0;}

代码解释

HashTable 类: 代表我们创建的哈希表。2. table: 一个 HashNode 指针数组，用于存储数据。3. hashFunction: 将键转换为数组索引的哈希函数。4. insert: 向哈希表插入新的键值对。如果发生冲突（多个键映射到同一个索引），则使用链表法解决。5. search: 根据键搜索对应的值。

总结

这段代码展示了如何使用数组和哈希函数创建一个简单的哈希表。你可以根据自己的需求对代码进行修改和扩展，例如实现删除元素等功能。