1. Toy模板网首页
  2. > Toy博客

C++【哈希表的模拟实现】

9月前 作者：北 海 分类：Toy博客 阅读(41) 违法举报

这篇具有很好参考价值的文章主要介绍了C++【哈希表的模拟实现】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

✨个人主页： 北 海
🎉所属专栏： C++修行之路
🎃操作环境： Visual Studio 2019 版本 16.11.17

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

🌇前言

哈希表的核心思想是 映射，对数据的键值进行处理后，映射 至表中对应的位置，实现存储，利用空间换时间，哈希表的查找效率非常高，可以达到 O(1)，哈希表的实现主要分为两种：闭散列 与 开散列，本文中将利用这两种方案实现哈希表

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

🏙️正文

1、模拟实现哈希表（闭散列）

闭散列与开散列是解决哈希冲突的两种方法

闭散列的关键在于 线性探测：当映射位置被占用时，向后移动，找到可用位置存储数据

探测后一定能找到可用的位置 [空 / 删除]

因为在闭散列中，还有一个 负载因子 用于控制是否需要扩容，确保一定有剩余空间

闭散列 存在 踩踏 问题，并不是很推荐使用

所谓的线性探测其实就是找位置，比如在停车场中，你中意的车位被占了，那只能在周围寻找可用车位（探测），找到后停好车，不过，你找的位置可能是别人中意的车位，别人停车时同样需要找车位（探测）

如此一来，本来大家都可以停在合适的位置，但因车位占用问题，局部秩序被打乱，最终导致整体秩序被打乱，而这就是 踩踏，秩序打乱后的直接影响是 寻找车位 变慢了！

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

1.1、存储数据结构的定义

闭散列中存储的数据至少包含两个信息：键值对、状态表示

键值对既可以是 K 也可以是 K / V，我们这里实现的是 K / V

而状态分为三种：

  1. 空 EMPTY 初始状态
  2. 存在 EXIST 插入数据后的状态
  3. 删除 DELETE 删除数据后的状态

其实简单分为 [可用 / 不可用] 两种状态也行，细分出 EMPTY 与 DELETE 是为了在进行 探测 时，提高效率

  • 探测 时，如果探测到空，就不必再探测，因为后面必然不存在我们想找的数据，如果存在，这里就不会为空了

所以闭散列中的 存储数据结构 可以用一个结构体定义

//节点状态
enum Status
{
	//空、被占用、删除
	EMPTY,
	EXIST,
	DELETE
};

//存储数据结构类
template<class K, class V>
struct HashData
{
	pair<K, V> _kv;	//键值对
	Status _status = EMPTY;	//状态
};

哈希表 的整体框架如下：

//闭散列
namespace ClosedHash
{
	//……
	
	//哈希表
	template<class K, class V>
	class HashTable
	{
		typedef HashData<K, V> Data;
	public:
		//……
	private:
		vector<Data> _table;	//数据表
		size_t _n;	//有效数据量（用于计算负载因子）
	};

1.2、查找

查找 的过程其实就是 找车位 的过程，无非就是判断 当前位置的数据是否为目标值

因为在 插入 时，是 线性探测式插入 的，所以 查找 时同样进行 线性探测，一旦发现当前位置为 空，就不必向后继续探测了，因为 后面必然不存在目标数据

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

查找 的代码如下：

HashData<K, V>* Find(const K& key)
{
	//如果其中没有数据，则查找失败
	if (_n == 0)
		return nullptr;

	//计算哈希值
	size_t HashI = key % _table.size();

	size_t index = HashI;	//保存位置，后面用来判断是否套圈了

	//查找（如果为空，说明其后面没有数据，不必继续探测）
	while (_table[index]._status != EMPTY)
	{
		//判断当前位置是否有数据+是否为目标
		if (_table[index]._status == EXIST && _table[index]._kv.first == key)
			return &_table[index];

		//线性探测
		index++;
		index %= _table.size();

		//判断是否绕圈了（找了一圈还没有找到）
		if (index == HashI)
			break;
	}

	return nullptr;
}

注意：

