数据结构（c++版）：深入理解哈希表

Jeff-Nolan

1216人浏览 · 2025-11-06 20:41:43

Jeff-Nolan · 2025-11-06 20:41:43 发布

哈希表是计算机科学中一种高效的数据结构，它能够在平均情况下以常数时间复杂度O(1)进行插入、删除和查找操作。让我们通过分析上面的代码，结合生动的比喻，来彻底理解哈希表的工作原理。

哈希表的基本概念

想象一下你去图书馆借书，图书馆有256个书架（对应哈希表的大小）。每本书都有一个唯一的ISBN号（键），你需要找到特定的书（值）。哈希表就是这样一个"智能图书馆系统"。

哈希节点：书的存放单元

template<typename Keytype,typename Valutype>
class HashNode
{
public:
    Keytype key;        // ISBN号（唯一标识）
    Valutype valu;      // 书的内容
    HashNode* next;     // 同一书架上下一本书的指针

    HashNode(const Keytype& key, const Valutype& valu)
    {
        this->key = key;
        this->valu = valu;
        this->next = NULL;
    }
};

比喻：每个HashNode就像图书馆中的一个书位，它记录了书的ISBN号（key）、书的内容（value），以及同一书架上下一本书的位置（next指针）。

哈希表主体：图书馆的智能管理系统

template<typename Keytype, typename Valutype>
class Hashtable
{
private:
    int size;                                   // 图书馆的书架总数
    HashNode<Keytype,Valutype>** table;        // 书架阵列（指针数组）
    
