[数据结构与算法] 哈希表的实现

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 哈希表的实现 -> 正文阅读

[数据结构与算法]哈希表的实现

哈希表的实现

本篇文章来介绍一下哈希表，哈希表也称散列表，其关键就是将插入的元素通过哈希函数是的元素的存储位置和它的关键码能够建立一一映射的关系，那么在查找某个元素的时候就可以直接通过该元素的关键码去找，查找速度非常快。

文章目录

- 整体代码

与平衡树的对比

平衡树中是通过元素的key来分配位置的，对于任何一个结点，当其左右孩子存在的时候，其左孩子对应的key,是小于自身key的，其右孩子的key是大于自身的key的。简而言之就是平衡树的构造规则是key小的往左边走，key大的往右边走。（key指的是插入元素的某种属性，插入的时候根据比较元素的key来决定该元素是插入到左边还是右边，比较方式可以自定义）。

平衡树的结构就使得其查找的复杂度是0(logN),也就是最坏的情况下需要找高度次才找的到。

但是哈希表就不同了，每个元素都右对应的关键码，只需要通过哈希函数算出对应元素的关键码，再按照关键码去找就可以快速的找到，时间复杂度是0（1），相比树型结构的查找就显得非常有优势了。

哈希表里需要将每个元素通过哈希函数创建出一个关键码，通过关键码来映射对应的位置。那么这里就需要对不同的类型设置不同的哈希函数了。

为哈希表设置哈希函数

template<class K>
	struct DefaultFunc//默认的哈希函数 
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
//模板特化
	template<>//字符串的哈希函数
	struct DefaultFunc<string>
	{
		size_t operator()(const string& str)
		{
			int ret = 0;
			for (auto& e : str)
			{
				ret = ret * 131 + e;
			}
			return ret;
		}
	};

创建结点存储数据

template<class T>
	struct HashNode
	{
		HashNode(const T& t)
			:_data(t)
			, next(nullptr)
		{

		}
		T _data;//数据
		HashNode* next;//下一个结点的指针
	};

总体结构


	template<class K, class T, class GetKeyofT, class HashFunc = DefaultFunc<K>>
	class HashTable
	{
        //迭代器中会用到哈希表并且访问器成员变量所以需要将迭代器类设置为哈希表的友元类
		template<class K, class T, class GetKeyofT, class HashFunc>
		friend class __Hash_iterator;

	public:
        //类型重定义 简化代码
		typedef __Hash_iterator<K, T, GetKeyofT, HashFunc> hash_iterator;
		typedef HashNode<T> Node;
        //创建两个对象 hf里是对应的K类型的哈希函数  
        //Koft是用来获取T中的key的，为后面封装unordered_set unordered_map做准备
        //因为后期封装这两个的时候T的类型不同 对于unrodered_set T和K类型相同 
        //对于unordered_map而言 T是一个由 K 和 V 构成的键值对pair<K,V>
        //因为对于不同的封装，T的类型不同 那么就需要设一个仿函数来获取T中的K 
		HashFunc hf;
		GetKeyofT Koft;
        
		//析构函数 清理结点
		~HashTable()
		{
		}
        //迭代器
		hash_iterator begin()
		{
		}

		hash_iterator end()
		{
		}
		//插入元素
		pair<hash_iterator, bool> insert(const T& kv)
		{
		}
        //判断某个元素是否在哈希表中
		hash_iterator find(const K& key)
		{
		}
		//删除某个元素
		bool erase(const K& key)
		{
		}
		//获取元素个数
		size_t size()
		{
		}
        //判断哈希表是否为空
		bool empty()
		{
		}
        //返回key所在桶中的元素个数
		size_t count(const K& key)
		{
		}
        //交换两个哈希表
		void swap(const HashTable<K, T, GetKeyofT>& hashtable)
		{
		
		}
        //清理哈希表
		void clear()
		{
		}
	private:
        //用vector来做数组，里面放结点，形成哈希表的开散列结构
		vector<Node*> _table;
        //元素个数
		size_t _size = 0;
	};

成员函数剖析

find()

find函数的原理就是通过给定的key，用哈希函数的得到其关键码从而得到其在表中对应的位置，然后去对应的位置中找是否存在该元素即可。非常的简单

	hash_iterator find(const K& key)
		{
        //如果表为空 直接返回null指针构造的迭代器（也就是end()) 
			if (_size == 0)
			{
				return hash_iterator(nullptr, this);
			}
			size_t hashi = hf(key);
			hashi %= _table.size();
			size_t starti = hashi;//映射的位置
			Node* cur = _table[starti];
			while (cur && Koft((cur->_data)) != key)
			{
				cur = cur->next;
			}
			return hash_iterator(cur, this);

		}

insert()

插入函数的实现分下面几个步骤：