  1. 需要先保存哈希值，用于判断是否被套圈（找了一圈还没找到目标值）
  2. 函数返回的是当前位置存储数据的指针，如果不存在，则返回空 nullptr

1.3、插入

在进行数据插入前，可以 先通过查找判断该值是否已存在，避免数据冗余

如果不存在，则可以进行插入，插入步骤如下：

  1. 根据键值计算出下标（哈希值）
  2. 线性探测，找到可用的位置 [空 / 删除]
  3. 插入数据，有效数据量+1

插入部分的具体操作代码如下：

bool Insert(const pair<K, V>& kv)
{
	//首先查找当前 key 是否已经存在了
	if (Find(kv.first) != nullptr)
		return false;

	//扩容问题
	//……
	
	//获取下标（哈希值）
	size_t HashI = kv.first % _table.size();
	int i = 0;	//探测时的权值，方便改为二次探测
	
	//如果为存在，进行探测
	while (_table[HashI]._status == EXIST)
	{
		HashI += i;	//向后移动
		HashI %= _table.size();
		i++;
	}

	//找到空位置了，进行插入
	_table[HashI]._kv = kv;
	_table[HashI]._status = EXIST;
	_n++;	//插入一个数据

	return true;
}

如果想降低踩踏发生的概率，可以将 线性探测 改为 二次探测

HashI += (i * i);	//二次探测

以上就是 插入操作 的具体实现，此时面临着一个棘手的问题：扩容问题

当数据 第一次插入 或 负载因子达到临界值 时，需要进行 扩容（因为 vector<Data> _table 一开始为空，所以第一次插入也要扩容）

当空间扩容后，容量发生了改变，这也就意味着 数据与下标 的映射关系也发生了改变，需要更新数据，即重新进行线性探测

扩容可分为 传统写法 和 现代写法

传统写法

bool Insert(const pair<K, V>& kv)
{
	//查找
	//……
	
	//考虑扩容问题（存储数据超过容量的 70% 就扩容）
	if (_table.size() == 0 || _n * 10 / _table.size() == 7)
	{
		size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
		vector<Data> newTable(newSize);	//创建新表
	
		//将老表中的数据，挪动至新表（需要重新建立映射关系）
		for (auto& e : _table)
		{
			//获取下标（哈希值）
			size_t HashI = e._kv.first % newTable.size();
			int i = 0;	//探测时的权值，方便改为二次探测
	
			//如果为空，进行探测
			while (newTable[HashI]._status == EXIST)
			{
				HashI += i;	//向后移动
				HashI %= newTable.size();
				i++;
			}
	
			//找到空位置了，进行插入
			newTable[HashI]._kv = e._kv;
			newTable[HashI]._status = EXIST;
			_n++;	//插入一个数据
		}
	
		//交换新表、旧表（成本不大）
		_table.swap(newTable);
	}

	//插入
	//……
}

传统写法思路：创建一个容量足够的 新表，将 原表 中的数据映射至 新表 中，映射完成后，交换 新表 和 原表，目的是为了更新当前哈希表对象中的 表

关于 平衡因子 的控制
根据别人的试验结果，哈希表中的存储的有效数据量超过哈希表容器的 70% 时，推荐进行扩容
假设容量为 M，存储的有效数据量为 N，两者比率 N / M == 0.7 时进行扩容
因为我们这里的容量和数据量都是整数，所以在等式两边*10，可得 N * 10 / M == 7

传统写法比较繁琐，下面就来看看 现代写法

现代写法

bool Insert(const pair<K, V>& kv)
{
	//查找
	//……
	
	//现代写法：调用 Insert
	if (_table.size() == 0 || _n * 10 / _table.size() == 7)
	{
		size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
		HashTable<K, V> newHashTable;	//创建新哈希表
		newHashTable._table.resize(newSize);	//直接扩容，后续调用 Insert 插入数据时，空间是绝对够的

		//将老表中的数据，插入至新表（建立映射关系的工作交给 Insert）
		for (auto& e : _table)
			newHashTable.Insert(e._kv);

		//交换新表、旧表（成本不大）
		_table.swap(newHashTable._table);

		//细节：需不需要交换 _n ？
	}
	
	//插入
	//……
}

其实 传统写法 中的 插入部分逻辑 与 Insert 中的 插入操作 重复了，因此我们可以借助现代思想（白嫖），创建一个 容量足够的哈希表，将 原表 中的数据遍历插入 新的哈希表 中，插入的过程调用 Insert，代码极其间接，并且不容易出错

细节：需不需将当前对象中的 有效数据量 _n 进行更新？

