哈希表的简单模拟实现

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

哈希表的简单模拟实现,散列表,哈希算法,数据结构,C++,c

初识哈希

哈希表是一种查找效率及其高的算法,最理想的情况下查询的时间复杂度为O(1)。

unordered_map容器通过key访问单个元素要比map快,但它通常在遍历元素子集的范围迭代方面效率

较低。

底层结构

unordered系列的关联式容器之所以效率更高,是因为底层采用了哈希的结构。

哈希是通过对key进行映射,然后通过映射值直接去拿到要的数据,效率更高,平衡树的查找是通过依次比对,相对而言就会慢一些。

  • 插入元素:通过计算出元素的映射值,来后通过映射值把元素插入到储存的位置当中。
  • 搜索元素:通过计算元素的映射值来取得元素。

哈希方法中使用的转换函数称之为哈希(散列)函数,构造出来的结构叫做哈希表(散列表)

例: 集合 {1,7,6,4,5,9,11,21};

哈希函数为:hash(key)=key%capacity,capacity为底层空间的最大值。

0 1 2 3 4 5 6 7 8 9
1 11 21 4 5 6 9

1%10=1、4%10=4、7%10=10…

但如果我要插入一个11怎么办?

这就是一个经典的问题,哈希冲突

哈希冲突

解决哈希冲突的两种常见方式就是:闭散列开散列

闭散列

闭散列也叫开放寻址法,当发生冲突的时候我就往后面去找,假如1和11去%10都等于1,但是1先去把1号坑位占了,那么11肯定不能把1的坑位抢了,只能往后找有没有没有被占的坑位,有的话就放11,这个方法叫做线性探测法

但是我要删除某个值该怎么办呢?

0 1 2 3 4 5 6 7 8 9
1 11 21 4 5 6 9

例如这段数据,我把11删掉之后

0 1 2 3 4 5 6 7 8 9
1 21 4 5 6 9

2的位置就空出来了,当我想要去找21的时候会发现找不到,因为找某个值和插入某个值是一样的,先确定映射值,如果不是当前值就往后面找,如果为空就找完了,这里2为空,不能继续往后找了,就要返回查找失败了,但是21是存在的呀,所以可以对每一个哈希节点进行标记,在每一个节点中记录一个状态值,是Empty还是Exit还是Delete,这样就可以避免上述情况了。

定义哈希节点

	//枚举状态
	enum State
	{
		Empty,
		Exit,
		Delete
	};

	template<class K,class V>
	struct Hash_Node
	{
		pair<K, V> _kv;
		State _state = Empty;
	};

定义哈希表

	template<class K,class V>
	class Hash_table
	{
	public:
		typedef Hash_Node<K, V> Node;
		
	private:
		vector<Node> _tables;
		size_t _size=0;
	};

哈希表什么情况下进行扩容?如何扩容?

哈希表的简单模拟实现,散列表,哈希算法,数据结构,C++,c

Insert()函数

bool Insert(const pair<K,V>& key)
		{
			//查重
			if (Find(key.first))
			{
				return false;
			}
			//扩容

			if (_tables.size()==0||10*_size / _tables.size()>=7)
			{
				//大于7需要扩容
				size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();
				Hash_table<K, V>newHT;
				newHT._tables.resize(newSize);//新表

				//复用Insert函数
				for (auto& e : _tables)
				{
					if (e._state == Exit)
					{
						newHT.Insert(e._kv);
					}
				}
				_tables.swap(newHT._tables);
			}
    			//线性探测
			size_t hashi = key.first % _tables.size();
			while (_tables[hashi]._state == Exit)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = key;
			_tables[hashi]._state = Exit;
			_size++;
    		return true;
		}

Find()函数

Hash_Node<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0) return nullptr;

			size_t start = key % _tables.size();
			size_t begin = start;
			while (_tables[start]._state != Empty)
			{
				if (_tables[start]._state != Delete && _tables[start]._kv.first == key)
				{
					return &_tables[start];
				}
				start++;
				start %= _tables.size();

				if (begin == start)
				{
					break;
				}
			}
			return nullptr;
		}

样例测试

	void test1()
	{
		int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,21,31,41,51,61,71,81,91,101 };
		Hash_table<int, int>hs;
		for (auto e : arr)
		{
			hs.Insert(make_pair(e, e));
		}
	}

测试结果如下:

哈希表的简单模拟实现,散列表,哈希算法,数据结构,C++,c

可以看到都是被成功的插入了。

线性探测的优先:简单方便。

线性探测的缺点:一旦发生哈希冲突了,所有的冲突都会堆积在一块,会导致查找的效率变得很低。