1.通过GetkeyofT仿函数，得到插入数据T的key（键）
2.通过哈希函数HashFunc得到key对应的关键码，从而得到映射的位置
3.将该数据插入到vector对应的位置中

注意这里的insert的返回值类型是一个键值对，其第一个参数是一个指向插入元素的迭代器，第二个查参数是一个布尔值，表示该元素是否插入成功！返回值类型与库中一致这样设计方便了unordered_map中可以重载[ ]，实现按下标访问！！！

	pair<hash_iterator, bool> insert(const T& kv)
		{
    		//通过find函数去找对应的元素是否已经存在哈希表中    
			hash_iterator pos = find(Koft(kv));
			if (pos != end())
			{
                //存在返回对应位置迭代器和false构成的键值对
				return make_pair(pos, false);
			}
			//如果哈希表为空或者载荷因子为1 了就说明需要扩容了（分配空间）
			if (_size == 0 || _size == _table.size())
			{
                //当哈希表为空时默认初始化容量为10 其他情况两倍一扩容
				size_t newsize = _size == 0 ? 10 : _size * 2;
                //开辟新的 容量够大的 vector来存储结点
				vector<Node*> temp;
				temp.resize(newsize);//初始化容量
                //将哈希表中的结点拷贝到新开辟的vector中 并且实现结点的深拷贝！
				for (auto& e : _table)
				{
					//遍历原链表插入数据 
					Node* cur = e;
					while (cur != nullptr)
					{
						Node* childNode = new Node(cur->_data);
						int i = hf(Koft(cur->_data)) % newsize;
						childNode->next = temp[i];
						temp[i] = childNode;
						cur = cur->next;
					}


				}
                //交换原哈希表的vector和新开辟出来的具有原表中数据的vector
				temp.swap(_table);
				
			}
			
        	//先用kfot获取插入数据的key,然后用hf形成这个key的关键码
			size_t hashi = hf(Koft(kv));
        	//关键码模上哈希表的长度作为插入数据映射的位置
			hashi %= _table.size();


			size_t starti = hashi;//映射的位置

			//在对应的位置下插入数据 也就是把这个结点头插到该位置对应的链表中，像桶一样挂上去
			
        	//用数据创建对应的新结点 
        	Node* newnode = new Node(kv);
			//头插
			Node* cur = _table[hashi];
			newnode->next = _table[hashi];
			_table[hashi] = newnode;
        	//更新头
			++_size;//更新表中的元素个数
        //返回对应结点的迭代器和ture构成的键值对
			return make_pair(hash_iterator(_table[hashi], this), true);

		}

注意上面的扩容写的深拷贝其实可以优化，不需要遍历原链表去每个结点都拷贝一份然后插入到新的vector中然后交换两个vector来实现深拷贝。
优化方案：直接将原来的链表与原来的vector解耦，然后挪动到新开辟的vector上即可，乾坤大挪移！

erase()

erase函数的实现也无非时那几步，先得到关键码，找到映射位置，去对应的链表中删除元素即可（演变成了链表中删除结点）

bool erase(const K& key)
		{
    		//表为空直接返回false
			if (_table.size() == 0)
			{
				return false;
			}
    		//获取对应的关键码得到映射位置
			size_t hashi = hf(key);
			hashi %= _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;//设置前驱指针，方便删除结点后的链接工作
			while (cur)//遍历链表删除对应结点即可
			{
				Node* next = cur->next;

				cur->next = next;

				if (Koft(cur->_data) == key)
				{
					if (cur == _table[hashi])
					{
						_table[hashi] = next;
					}
					else
					{
						prev->next = next;
					}
					delete cur;
				}
				prev = cur;
				cur = next;
			}
    //更新表中的元素个数
			--_size;
			return true;
		}

析构函数

析构函数的功能就是去遍历表中的每个结点，然后将其delete。类似于链表的删除。只不过这里相当于是多个链表的删除（因为每个位置都是一些冲突的元素构造的结点构成的单链表），只需要控制好迭代即可。


	~HashTable()
	{
		for (auto& e : _table)//遍历每个映射位置
		{
			Node* cur = e;
			while (cur && cur->next)//释放每个位置上的链表
			{
				Node* next = cur->next;
				delete cur;
				cur = nullptr;
				cur = next;
			}
			e = nullptr;
		}
	}

其他的简单的成员函数

swap()

void swap(const HashTable<K, T, GetKeyofT>& hashtable)
	{
		_table.swap(hashtable._table);
	}

这里的_table是一个vector 想要交换两个vector可以调用vector的自带的成员函数swap进行交换即可

count()

size_t count(const K& key)
	{
		size_t hashi = hf(key) % _table.size();
		Node* cur = _table[hashi];
		size_t count = 0;
		while (cur)
		{
			count++;
			cur = cur->next;
		}
		return count;
	}