  • 答案是不需要，往新的哈希表中插入 _n 个数据，意味着无论是 新的哈希表 还是当前对象，它们的有效数据量都是一致的，因此不需要更新

可以对 查找 和 插入 这两个功能进行测试

//测试
void TestCloseHash1()
{
	int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
	HashTable<int, int> ht;
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}

	ht.Insert(make_pair(15, 15));

	if (ht.Find(13))
	{
		cout << "13在" << endl;
	}
	else
	{
		cout << "13不在" << endl;
	}
}

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

数据在 哈希表 的存储关系如下：

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

1.4、删除

删除 操作就十分简单了，获取待删除数据，将其中的状态改为 删除 DELETE 即可，不必清空数据，只要访问不到就行了，当然，有效数据量-1

此时可以调用 查找 Find，如果待 删除 数据存在，可以得到指向它的指针，进行状态修改即可，如果不存在，就不进行操作，返回 false

bool Erase(const K& key)
{
	//查找目标是否存在
	HashData<K, V>* pret = Find(key);

	if (pret != nullptr)
	{
		//进行删除，更改状态为删除，数量-1即可
		pret->_status = DELETE;
		_n--;
		return true;
	}

	return false;
}

测试 删除 功能

void TestCloseHash2()
{
	int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
	HashTable<int, int> ht;
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}

	ht.Insert(make_pair(15, 15));

	if (ht.Find(13))
	{
		cout << "13在" << endl;
	}
	else
	{
		cout << "13不在" << endl;
	}

	ht.Erase(13);

	if (ht.Find(13))
	{
		cout << "13在" << endl;
	}
	else
	{
		cout << "13不在" << endl;
	}
}

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

哈希表（闭散列）实战价值不大，因此只做简单了解即可，真正重点在于 开散列

2、模拟实现哈希表（开散列）

哈希表（开散列） 又称为 哈希桶

因为它的下面挂着一个 单链表，形似一个 桶

哈希表（开散列） 就比较有 研究价值 了，因为它在解决 哈希冲突 的同时，不会产生 踩踏 问题，是一种比较灵活且强大的解决方案

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

2.1、存储节点结构的定义

哈希桶 中需要维护一个 单链表，因此需要一个 _next 指针指向下一个节点

//节点类
template<class K, class V>
struct HashNode
{
	HashNode(const pair<K, V>& kv)
		:_kv(kv)
		,_next(nullptr)
	{}

	pair<K, V> _kv;
	HashNode<K, V>* _next;	//指向下一个节点
};

因为引入了 单链表，所以 哈希桶 中 表 的存储类型也变成了 节点指针

//哈希表（哈希桶）
template<class K, class V>
class HashTable
{
	typedef HashNode<K, V> Node;

	//……

private:
	//哈希桶中不需要平衡因子，节点存储满后，进行扩容就行了
	vector<Node*> _table;
	size_t _n = 0;	//有效数据量
};

注意：哈希桶中不需要状态表示，因为可以直接插入

2.2、析构函数

因为有 单链表，所以在对象析构时，需要手动遍历其中的节点，将其释放，避免 内存泄漏