二次探测

二次探测其实就是每次跳过i的平方个间隔,原来的线性探测是一个一个往后找。

0 1 2 3 4 5 6 7 8 9
Exit Exit Exit

比如在1发生了哈希冲突,那么线性探测就会去找2位置,然后再找3位置,直到找到空为止。

但二次探测是1没有,i=1,i的平方等于1,找2位置,i=2,i的平方等于4,找5位置,发现没有元素,就直接占位,二次探测可以让数据更加分散,降低哈希冲突的发生率。

		size_t start = hash(kv.first) % _tables.size();
		size_t i = 0;
		size_t hashi = start;
		// 二次探测
		while (_tables[hashi]._state == Exit)
		{
			++i;
			hashi = start + i*i;
			hashi %= _tables.size();
		}

		_tables[hashi]._kv = kv;
		_tables[hashi]._state = EXIST;
		++_size;

以上的哈希表只能用来映射int类型的值,如果是其他类型就不行了,这里可以增加一个仿函数来兼容其他类型,这里最重要的是string类型了,如何才能将string类型转换为一个数值。

我们可以把ASCII码相加,就能得到key了,但是面对以下场景就会哈希冲突了。

string str1="abc";
string str2="acb";
string str3="cba";

这里有大佬得出过一个结论

hash = hash * 131 + ch,这样可以降低哈希碰撞的概率。

HashFunc()仿函数

	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	//特例化模板参数来解决string的问题
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t val = 0;
			for (auto ch : key)
			{
				val *= 131;
				val += ch;
			}

			return val;
		}
	};
#pragma once
#include<iostream>
#include<set>
#include<vector>
using namespace std;

//闭散列
namespace mudan
{
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	//特例化模板参数来解决string的问题
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t val = 0;
			for (auto ch : key)
			{
				val *= 131;
				val += ch;
			}

			return val;
		}
	};

	enum State
	{
		Empty,
		Exit,
		Delete
	};

	template<class K,class V>
	struct Hash_Node
	{
		pair<K, V> _kv;
		State _state = Empty;
	};

	template<class K,class V,class Hash=HashFunc<K>>
	class Hash_table
	{
	public:
		typedef Hash_Node<K, V> Node;
		
		bool Insert(const pair<K,V>& key)
		{
			//查重
			if (Find(key.first))
			{
				return false;
			}
			//扩容

			if (_tables.size()==0||10*_size / _tables.size()>=7)
			{
				//大于7需要扩容
				size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();
				Hash_table<K, V>newHT;
				newHT._tables.resize(newSize);//新表

				//复用Insert函数
				for (auto &e : _tables)
				{
					if (e._state == Exit)
					{
						newHT.Insert(e._kv);
					}
				}
				_tables.swap(newHT._tables);
			}
			
			Hash hash;
			//线性探测
			size_t hashi = hash(key.first) % _tables.size();
			while (_tables[hashi]._state == Exit)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = key;
			_tables[hashi]._state = Exit;
			_size++;
            return true;
		}

		Hash_Node<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0) return nullptr;

			Hash hash;
			size_t start = hash(key) % _tables.size();
			size_t begin = start;
			while (_tables[start]._state != Empty)
			{
				if (_tables[start]._state != Delete && _tables[start]._kv.first == key)
				{
					return &_tables[start];
				}
				start++;
				start %= _tables.size();

				if (begin == start)
				{
					break;
				}
			}
			return nullptr;
		}

	private:
		vector<Node> _tables;
		size_t _size;
	};

	void TestHT2()
	{
		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

		//HashTable<string, int, HashFuncString> countHT;
		Hash_table<string, int> countHT;
		for (auto& str : arr)
		{
			auto ptr = countHT.Find(str);
			if (ptr)
			{
				ptr->_kv.second++;
			}
			else
			{
				countHT.Insert(make_pair(str, 1));
			}
		}
	}


	void test1()
	{
		int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,21,31,41,51,61,71,81,91,101 };
		Hash_table<int, int>hs;
		for (auto e : arr)
		{
			hs.Insert(make_pair(e, e));
		}
	}
}

可以看到映射也成功了。

哈希表的简单模拟实现,散列表,哈希算法,数据结构,C++,c

哈希表的简单模拟实现,散列表,哈希算法,数据结构,C++,c

对于之前说的问题也解决了。

string str1="abc";
string str2="acb";
string str3="cba";		

Erase()函数

这个就简单了,Erase不是真正意义上把这个数字从数组当中删掉,而是改变状态,把状态改成Delete即可。

		bool Erase(const K& key)
		{
			Hash_Node<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = Delete;
				--_size;
				return true;
			}
			else
			{
				return false;
			}
		}