    int Hash(const Keytype& key)const          // 图书归类算法
    {
        int hashkey = key % size;              // 根据ISBN决定放在哪个书架
        if (hashkey < 0) hashkey += size;      // 确保书架编号为正数
        return hashkey;
    }

比喻：

size：图书馆总共有的书架数量
table：所有书架的集合，每个书架可以放多本书
Hash函数：图书管理员的归类算法，根据ISBN号决定书应该放在哪个书架

哈希表的构建：建设图书馆

template<typename Keytype, typename Valutype>
Hashtable<Keytype, Valutype>::Hashtable(int size)
{
    this->size = size;
    this->table = new HashNode<Keytype, Valutype>* [size];
    for (int i = 0; i < size; i++)
    {
        table[i] = NULL;  // 初始化所有书架为空
    }
}

比喻：建设一个新图书馆，先确定要建多少个书架（size），然后准备好所有空书架（table数组初始化），确保每个书架初始时都是空的。

哈希函数：智能归类系统

哈希函数key % size就像图书管理员的归类规则：

规则简单高效：直接取模运算
均匀分布：确保书籍相对均匀地分布在不同书架
快速定位：通过ISBN号能立即知道在哪个书架查找

插入操作：新书入库

template<typename Keytype, typename Valutype>
void Hashtable<Keytype, Valutype>::insert(const Keytype& key, const Valutype& valu)
{
    int index = Hash(key);  // 确定放在哪个书架
    HashNode<Keytype, Valutype>* now = new HashNode<Keytype, Valutype>(key, valu);
    
    if (table[index] == NULL)  // 如果书架是空的
    {
        table[index] = now;    // 直接放在书架最前面
    }
    else {  // 采用头插法
        now->next = table[index];
        table[index] = now;
    }
}

比喻流程：

确定位置：管理员用ISBN号计算这本书应该放在3号书架（index = 3）
准备书籍：创建新的图书记录（new HashNode）
放置书籍：
- 如果3号书架是空的，直接放在最前面
- 如果已有书籍，采用"新书放在最前面"的策略（头插法），这样新书更容易被找到

查找操作：借书查询

template<typename Keytype, typename Valutype>
bool Hashtable<Keytype, Valutype>::find(const Keytype& key,Valutype&valu)const
{
    int index = Hash(key);  // 先确定在哪个书架
    
    if (table[index])  // 如果这个书架有书
    {
        if (table[index]->key == key)  // 检查第一本书
        {
            valu = table[index]->valu;
            return true;
        }
        else {  // 继续检查书架上的其他书
            HashNode<Keytype, Valutype>* curr = table[index];
            while (curr->next && curr->next->key != key)
            {
                curr = curr->next;
            }
            if (curr->next)  // 找到了
            {
                valu = curr->next->valu;
                return true;
            }
        }
    }
    return false;  // 整个图书馆都没有这本书
}

比喻流程：

定位书架：管理员根据ISBN算出在5号书架查找
顺序查找：
- 先看书架最前面的书（第一本）
- 如果不是，继续查看同一书架上的下一本
- 直到找到正确的ISBN或查完整个书架
返回结果：找到则返回书的内容，否则报告书籍不存在

删除操作：书籍下架

template<typename Keytype, typename Valutype>
void Hashtable<Keytype, Valutype>::Dlete(const Keytype& key)
{
    int index = Hash(key);
    
    if (table[index])  // 如果这个书架有书
    {
        if (table[index]->key == key)  // 要删除的是第一本书
        {
            HashNode<Keytype, Valutype>* next = table[index]->next;
            delete table[index];
            table[index] = next;  // 第二本书成为新的第一本
        }
        else {
            HashNode<Keytype, Valutype>* curr = table[index];
            // 找到要删除书籍的前一本书
            while (curr->next && curr->next->key != key)
            {
                curr = curr->next;
            }
            if (curr->next)  // 找到了要删除的书
            {
                HashNode<Keytype, Valutype>* next = curr->next->next;
                delete curr->next;     // 移除这本书
                curr->next = next;     // 前后书籍重新连接
            }
        }
    }
}

比喻流程：

定位书架：确定在哪个书架
查找书籍：
- 如果要删除的是书架的第一本书：直接移除，第二本书成为新的第一本
- 如果要删除的是中间或后面的书：找到前一本书，让它直接指向后一本书，跳过要删除的书
清理空间：物理上移除书籍记录

内存管理：图书馆的日常维护

template<typename Keytype, typename Valutype>
Hashtable<Keytype, Valutype>::~Hashtable()
{
    for (int i = 0; i < size; i++)  // 清理每个书架
    {
        if (table[i])  // 如果书架有书
        {
            HashNode<Keytype, Valutype>* curr = table[i];
            while (curr)  // 清空整个书架
            {
                HashNode<Keytype, Valutype>* next = curr->next;
                delete curr;  // 移除每本书
                curr = next;
            }
        }
        table[i] = NULL;  // 标记书架为空
    }
    delete []table;  // 拆除所有书架
    table = NULL;    // 标记图书馆已拆除
}

比喻：图书馆关闭时的清理工作：

逐个书架清理：从0号书架开始，清理每个书架上的所有书籍
书籍回收：逐本书籍进行销毁（释放内存）
拆除设施：最后拆除所有书架结构本身

哈希冲突与解决策略

哈希冲突就像不同ISBN的书籍被分配到同一个书架，这是不可避免的。我们的代码使用"链地址法"解决冲突：

冲突发生：两本不同的书被分配到同一个书架
解决方案：在同一个书架上用链表连接多本书
查找代价：最坏情况下需要遍历整个书架的书籍

代码中的实际演示

int main()
{
    Hashtable<int, char>h(1000);  // 建立有1000个书架的图书馆
    
    // 入库新书
    h.insert(1, 'a');      // ISBN=1的书，内容='a'
    h.insert(2, 'b');
    h.insert(3, 'c');
    h.insert(545674, 'd');
    h.insert(1001, 'g');
    
    char val;
    if (!h.find(51, val))  // 查找ISBN=51的书
    {
        cout << "51 not found" << endl;  // 未找到
    }
    if (h.find(545674, val))  // 查找ISBN=545674的书
    {
        cout << "545674 is found is :" << val << endl;  // 找到并输出内容
    }
    
    return 0;
}

哈希表的优势与局限

优势：

快速访问：平均O(1)时间复杂度
灵活扩容：可根据需要调整大小
键值对存储：天然的映射关系

局限：

内存占用：需要预分配空间
哈希冲突：最坏情况下性能退化
无序性：元素存储顺序不确定

总结

哈希表就像是一个高效的智能图书馆系统，通过哈希函数快速定位，通过链表解决冲突。理解哈希表的关键在于：

哈希函数是心脏：决定数据的分布效率
冲突解决是大脑：处理不可避免的"撞车"情况
内存管理是后勤：确保资源的高效利用

通过这个生动的图书馆比喻，相信你已经对哈希表的工作原理有了深刻的理解。下次使用字典或映射数据结构时，你会想起这个智能的"图书馆系统"是如何高效工作的！

源码及运行：

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
template<typename Keytype,typename Valutype>
class HashNode
{
public:
	Keytype key;
	Valutype valu;
	HashNode* next;