~HashTable()
{
	//因为哈希桶中涉及了我们直接写的单链表，因此需要手动释放节点
	//顺便把 vector 中的节点释放了
	for (auto& pnode : _table)
	{
		Node* cur = pnode;

		while (cur)
		{
			//保存下一个节点
			Node* next = cur->_next;

			//释放当前节点
			delete cur;
			cur = next;
		}

		pnode = nullptr;
	}
}

为什么 哈希表（闭散列） 中不需要写 析构函数？

  • 因为在闭散列中，表中存储的数据不涉及自定义类型的动态内存管理，并且 vector 在对象调用默认析构时，会被调用其析构，释放其中的内存

2.3、查找

哈希桶 在查找时，只需要先定位至具体的位置，然后遍历其中的 桶 中是否存在 目标 即可

//查找
Node* Find(const K& key)
{
	if (_table.size() == 0)
		return nullptr;

	//计算哈希值
	size_t HashI = key % _table.size();

	//在哈希值对应的桶里查找是否存在目标值
	Node* cur = _table[HashI];
	while (cur)
	{
		if (cur->_kv.first == key)
			return cur;
		cur = cur->_next;
	}

	return nullptr;
}

本质上就是单链表的遍历~

2.4、插入

在进行数据插入时，既可以尾插，也可以头插，因为桶中的存储顺序没有要求

为了操作简单，我们选择 头插

同样的，哈希桶在扩容时，也有传统写法和现代写法，这里采用 传统写法

//插入
bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first) != nullptr)
		return false;	//冗余

	//判断扩容
	if (_n == _table.size())
	{
		//传统写法
		size_t newSize = _table.size() == 0 ? 5 : _table.size() * 2;
		vector<Node*> newTable(newSize);	//新的表

		for (auto& cur : _table)
		{
			while (cur)
			{
				size_t HashI = cur->_kv.first % newSize;	//计算新的哈希值
				Node* next = cur->_next;

				//节点头插至新表（回收节点）
				cur->_next = newTable[HashI];
				newTable[HashI] = cur;


				cur = next;
			}
		}

		_table.swap(newTable);

		现代写法
		//size_t newSize = _table.size() == 0 ? 5 : _table.size() * 2;
		//HashTable<K, V> newHashTable;
		//newHashTable._table.resize(newSize);	//直接就扩容了

		//for (auto& cur : _table)
		//{
		//	while (cur)
		//	{
		//		newHashTable.Insert(cur->_kv);
		//		cur = cur->_next;
		//	}
		//}

		//_table.swap(newHashTable._table);
	}

	//插入
	size_t HashI = kv.first % _table.size();	//计算哈希值

	//单链表头插
	Node* cur = _table[HashI];	//原来的头节点
	_table[HashI] = new Node(kv);	//创建新的头
	_table[HashI]->_next = cur;	//连接
	_n++;

	return true;
}

这里的 传统写法 有一个很巧妙的地方：节点回收

既然 旧表 中节点不用了，那我可以直接把其中的节点 转移链接 至 新表 中，这样可以提高效率，且代码十分优雅

简单对 插入（含查找） 功能进行测试

//测试
void TestOpenHash1()
{
	int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
	HashTable<int, int> ht;
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}

	ht.Insert(make_pair(15, 15));
	ht.Insert(make_pair(25, 25));
	ht.Insert(make_pair(35, 35));
	ht.Insert(make_pair(45, 45));

	cout << ht.Find(5) << endl;
	cout << ht.Find(50) << endl;
}

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

注意：进行单链表链接操作时，要注意野指针问题

2.5、删除

哈希桶 的删除本质上就是 单链表 的删除，不过先要根据 哈希值 获取对应的 头节点