全部的代码

#pragma once
#include<iostream>
#include<set>
#include<vector>
using namespace std;

//闭散列
namespace mudan
{
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	//特例化模板参数来解决string的问题
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t val = 0;
			for (auto ch : key)
			{
				val *= 131;
				val += ch;
			}

			return val;
		}
	};

	enum State
	{
		Empty,
		Exit,
		Delete
	};

	template<class K,class V>
	struct Hash_Node
	{
		pair<K, V> _kv;
		State _state = Empty;
	};

	template<class K,class V,class Hash=HashFunc<K>>
	class Hash_table
	{
	public:
		typedef Hash_Node<K, V> Node;
		
		bool Insert(const pair<K,V>& key)
		{
			//查重
			if (Find(key.first))
			{
				return false;
			}
			//扩容

			if (_tables.size()==0||10*_size / _tables.size()>=7)
			{
				//大于7需要扩容
				size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();
				Hash_table<K, V>newHT;
				newHT._tables.resize(newSize);//新表

				//复用Insert函数
				for (auto &e : _tables)
				{
					if (e._state == Exit)
					{
						newHT.Insert(e._kv);
					}
				}
				_tables.swap(newHT._tables);
			}
			
			Hash hash;
			//线性探测
			size_t hashi = hash(key.first) % _tables.size();
			while (_tables[hashi]._state == Exit)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = key;
			_tables[hashi]._state = Exit;
			_size++;
			return true;
		}

		Hash_Node<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0) return nullptr;

			Hash hash;
			size_t start = hash(key) % _tables.size();
			size_t begin = start;
			while (_tables[start]._state != Empty)
			{
				if (_tables[start]._state != Delete && _tables[start]._kv.first == key)
				{
					return &_tables[start];
				}
				start++;
				start %= _tables.size();

				if (begin == start)
				{
					break;
				}
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			Hash_Node<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = Delete;
				--_size;
				return true;
			}
			else
			{
				return false;
			}
		}

	private:
		vector<Node> _tables;
		size_t _size=0;
	};

	void TestHT2()
	{
		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

		//HashTable<string, int, HashFuncString> countHT;
		Hash_table<string, int> countHT;
		for (auto& str : arr)
		{
			auto ptr = countHT.Find(str);
			if (ptr)
			{
				ptr->_kv.second++;
			}
			else
			{
				countHT.Insert(make_pair(str, 1));
			}
		}
	}


	void test1()
	{
		int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,21,31,41,51,61,71,81,91,101 };
		Hash_table<int, int>hs;
		for (auto e : arr)
		{
			hs.Insert(make_pair(e, e));
		}
	}

	void TestHT3()
	{
		HashFunc<string> hash;
		cout << hash("abcd") << endl;
		cout << hash("bcad") << endl;
		cout << hash("eat") << endl;
		cout << hash("ate") << endl;
		cout << hash("abcd") << endl;
		cout << hash("aadd") << endl << endl;

		cout << hash("abcd") << endl;
		cout << hash("bcad") << endl;
		cout << hash("eat") << endl;
		cout << hash("ate") << endl;
		cout << hash("abcd") << endl;
		cout << hash("aadd") << endl << endl;
	}
}

开散列

哈希表的简单模拟实现,散列表,哈希算法,数据结构,C++,c

开散列如上图所示,他有一个桶子来表示key值,然后key值相同的(哈希冲突的)就都连接到这个桶的key对应的位置下面。

这个桶其实就是一个指针数组

定义哈希节点

	template<class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K,V>* _next;

		HashNode(const pair<K,V>& data)
			:_kv(data)
			,_next(nullptr)
		{}
	};

定义哈希表

template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;

	public:

	private:
		vector<Node*>_tables;
		size_t _size=0;
	};

Insert()函数

插入操作头插和尾插都很快,这里由于定义的是单链表,就选择头插了。

插入过程如下图所示:

哈希表的简单模拟实现,散列表,哈希算法,数据结构,C++,c

bool Insert(const pair<K, V>& key)
		{
			Hash hash;
			//去重

			if (Find(key.first)) return false;

			//负载因子等于1就要扩容了

			if (_size == _tables.size())
			{
				size_t newsize = _tables.size() == 0 ? 10:2 * _tables.size();
				vector<Node*>newTables;
				newTables.resize(newsize);
				
				for (int i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						
						size_t hashi = hash(cur->_kv.first) % newTables.size();
						cur->_next =newTables[hashi];
						newTables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;//销毁原来的桶
				}
				_tables.swap(newTables);
			}

			//头插
			//  head
			//    1     2头插,2->next=1,head=2;
			size_t hashi = hash(key.first) % _tables.size();
			Node* newnode = new Node(key);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_size;

			return true;
		}