count()函数返回的是key对应映射位置上的冲突元素的个数，也可以将这个位置看为一个桶，相同关键码的元素就放在一个桶中，这里的count就是返回某个桶中的元素个数。

clear()

void clear()
{
	this->~HashTable();
}

直接调用析构函数即可。

empty()和size()

size_t size()
{
	return _size;
}
bool empty()
{
	return _size == 0;
}

迭代器的实现

//因为迭代器中不仅需要有一个结点，当从一个桶切换到另一个桶中的时候就需要用到哈希表，所以还得需要引入一个哈希表的指针！
//那么如果这个迭代器是在哈希表的上面定义的就需要提前声明一下哈希表这个类 因为编译器只会默认往下找，不会往上找
template<class K, class T, class KeyofT, class HashFunc >
	class HashTable;

	template<class K, class T, class KeyofT, class HashFunc >
	class __Hash_iterator
	{
        //类型重定义 简化代码
		typedef __Hash_iterator<K, T, KeyofT, HashFunc> self;
		typedef HashTable<K, T, KeyofT, HashFunc> HashTable;
		typedef typename HashNode<T> Node;
	public:
		//这里的node是一个类 那么就有this指针了 就不能将const的给非const的了 否则存在权限放大
		__Hash_iterator(Node* node, HashTable* hash)
			:_start(node)
			, _hash(hash)
		{
		}
		//* 的重载 返回结点中的数据
		T& operator*()
		{
			return _start->_data;
		}
        //-> 的重载返回结点中数据的地址
		T* operator->()
		{
			//这里是返回的*this
			return &(_start->_data);
		}
		
        //迭代器往后移动 前置加加
		self& operator++()
		{
			if (_start && _start->next)
			{
				_start = _start->next;
			}
			else
			{
				KeyofT koft;
				HashFunc hf;
				//这里是返回_data里的first再转化为key！！！
				size_t hashi = hf(koft(_start->_data));

				hashi %= _hash->_table.size();//这里要注意模一个table.size() 获取对应的映射值！！！
				++hashi;
				for (; hashi < _hash->_table.size(); hashi++)
				{
					if (_hash->_table[hashi])
					{
						_start = _hash->_table[hashi];
						break;
					}

				}
				if (hashi == _hash->_table.size())
					_start = nullptr;
			}
			return *this;
		}
        
        //后置加加
		self& operator++(int)
		{
			self tmp = *this;
			++(*this);
			return tmp;

		}
        //迭代器相等比较 
		bool operator == (const self& it)
		{
			return _start == it._start;
		}

		bool operator!=(const self& it)
		{
			return _start != it._start;
		}
	private:
        //哈希表指针
		HashTable* _hash;
		//结点指针
		Node* _start;
	};

这里的迭代器实现的原理就是封装一个结点指针，通过改变这个结点指针指向的结点来完成迭代器的迭代。但是仅仅只有一个结点指针是不够的，因为开散列的哈希表是由多个链表构成的（也可以说是多个桶构成的）当遍历完一个映射位置的链表后就需要去遍历下一条链表，这个过程就需要获取原来哈希表的存储结点的vector,也就是需要有一个哈希表指针指向原来的哈希表，来完成链表之间的转换工作！！！所以这里封装的迭代器有两个成员变量一个是结点指针一个是哈希表指针。并且需要在迭代器定义的前面先声明一下哈希表，并且需要将这个迭代器类设置为哈希表的友元，因为迭代器需要访问哈希表的成员！！！

整体代码

#pragma once 
#include<iostream>
#include<vector>
#include<string>
using std::make_pair;
using std::pair;
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;



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

	template<>
	struct DefaultFunc<string>
	{
		size_t operator()(const string& str)
		{
			int ret = 0;
			for (auto& e : str)
			{
				ret = ret * 131 + e;
			}
			return ret;
		}
	};

namespace zh
{
	template<class T>
	struct HashNode
	{
		HashNode(const T& t)
			:_data(t)
			, next(nullptr)
		{

		}
		T _data;
		HashNode* next;
	};


	template<class K, class T, class KeyofT, class HashFunc >
	class HashTable;
	//template<class K,class T,class KeyofT,class Ref,class Ptr, class HashFunc >
	template<class K, class T, class KeyofT, class HashFunc >
	class __Hash_iterator
	{

		typedef __Hash_iterator<K, T, KeyofT, HashFunc> self;
		typedef HashTable<K, T, KeyofT, HashFunc> HashTable;
		typedef typename HashNode<T> Node;
	public:
		//这里的node是一个类 那么就有this指针了 就不能将const的给非const的了 否则存在权限放大
		__Hash_iterator(Node* node, HashTable* hash)
			:_start(node)
			, _hash(hash)
		{
		}