bool Erase(const K& key)
{
	//这里直接查找，因为需要保存上一个节点信息（单链表的删除）

	size_t HashI = key % _table.size();
	Node* prev = nullptr;
	Node* cur = _table[HashI];

	//单链表的删除
	while (cur)
	{
		Node* next = cur->_next;

		if (cur->_kv.first == key)
		{
			//删除
			if (prev == nullptr)
			{
				//头删
				_table[HashI] = next;
			}
			else
				prev->_next = next;

			delete cur;
			_n--;
			return true;
		}
		else
		{
			prev = cur;
			cur = next;
		}
	}

	return false;
}

测试 删除 功能

void TestOpenHash2()
{
	int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
	HashTable<int, int> ht;
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}

	cout << ht.Find(5) << endl;

	ht.Erase(12);
	ht.Erase(5);
	ht.Erase(33);

	cout << ht.Find(5) << endl;
}

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

注意：单链表删除时，需要考虑删除的是头节点的情况

2.6、桶的长度

哈希桶 中的长度不会太长，因为存在 扩容 机制，并且 每次扩容后，映射关系会进行更新，桶的整体高度会降低

可以插入大量数据，查看 哈希桶 的最大高度

class HashTable
{
	//……
	
	size_t MaxBucketSize()
	{
		size_t max = 0;
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			size_t size = 0;
			while (cur)
			{
				++size;
				cur = cur->_next;
			}
	
			if (size > max)
				max = size;
		}
	
		return max;
	}

	//……
};

void TestOpenHash3()
{
	//插入大量随机数，查看最长的桶长度
	srand((size_t)time(nullptr));

	HashTable<int, int> ht;

	int n = 1000000;
	for (int i = 0; i < n; i++)
	{
		int val = rand() + i;
		ht.Insert(make_pair(val, val));
	}

	//查看最长的长度
	cout << ht.MaxBucketSize() << endl;
}

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

插入约 100w 数据，哈希桶 的最大高度不过为 2

因此，哈希桶可以做到常数级别的查找速度，并且不存在 踩踏 问题

其实库中的 unordered_set 和 unordered_map 就是使用 哈希桶 封装实现的，就像 红黑树 封装 set 和 map 那样

不过我们当前的 哈希桶 仍然存在不少问题且不够完善，在下一篇文章中，我们首先对其进行完善，然后直接利用一个 哈希桶 封装实现 unordered_set 与 unordered_map

3、源码

本文中涉及的所有代码位于下面这个 Gitee 仓库中

《哈希表的模拟实现》

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

🌆总结

以上就是本次关于 C++【哈希表的模拟实现】的全部内容了，在本文中，我们主要对哈希表的两种实现方式：闭散列与开散列（哈希桶）进行了简单模拟实现，学习了 线性探测 和 单链表 这两种哈希冲突的解决方法，之前觉得没什么用的单链表，在此处闪闪发光

C++【哈希表的模拟实现】,C++修行之路,c++,散列表,开发语言,数据结构,学习

文章来源地址https://www.toymoban.com/news/detail-540420.html

相关文章推荐

C++ 进阶知识

C++【初识哈希】

C++【一棵红黑树封装 set 和 map】

C++【红黑树】

C++【AVL树】

C++【set 和 map 学习及使用】

C++【二叉搜索树】

C++【多态】

C++【继承】