Find()函数

		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			//没找到,返回空
			return nullptr;
		}

Erase()函数

和链表的和删除一摸一样文章来源地址https://www.toymoban.com/news/detail-610977.html

bool Erase(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					// 1、头删
					// 2、中间删
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_size;

					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

总代码

#pragma once
#include<iostream>
#include<set>
#include<vector>
using namespace std;

//闭散列
namespace mudan
{
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	//特例化模板参数来解决string的问题
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t val = 0;
			for (auto ch : key)
			{
				val *= 131;
				val += ch;
			}

			return val;
		}
	};

	enum State
	{
		Empty,
		Exit,
		Delete
	};

	template<class K,class V>
	struct Hash_Node
	{
		pair<K, V> _kv;
		State _state = Empty;
	};

	template<class K,class V,class Hash=HashFunc<K>>
	class Hash_table
	{
	public:
		typedef Hash_Node<K, V> Node;
		
		bool Insert(const pair<K,V>& key)
		{
			//查重
			if (Find(key.first))
			{
				return false;
			}
			//扩容

			if (_tables.size()==0||10*_size / _tables.size()>=7)
			{
				//大于7需要扩容
				size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();
				Hash_table<K, V>newHT;
				newHT._tables.resize(newSize);//新表

				//复用Insert函数
				for (auto &e : _tables)
				{
					if (e._state == Exit)
					{
						newHT.Insert(e._kv);
					}
				}
				_tables.swap(newHT._tables);
			}
			
			Hash hash;
			//线性探测
			size_t hashi = hash(key.first) % _tables.size();
			while (_tables[hashi]._state == Exit)
			{
				hashi++;
				hashi %= _tables.size();
			}
			_tables[hashi]._kv = key;
			_tables[hashi]._state = Exit;
			_size++;
			return true;
		}

		Hash_Node<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0) return nullptr;

			Hash hash;
			size_t start = hash(key) % _tables.size();
			size_t begin = start;
			while (_tables[start]._state != Empty)
			{
				if (_tables[start]._state != Delete && _tables[start]._kv.first == key)
				{
					return &_tables[start];
				}
				start++;
				start %= _tables.size();

				if (begin == start)
				{
					break;
				}
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			Hash_Node<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = Delete;
				--_size;
				return true;
			}
			else
			{
				return false;
			}
		}

	private:
		vector<Node> _tables;
		size_t _size=0;
	};

	void TestHT2()
	{
		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

		//HashTable<string, int, HashFuncString> countHT;
		Hash_table<string, int> countHT;
		for (auto& str : arr)
		{
			auto ptr = countHT.Find(str);
			if (ptr)
			{
				ptr->_kv.second++;
			}
			else
			{
				countHT.Insert(make_pair(str, 1));
			}
		}
	}


	void test1()
	{
		int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,21,31,41,51,61,71,81,91,101 };
		Hash_table<int, int>hs;
		for (auto e : arr)
		{
			hs.Insert(make_pair(e, e));
		}
	}

	void TestHT3()
	{
		HashFunc<string> hash;
		cout << hash("abcd") << endl;
		cout << hash("bcad") << endl;
		cout << hash("eat") << endl;
		cout << hash("ate") << endl;
		cout << hash("abcd") << endl;
		cout << hash("aadd") << endl << endl;

		cout << hash("abcd") << endl;
		cout << hash("bcad") << endl;
		cout << hash("eat") << endl;
		cout << hash("ate") << endl;
		cout << hash("abcd") << endl;
		cout << hash("aadd") << endl << endl;
	}
}