		T& operator*()
		{
			return _start->_data;
		}
		T* operator->()
		{
			//这里是返回的*this
			return &(_start->_data);
		}

		self& operator++()
		{
			if (_start && _start->next)
			{
				_start = _start->next;

			}
			else
			{
				KeyofT koft;
				HashFunc hf;
				//这里是返回_data里的first再转化为key！！！
				size_t hashi = hf(koft(_start->_data));

				hashi %= _hash->_table.size();//这里要注意模一个table.size() 获取对应的映射值！！！
				++hashi;
				for (; hashi < _hash->_table.size(); hashi++)
				{
					if (_hash->_table[hashi])
					{
						_start = _hash->_table[hashi];
						break;
					}

				}
				if (hashi == _hash->_table.size())
					_start = nullptr;
			}
			return *this;
		}
		self& operator++(int)
		{
			self tmp = *this;
			++(*this);
			return tmp;

		}
		bool operator == (const self& it)
		{
			return _start == it._start;
		}

		bool operator!=(const self& it)
		{
			return _start != it._start;
		}
	private:
		HashTable* _hash;

		Node* _start;
	};


	template<class K, class T, class GetKeyofT, class HashFunc = DefaultFunc<K>>
	class HashTable
	{
		template<class K, class T, class GetKeyofT, class HashFunc>
		friend class __Hash_iterator;


	public:
		typedef __Hash_iterator<K, T, GetKeyofT, HashFunc> hash_iterator;
		typedef HashNode<T> Node;
		HashFunc hf;
		GetKeyofT Koft;

		~HashTable()
		{
			for (auto& e : _table)
			{
				Node* cur = e;
				while (cur && cur->next)
				{
					Node* next = cur->next;
					delete cur;
					cur = nullptr;
					cur = next;
				}
				e = nullptr;
			}
		}
		hash_iterator begin()
		{
			for (int i = 0; i < _table.size(); i++)
			{
				if (_table[i])
				{
					return hash_iterator(_table[i], this);
				}
			}
			return end();
		}

		hash_iterator end()
		{
			return hash_iterator(nullptr, this);
		}

		pair<hash_iterator, bool> insert(const T& kv)
		{
			hash_iterator pos = find(Koft(kv));
			if (pos != end())
			{
				return make_pair(pos, false);
			}

			if (_size == 0 || _size == _table.size())
			{
				size_t newsize = _size == 0 ? 10 : _size * 2;
				vector<Node*> temp;
				temp.resize(newsize);
				for (auto& e : _table)
				{
					//遍历原链表插入数据 
					Node* cur = e;
					while (cur != nullptr)
					{
						Node* childNode = new Node(cur->_data);
						int i = hf(Koft(cur->_data)) % newsize;
						childNode->next = temp[i];
						temp[i] = childNode;
						cur = cur->next;
					}


				}
				temp.swap(_table);
				//_size = newsize;
			}

			size_t hashi = hf(Koft(kv));
			hashi %= _table.size();


			size_t starti = hashi;//映射的位置

			//在对应的位置下插入数据 也就是把这个结点挂到这个链表下
			Node* newnode = new Node(kv);

			Node* cur = _table[hashi];
			newnode->next = _table[hashi];
			_table[hashi] = newnode;
			++_size;
			return make_pair(hash_iterator(_table[hashi], this), true);



		}
		hash_iterator find(const K& key)
		{
			if (_size == 0)
			{
				return hash_iterator(nullptr, this);
			}
			size_t hashi = hf(key);
			hashi %= _table.size();
			size_t starti = hashi;//映射的位置
			Node* cur = _table[starti];
			while (cur && Koft((cur->_data)) != key)
			{
				cur = cur->next;
			}
			return hash_iterator(cur, this);

		}

		bool erase(const K& key)
		{
			if (_table.size() == 0)
			{
				return false;
			}
			size_t hashi = hf(key);
			hashi %= _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				Node* next = cur->next;

				cur->next = next;

				if (Koft(cur->_data) == key)
				{

					if (cur == _table[hashi])
					{
						_table[hashi] = next;

					}
					else
					{
						prev->next = next;



					}
					delete cur;

				}
				prev = cur;
				cur = next;
			}
			--_size;
			return true;

		}

		size_t size()
		{
			return _size;
		}
		bool empty()
		{
			return _size == 0;
		}
		size_t count(const K& key)
		{
			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			size_t count = 0;
			while (cur)
			{
				count++;
				cur = cur->next;
			}
			return count;
		}
		void swap(const HashTable<K, T, GetKeyofT>& hashtable)
		{
			_table.swap(hashtable._table);
		}
		void clear()
		{
			this->~HashTable();
		}
	private:
		vector<Node*> _table;
		size_t _size = 0;
	};

}