到了这里，关于C++【哈希表的模拟实现】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • C++哈希表的实现

    C++哈希表的实现

    解决哈希冲突两种常见的方法是：闭散列和开散列 因为线性探测跟二次探测很像,所以这里就只实现线性探测了 1.线性探测 1.动图演示 2.注意事项 3.代码的注意事项 1.仿函数的问题: (1).因为string类型不能进行取模运算,因此给string类型增加一个仿函数 该仿函数可以将string转为整

    2024年02月04日
    浏览(44)
  • 【C++】“最强查找“哈希表的底层实现

    【C++】“最强查找“哈希表的底层实现

    哈希表的查找的时间复杂度是O（1）~ 文章目录 前言 一、哈希冲突和哈希函数 二、哈希表底层实现 1.开放地址法 2.链地址法 总结 哈希概念： 顺序结构以及平衡树 中，元素关键码与其存储位置之间没有对应的关系，因此在 查找一个元素 时，必须要经过关键码的多次比较 。

    2024年02月06日
    浏览(46)
  • 哈希表/散列表(HashTable)c++实现

    哈希表/散列表(HashTable)c++实现

    目录 哈希表实现的思想 除留余数法  哈希冲突 第一种方法：探测法实现哈希表 探测法的思想  结点类  插入数据(insert) 冲突因子 数据扩容 哈希值  插入的代码实现以及哈希类 查找数据(find) 删除数据(erase) 第二种方法：拉链法实现哈希表 结点类 哈希类的成员 插入(insert)

    2024年02月10日
    浏览(45)
  • 哈希桶的模拟实现【C++】

    哈希桶的模拟实现【C++】

    发生哈希冲突时，如果哈希表未被装满，说明在哈希表种必然还有空位置，那么可以把产生冲突的元素存放到冲突位置的“下一个”空位置中去 如何寻找“下一个位置” 1、 线性探测 发生哈希冲突时，从发生冲突的位置开始，依次向后探测，直到找到下一个空位置为止 Hi=

    2024年02月03日
    浏览(34)
  • 【C++】哈希（模拟实现unordered系列容器）

    【C++】哈希（模拟实现unordered系列容器）

    1、模板参数列表的改造 K ：关键码类型 V ：不同容器V的类型不同。如果是 unordered_map，V 代表一个键值对；如果是 unordered_set，V 为 K。 KeyOfValue ：因为 V 的类型不同，通过 value 取 key 的方式就不同，通过T的类型来获取 key 值。 HF ：哈希函数仿函数对象类型，哈希函数使用除留

    2024年02月05日
    浏览(41)
  • 模拟实现哈希表超详解（C++）

    模拟实现哈希表超详解（C++）

    😇 😇 hello！我是bug。前面几期我们讲解了树的相关结构，今天我们就要进入 哈希表 的学习了： （代码可能会有一点问题，请各位老铁指正 😘 😘 ） 🌵🌵在前面，我们学习了 红黑树、AVL树 的相关性质，他们增删查改的时间复杂度都是O（logN），这个效率已经是比较高的

    2023年04月08日
    浏览(29)
  • 【C++】哈希unordered系列容器的模拟实现

    【C++】哈希unordered系列容器的模拟实现

    开散列又叫链地址法（开链法），首先对关键码集合用散列函数计算散列地址，即 key 映射的下标位置，具有相同地址的关键码 (哈希冲突) 归于同一子集合，每一个子集合称为一个桶 (哈希桶)，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中；也就

    2024年02月13日
    浏览(37)
  • 【C++修炼之路】list 模拟实现

    【C++修炼之路】list 模拟实现

    👑作者主页：@安 度 因 🏠学习社区：StackFrame 📖专栏链接：C++修炼之路

    2024年02月16日
    浏览(38)
  • 【C++进阶之路】模拟实现string类

    【C++进阶之路】模拟实现string类

    本文所属专栏——【C++进阶之路】  上一篇,我们讲解了string类接口的基本使用，今天我们就实战从底层实现自己的string类，当然实现所有的接口难度很大，我们今天主要实现的常用的接口~ 1.为了 不与库里面的string冲突 ，我们需要 命名空间 对 自己实现的类进行封装 2.这里

    2024年02月13日
    浏览(44)
  • 【数据结构】哈希表的开散列和闭散列模拟

    【数据结构】哈希表的开散列和闭散列模拟

    在顺序和树状结构中，元素的存储与其存储位置之间是没有对应关系，因此在查找一个元素时，必须要经过多次的比较。 顺序查找的时间复杂度为0(N)，树的查找时间复杂度为log(N)。 我们最希望的搜索方式：通过元素的特性，不需要对比查找，而是直接找到某个元素。 这一个

    2024年02月22日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包