	HashNode(const Keytype& key, const Valutype& valu)//传的参数是键和值并且要加引用不能修改传入进来的参数
	{
		this->key = key;
		this->valu = valu;
		this->next = NULL;

	}
};
template<typename Keytype, typename Valutype>
class Hashtable
{
private:
	int size;
	HashNode<Keytype,Valutype>** table;//跟邻接表有点相似
	int Hash(const Keytype& key)const
	{
		int hashkey = key % size;
		if (hashkey < 0)
		{
			hashkey += size;
		}
		return hashkey;
	}
public:
	Hashtable(int size = 256);
	~Hashtable();
	void insert(const Keytype& key, const Valutype& valu);//不希望传进来的键和值被修改
	void Dlete(const Keytype& key);//键和值是一个整体删除键值就自然删除了
	bool find(const Keytype& key,Valutype& valu)const;

};



template<typename Keytype, typename Valutype>
Hashtable<Keytype, Valutype>::Hashtable(int size)
{
	this->size = size;//改变成员变量给成员size初始化
	this->table = new HashNode<Keytype, Valutype>* [size];//申请一个大小为size的表
	for (int i = 0; i < size; i++)//把表头置空，不然就变成野指针了
	{
		table[i] = NULL;
	}

}
template<typename Keytype, typename Valutype>
Hashtable<Keytype, Valutype>::~Hashtable()
{
	for (int i = 0; i < size; i++)
	{
		if (table[i])//遍历所有表头
		{
			HashNode<Keytype, Valutype>* curr = table[i];//申请临时变量来删除表里的同一个键的不同元素
			while (curr)//
			{
				HashNode<Keytype, Valutype>* next = curr->next;
				delete curr;
				curr = next;
			}
		}
		table[i] = NULL;//置空防止变成野指针
	}
	delete []table;//删除所有表头
	table = NULL;//给申请数组置空防止变成指针
}
template<typename Keytype, typename Valutype>
void Hashtable<Keytype, Valutype>::insert(const Keytype& key, const Valutype& valu)//插入操作
{
	int index = Hash(key);//把下标变成键值
	HashNode<Keytype, Valutype>* now = new HashNode<Keytype, Valutype>(key, valu);//创建新的哈希表节点
	if (table[index] == NULL)//表头为空则直接把要插入的键置为表头
	{
		table[index] = now;
	}
	else {//头插法插入表中
		now->next = table[index];
		table[index] = now;
	}

}
template<typename Keytype, typename Valutype>
void Hashtable<Keytype, Valutype>::Dlete(const Keytype& key)//键和值是一个整体删除键值就自然删除了
{
	int index = Hash(key);
	if (table[key])//哈希表头是否为空，为空就不用删除了
	{
		if (table[index] == key)//判断是否是表头
		{//是表头则将表头的下一个节点保存再next中，删除原来的表头，再把next置为表头
			HashNode<Keytype, Valutype>* next = table[index]->next;
			delete table[index];
			table[index] = next;
		}
		else {
			HashNode<Keytype, Valutype>* curr = table[key];//创建临时变量
			while (curr->next&&curr->next->key!=key)//遍历表头里面的元素找到要删除元素的前面一个
			{
				curr = curr->next;
			}
			if (curr->next)//创建临时遍历直接指向要删除的后面的节点，释放掉要删除节点的内存，把被删除的节点置为下一个节点。
			{
				HashNode<Keytype, Valutype>* next = curr->next->next;
				delete curr->next;
				curr->next = next;
			}

		}
	}
}
template<typename Keytype, typename Valutype>
bool Hashtable<Keytype, Valutype>::find(const Keytype& key,Valutype&valu)const//我传进来的valu会在找到后被修改所以valu前面不用const
{
	int index = Hash(key);//查找与删除部分逻辑相同，如果是表头就直接将值赋给传进来的键所对应的值然后返回。
	if (table[index])
	{
		if (table[index]->key == key)
		{
			valu = table[index]->valu;
				return true;
		}
		else {
			HashNode<Keytype, Valutype>* curr = table[index];
			while (curr->next && curr->next->key != key)
			{
				curr = curr->next;
			}
			if (curr->next)
			{
				valu = curr->next->valu;
              return true;
			}
		}
	}
	return false;
}
int main()
{
	Hashtable<int, char>h(1000);
	h.insert(1, 'a');
	h.insert(2, 'b');
	h.insert(3, 'c');
	h.insert(545674, 'd');
	h.insert(1001, 'g');
	char val;
	if (!h.find(51, val))
	{
		cout << "51 not found" << endl;
	}
	if (h.find(545674, val))
	{
		cout << "545674 is found is :" << val << endl;
	}
	if (h.find(1001, val))
	{
		cout << "1001 is found is :" << val << endl;
	}
	Hashcount<long long>hc(1000);
	hc.add(6);
	hc.add(6);
	hc.add(6);
	hc.add(6);
	hc.add(5);
	hc.add(6);
	hc.add(6);
	hc.sub(6);
	cout << hc.get(6) << endl;
	cout << hc.get(5) << endl;

	return 0;
}

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

2026企业微信AI Agent实测：7款技术方案对比

会话审计、敏感词管理、聊天质检、敏感行为识别、舆情、属性、词频及竞品分析覆盖服务风险；线索公海、客户、产品、商机、订单、回款、发票和业绩目标则连接销售全过程。快创助手负责快速建运营任务，策略生成把目标拆成方案，智能客服回答系统使用咨询，数据报表处理自然语言查数，AI洞察联合标签、订单和会话分析客户。我们设计了客户筛选、订单关联、销售交接、会话质检和异常恢复任务，配合技术访谈与行业公开资料复核。准备