哈希表的实现（C++ 和 C 语言）

哈希表简介

哈希表是一种通过哈希函数将键映射到数组索引的数据结构，能够实现高效的数据查找、插入和删除。适用于需要快速访问的场景。

C语言实现

代码示例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define TABLE_SIZE 10 // 定义哈希表的大小// 哈希表节点
typedef struct Node {char *key;int value;struct Node *next; // 链表的下一个节点
} Node;// 哈希表结构体
typedef struct HashTable {Node **table; // 指向节点的指针数组
} HashTable;// 哈希函数
unsigned int hash(char *key) {unsigned int hash = 0;while (*key) {hash = (hash << 5) + *key++; // 计算哈希值}return hash % TABLE_SIZE; // 返回索引
}// 创建哈希表
HashTable* create_table() {HashTable *ht = malloc(sizeof(HashTable));ht->table = malloc(sizeof(Node*) * TABLE_SIZE);for (int i = 0; i < TABLE_SIZE; i++) {ht->table[i] = NULL; // 初始化为空}return ht;
}// 插入键值对
void insert(HashTable *ht, char *key, int value) {unsigned int index = hash(key);Node *new_node = malloc(sizeof(Node));new_node->key = strdup(key); // 复制键new_node->value = value;new_node->next = ht->table[index]; // 插入到链表头部ht->table[index] = new_node;
}// 查找值
int search(HashTable *ht, char *key) {unsigned int index = hash(key);Node *current = ht->table[index];while (current) {if (strcmp(current->key, key) == 0) {return current->value; // 找到返回值}current = current->next; // 继续查找}return -1; // 找不到返回 -1
}// 释放哈希表内存
void free_table(HashTable *ht) {for (int i = 0; i < TABLE_SIZE; i++) {Node *current = ht->table[i];while (current) {Node *temp = current;current = current->next;free(temp->key); // 释放键free(temp);}}free(ht->table); // 释放表free(ht); // 释放哈希表结构体
}int main() {HashTable *ht = create_table();insert(ht, "apple", 1);insert(ht, "banana", 2);printf("Value for key 'apple': %d\n", search(ht, "apple"));printf("Value for key 'banana': %d\n", search(ht, "banana"));free_table(ht); // 释放内存return 0;
}

C++语言实现

代码示例

#include <iostream>
#include <string>
#include <list>
#include <vector>class HashTable {
private:static const int TABLE_SIZE = 10; // 定义哈希表的大小std::vector<std::list<std::pair<std::string, int>>> table; // 使用链表处理碰撞// 哈希函数int hash(const std::string &key) {int hash = 0;for (char ch : key) {hash = (hash * 31 + ch) % TABLE_SIZE; // 计算哈希值}return hash;}public:HashTable() : table(TABLE_SIZE) {} // 初始化哈希表// 插入键值对void insert(const std::string &key, int value) {int index = hash(key);table[index].emplace_back(key, value); // 使用 emplace_back 插入}// 查找值int search(const std::string &key) {int index = hash(key);for (const auto &pair : table[index]) {if (pair.first == key) {return pair.second; // 找到返回值}}return -1; // 找不到返回 -1}
};int main() {HashTable ht;ht.insert("apple", 1);ht.insert("banana", 2);std::cout << "Value for key 'apple': " << ht.search("apple") << std::endl;std::cout << "Value for key 'banana': " << ht.search("banana") << std::endl;return 0;
}