namespace mudan1
{

	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	//特例化模板参数来解决string的问题
	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& key)
		{
			size_t val = 0;
			for (auto ch : key)
			{
				val *= 131;
				val += ch;
			}

			return val;
		}
	};

	template<class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K,V>* _next;

		HashNode(const pair<K,V>& data)
			:_kv(data)
			,_next(nullptr)
		{}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;

	public:

		bool Insert(const pair<K, V>& key)
		{
			Hash hash;
			//去重

			if (Find(key.first)) return false;

			//负载因子等于1就要扩容了

			if (_size == _tables.size())
			{
				size_t newsize = _tables.size() == 0 ? 10:2 * _tables.size();
				vector<Node*>newTables;
				newTables.resize(newsize);
				
				for (int i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						
						size_t hashi = hash(cur->_kv.first) % newTables.size();
						cur->_next =newTables[hashi];
						newTables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;//销毁原来的桶
				}
				_tables.swap(newTables);
			}

			//头插
			//  head
			//    1     2头插,2->next=1,head=2;
			size_t hashi = hash(key.first) % _tables.size();
			Node* newnode = new Node(key);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_size;

			return true;
		}

		Node* Find(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			//没找到,返回空
			return nullptr;
		}

		bool Erase(const K& key)
		{
			if (_tables.size() == 0)
			{
				return nullptr;
			}

			Hash hash;
			size_t hashi = hash(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					// 1、头删
					// 2、中间删
					if (prev == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_size;

					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

	private:
		vector<Node*>_tables;
		size_t _size=0;
	};

	void TestHT1()
	{
		int a[] = { 1, 11, 4, 15, 26, 7, 44,55,99,78 };
		HashTable<int, int> ht;
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}

		ht.Insert(make_pair(22, 22));
	}
}

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

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

领支付宝红包 赞助服务器费用

相关文章

  • 实验:哈希表的算法实现

    实验内容 : 采用除留余数法实现哈希表的创建,任意采用一种处理冲突的方法解决冲突,计算哈希表的平均查找长度。编程 实现以下功能: 已知一组(19,14,23,1,68,20,84,27,55,11,10,79),哈希函数定义为:H(key)=key MOD 13, 哈希表长为m=16。实现该哈希表的散列,并计算平均查找

    2024年02月04日
    浏览(40)
  • 【算法】哈希表介绍 | 哈希表的链式地址法代码实现(C/C++)

    创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡𖥦)!! 主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步! 更多算法分析与设计知识专栏:算法分析🔥 给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ 哈希表(H

    2024年01月16日
    浏览(39)
  • C语言简单的数据结构:单链表的有关算法题(2)

    接着我们介绍后面的三道题,虽然代码变多了但我们的思路更加通顺了 题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/ 创建新链表,遍历原链表,将节点值小的进行尾插到新链表中 这里要多次进行对NULL的判断,开始传入列表,中间newHead的判断,循环出来一个为NULL的判断

    2024年04月15日
    浏览(63)
  • 数据结构----链表介绍、模拟实现链表、链表的使用

    ArrayList底层使用连续的空间,任意位置插入或删除元素时,需要将该位置后序元素整体往前或者往后搬移,故时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后

    2024年02月21日
    浏览(51)
  • 【数据结构】单链表的简单实现

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元

    2024年02月04日
    浏览(57)
  • 哈希表-散列表数据结构

    哈希表也叫散列表,哈希表是根据关键码值(key value)来直接访问的一种数据结构,也就是将关键码值(key value)通过一种映射关系映射到表中的一个位置来加快查找的速度,这种映射关系称之为哈希函数或者散列函数,存放记录的数组称之为哈希表。 哈希表采用的是一种转换思

    2024年01月21日
    浏览(55)
  • 数据结构-顺序表的基本实现(C语言,简单易懂,含全部代码)

    今天起开始编写数据结构中的各种数据结构及算法的实现,说到顺序表,我们首先得了解下线性表。 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻

    2023年04月08日
    浏览(39)
  • 【数据结构(C++版)】哈希表(散列表)

    目录   1. 散列表的概念 2. 散列函数的构造方法 2.1 直接定址法 2.2 除留余数法 2.3 数字分析法 2.4 平方取中法 3. 处理冲突的方法 3.1 开放定址法 3.1.1 线性探测法 3.1.2 平方探测法 3.1.3 双散列法 3.1.4 伪随机序列法 3.2 拉链法(链接法) 4. 散列查找及性能分析 5. 哈希的应用 5.1 位

    2024年02月15日
    浏览(45)
  • 【数据结构与算法】深入浅出:单链表的实现和应用

      🌱博客主页:青竹雾色间. 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注  ✨ 人生如寄,多忧何为  ✨ 目录 前言 单链表的基本概念 节点 头节点 尾节点 单链表的基本操作 创建单链表 头插法: 尾插法: 插入(增)操作  删除(删)操作: 查找(查)操作: 修改(改

    2024年02月08日
    浏览(72)
  • 算法与数据结构(二)--【1】表的概念及其四种实现方式

    目录 一.表是什么 二.用动态数组实现表 三.用链表(指针)实现表 四.用间接寻址方法实现表 【1】定义:表,又称为线性表。 线性表L是n个相同类型数据元素a(1),a(2),...,a(n)组成的有限序列。 重点:序列!简单说就是一长串的数据,与树和图区分开! 【2】相关概念: 表长:线性

    2024年02月16日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包