哈希知识详解

发布于：2024-12-18 ⋅ 阅读:(4) ⋅ 点赞:(0)
微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

目录

一、哈希

二、哈希函数

  1、直接定值法

  2、除留余数法

三、哈希冲突

四、哈希冲突解决

1、闭散列(开放定值法)

         闭散列代码

 2、哈希桶

          哈希桶的结构

         查找方法

        插入方法

        删除方法

         析构

        迭代器 

        完整哈希桶代码 

五、通过哈希桶封装 unordered_map 和 unordered_set

一、哈希

以前，在面对海量数据的查找时，最快就是红黑树 logN，无法满足需求。

于是探索出了另一种用关键字 key 值与其存储位置建立映射的思想，让查找效率提升到 O(1) ，这个就是哈希。

二、哈希函数

  1、直接定值法

        ①、直接定值法：用当前的值与数组建立一一对应的关系。

        例如，a,b,c,d 在数组 v 上的映射为 v[0],v[1],v[2],v[3]

        ②、直接定值法的缺点：如果给的值直接跨度较大就非常消耗空间。

        例如：1,1000 在数组 v 上的映射为 v[1] v[1000] 。为了存两个数开了1000多空间，十分浪费。

  2、除留余数法

        除留余数法就是：映射位置为 key 值模上空间大小。( i = key % 空间大小 )

三、哈希冲突

        用上述方法可能会有哈希冲突的问题(也就是不同的 key 值 映射到了同一个地方)

        如：除留余数法，空间大小为7,key值 1 和 8 会映射在同一个地方(1%7 = 8%7 = 1)

四、哈希冲突解决

1、闭散列(开放定值法)

        假设空间大小为 N

        线性探测：假设用除留余数法，i = key % N，如果找到的当前位置有值了，那就向后找，直到找到空位置，放进去。

        查找：执行 i = (i + 1) % N，不断向后查找(后面找完了，就从第一个位置开始继续找)，直到找到空位置。

        可以看到，哈希冲突越多，我们查找的效率越低。因此，我们可以想办法让数据的个数和空间大小维持在一个比例，降低哈希冲突。也就是维持 负载因子 / 载荷因子 的大小

        (负载因子 / 载荷因子 = 数据个数 / 空间大小 )。

        闭散列(开放定值法) 一般将这个比例维持在 0.7 左右。

        删除：如上图，如果我们删除 8，那么查找 16 的时候就找到空位置 2，无法找到 16。因此，我们删除不能只是简单的将值删除，还应该将表的每个位置增设标志位。

 

         闭散列代码

        插入：

        1、判断当前 负载因子 / 载荷因子 是否超过 0.7，如果超过，就扩容。

        2、因为扩容后的空间大小变化了，因此，所有的数据需要重新插入，我们可以定义一个临时对象 HashTable temp，把当前所有数据插入 temp 中，再将 temp 中的数据换出来，完成重新插入。

        3、根据新的空间大小和 key 值，找到映射位置。如果当前位置有值，就向后查找空闲位置(标志位不为 EXIST)，找到就插入

        查找：

        1、先判断当前 key 值的映射位置 keyi 是否正确，如果不对，继续向后查找

        2、 如果查找到了，返回下标；如果没找到，找了一圈回到 keyi ，则返回 -1

        删除：

        1、通过 key 用 Find 找到 keyi，如果不存在，就返回

        2、如果存在，则将标志位设为 DELETE 并 --_size  

// 定义的状态
enum Status
{
	EMPTY,
	EXIST,
	DELETE
};

// 哈希表中的数据
template<class K, class V>
struct HashData
{
	typedef HashData<K, V> self;
public:
	HashData()
		:_status(EMPTY)
	{}

	/*HashData(const std::pair<K, V>& value)
	{
		_data = value;
		_status = EXIST;
	}

	self& operator=(const self& val)
	{
		_data = val._data;
		_status = val._status;

		return *this;
	}*/
public:
	std::pair<K, V> _data; // 数据
	Status _status; // 状态
};


template<class K, class V>
class HashTable
{
public:
	static const double rate;
public:
	HashTable(int n = 0)
	{
		_table.resize(n);
	}

	void Insert(const std::pair<K, V>& value)
	{
		// 空间大小
		int n = _table.size();

		// 如果比例超过 rate 就扩容
		if (_size >= rate * n)
		{
			// 扩容为原来的 2 倍 (哈希表的大小最好为素数，这里就简化一下)
			int newcapacity = n == 0 ? 4 : 2 * n;

			// 因为扩容后空间大小变了，因此每个数据的映射位置也会变化，所以要重新插入
			// 定义一个临时的哈希表
			HashTable<K, V> temp(newcapacity);
			// 把原来的数据重新插入新表中
			for (auto e : _table)
			{
				if(e._status == EXIST)
					temp.Insert(e._data);
			}

			// 将新表换出来
			_table.swap(temp._table);
			_size = temp._size;
			n = newcapacity;
		}
		// 通过除留余数法 找到对应下标
		int keyi = value.first % n;

		// 找到第一个标记位不为 EXIST 的位置，放入
		while (_table[keyi]._status == EXIST)
		{
			keyi = (keyi + 1) % n;
		}
		_table[keyi]._data = value;
		_table[keyi]._status = EXIST;
		_size++;
	}
	
    // 找到了就返回下标，没找到返回 -1
	int Find(const K& key)
	{
		int n = _table.size();
		// 通过除留余数法 找到对应下标
		int keyi = key % n;
		if (_table[keyi]._data.first == key)
		{
			return keyi;
		}

		// 从第 2 个位置继续查找
		int pos = (keyi + 1) % n;
		while (_table[pos]._status != EMPTY)
		{
			// 转一圈回来了，全是 DELETE 和 EXIST
			if (pos == keyi)
				break;
			if (_table[pos]._data.first == key)
			{
				return pos;
			}
			pos = (pos + 1) % n;
		}

		return -1;
	}

	void Erase(const K& key)
	{
		int n = _table.size();
		// 如果没找到，就直接返回
		int pos = Find(key);
		if (pos == -1) return;

		// size-- 并设置标志位
		_table[pos]._status = DELETE;
		_size--;
	}

private:
	std::vector<HashData<K, V>> _table; // 哈希表
	int _size; // 当前负载
};
template<class K, class V>
const double HashTable<K, V>::rate = 0.7; // 比例为 0.7

 2、哈希桶

        与闭散列不同，哈希桶(也叫做拉链法) 是在对应位置放单链表，当有哈希冲突的时候，就把值尾插挂在对应位置的单链表下。

        优化：当一个位置的单链表的节点个数超过 8 个时，可以考虑挂红黑树。

          哈希桶的结构

// 哈希表下挂的 单链表的节点
template<class T>
struct HashNode
{
	HashNode()
	{}

	HashNode(const T& val)
		:_val(val)
	{}

	HashNode<T>* _next = nullptr; // next 指针，指向下一个位置
	T _val = T(); // 值
};

// K 表示 key(关键字) 的类型
// T 表示 值 的类型
// KOFT 表示通过 T 找到对应的 key 的仿函数(封装map和set就可以一起使用了)
// map 的值是 pair<K, T>，set 的值和 key 一样，因此，通过传入仿函数就可以让它们一起使用
// HASH 表示哈希函数，如，string 就需要通过哈希函数转化才能求位置
template<class K, class T, class KOFT, class HASH>
class HashBucket
{
    // typedef
	using node = HashNode<T>;
    // 设置 负载因子 / 载荷因子 的比例
	static const double rate;// 静态成员变量，类内定义，类外初始化
		
public:
	HashBucket(int n = 0)
	{
        // 将数组的大小开为 n
		_table.resize(n, nullptr);
	}

private:
	std::vector<node*> _table;// 哈希表，每个位置存一个单链表
	size_t _size;// 数据个数
};
template<class K, class T, class KOFT, class HASH>
const double HashBucket<K, T, KOFT, HASH>::rate = 0.7;// 初始化比例

         查找方法

        1、先判断哈希表是否为空

        2、通过哈希函数得到值，用除留余数法得到对应的下标

        3、通过下标找到单链表 _table[keyi] ，在这个单链表中遍历查找即可

iterator Find(const K& key)
{
    // 如果表是空的，那么不需要查找
	if (_table.size() == 0)
		return end();

	// 通过哈希函数，除留余数法 得到对应下标 keyi
	HASH hashfunc;
	int keyi = hashfunc(key) % _table.size();

	KOFT kot;

	// 从单链表中查找值
	node* head = _table[keyi];
	while (head)
	{
		// 找到返回
		if (kot(head->_val) == key)
		{
			return iterator(head, this);
		}
		head = head->_next;
	}
	// 没找到返回 end()
	return end();
}

        插入方法

        1、先判断 key 值是否已经存在，存在就不插入了

        2、如果 负载因子 / 载荷因子 的比例超过 定义的 rate，扩容

                扩容思想和上面的闭散列类似，因为哈希桶的大小发生变化，要重新插入原有值。我们可以先定义一个临时的大小为 newcapacity 的哈希桶，再将原本的数据插入新的临时哈希桶中，只要把临时桶的资源换出来，就完成了重新插入。

        3、通过哈希函数和 key 找到对应下标，通过下标找到该插入的单链表

        4、创建新节点，头插到单链表中，将 _size++ 完成插入 

// 设计前面的 iterator 可以帮助 运算符[], 拿到迭代器
std::pair<iterator, bool> Insert(const T& val)
{
	// 拿到 key 值
	KOFT kot;
	const K& key = kot(val);

	// 通过Find判断是否存在对应的 key
	iterator it = Find(key);
	if (it != end())
		return std::make_pair(it, false);

	int n = _table.size();
	if (_size >= n * rate)
	{
		// 如果 size 为空，设置初始容量为 4，否则新容量为原来的 2 倍
		int newcapacity = _size == 0 ? 4 : 2 * n;

		// 设置临时对象
		HashBucket temp(newcapacity);
		for (node* head : _table)
		{
			// 因为容量发生变化，所以所有数据的映射位置发生变化
			// 将所有数据重新插入 temp
			while (head)
			{
				temp.Insert(head->_val);
				head = head->_next;
			}
		}

		// 将 temp 中的资源换出来
		_table.swap(temp._table);
		_size = temp._size;
		n = newcapacity;
	}
			
	// 得到对应下标 keyi
	HASH hashfunc;
	int keyi = hashfunc(key) % n;

	// 创建新节点
	node* newnode = new node(val);

	// 头插
	newnode->_next = _table[keyi];
	_table[keyi] = newnode;

	// ++size
	++_size;

	return std::make_pair(iterator(newnode, this), true);
}

        删除方法

        1、和插入一样，先进行查找，如果没找到 key，就直接返回

        2、通过 key 和哈希函数得到对应的下标，找到对应单链表

        3、问题转化为在单链表中查找节点，找到返回即可

bool Erase(const K& key)
{
	// 先进行查找，没找到直接返回
	iterator iter = Find(key);
	if (iter == end())
		return false;

	// 通过 key 得到下标
	HASH hashfunc;
	int keyi = hashfunc(key) % _table.size();

	KOFT kot;

	node* prev = nullptr;
	node* cur = _table[keyi];
	while (cur)
	{
		if (kot(cur->_val) == key)
		{
			if (prev == nullptr)
				_table[keyi] = cur->_next;
			else
				prev->_next = cur->_next;
					
			delete cur;
			break;
		}
		prev = cur;
		cur = cur->_next;
	}
	return true;
}

         析构

        遍历哈希表，将所有单链表释放。 

~HashBucket()
{
	// 释放所有单链表的节点
	for (node* head : _table)
	{
		while (head)
		{
			node* next = head->_next;
			delete head;
			head = next;
		}
	}
}

        迭代器 

        1、迭代器基本结构 

        哈希桶的迭代器需要节点，因为进行++操作时，需要查找表的下一个非空节点，因此还需要这个哈希桶的指针。

         哈希桶的 operator== 和  operator!= 判断节点的地址是否相同即可

        解引用*和->，* 返回值引用，-> 返回值的地址

        注意：因为通过哈希表指针使用了私有成员 _table ，因此要把迭代器设为友元，或设置 GetTable() 函数返回。

// 声明
template<class K, class T, class KOFT, class HASH>
class HashBucket;

template<class K, class T, class KOFT, class HASH>
class __HashIterator
{
public:
	typedef HashNode<T> node;
	typedef HashBucket<K, T, KOFT, HASH> HT;
	typedef __HashIterator<K, T, KOFT, HASH> self;

	__HashIterator(node* node, HT* ht)
		:_node(node)
		,_ht(ht)
	{}

	bool operator!=(const self& iter)
	{
		return _node != iter._node;
	}
	bool operator==(const self& iter)
	{
		return _node == iter._node;
	}
	T& operator*()
	{
		return _node->_val;
	}
	T* operator->()
	{
		return &(_node->_val);
	}

	node* _node;
	HT* _ht;
};

        2、迭代器 ++

        ++iterator，前置++，返回自己

        思路：找到下一个不为空的节点，因为是++，所以不需要回到开头，后面都为空就返回。

self& operator++()
{
	// 如果 _node 为空，说明在 end() 位置，直接返回
	if (_node == nullptr)
		return *this;

	// 如果该节点的 next 不为空，返回它的下一个节点
	if (_node->_next)
	{
		_node = _node->_next;
		return *this;
	}

	// 如果它是该链表的最后一个节点，找下一条链表的头
	//  获取当前节点的映射位置 keyi
	KOFT kot;
	HASH hashfunc;
	const K& key = kot(_node->_val);
	int keyi = hashfunc(key) % _ht->_table.size();

	// 向后查找哈希表中不为空的链表
	while (++keyi < _ht->_table.size())
	{
		// 找到，_node 为当前链表的头，也就是 _table[keyi]
		if (_ht->_table[keyi])
		{
			_node = _ht->_table[keyi];
			break;
		}
	}
	// 没找到，_node 返回空
	if (keyi == _ht->_table.size())
		_node = nullptr;
	return *this;
}

        完整哈希桶代码 

namespace bucket
{
	// 哈希表下挂的 单链表的节点
	template<class T>
	struct HashNode
	{
		HashNode()
		{}

		HashNode(const T& val)
			:_val(val)
		{}

		HashNode<T>* _next = nullptr;
		T _val = T();
	};
	// 声明
	template<class K, class T, class KOFT, class HASH>
	class HashBucket;

	template<class K, class T, class KOFT, class HASH>
	class __HashIterator
	{
	public:
		typedef HashNode<T> node;
		typedef HashBucket<K, T, KOFT, HASH> HT;
		typedef __HashIterator<K, T, KOFT, HASH> self;

		__HashIterator(node* node, HT* ht)
			:_node(node)
			,_ht(ht)
		{}

		bool operator!=(const self& iter)
		{
			return _node != iter._node;
		}
		bool operator==(const self& iter)
		{
			return _node == iter._node;
		}
		T& operator*()
		{
			return _node->_val;
		}
		T* operator->()
		{
			return &(_node->_val);
		}

		self& operator++()
		{
			// 如果 _node 为空，说明在 end() 位置，直接返回
			if (_node == nullptr)
				return *this;

			// 如果该节点的 next 不为空，返回它的下一个节点
			if (_node->_next)
			{
				_node = _node->_next;
				return *this;
			}

			// 如果它是该链表的最后一个节点，找下一条链表的头
			//  获取当前节点的映射位置 keyi
			KOFT kot;
			HASH hashfunc;
			const K& key = kot(_node->_val);
			int keyi = hashfunc(key) % _ht->_table.size();

			// 向后查找哈希表中不为空的链表
			while (++keyi < _ht->_table.size())
			{
				// 找到，_node 为当前链表的头，也就是 _table[keyi]
				if (_ht->_table[keyi])
				{
					_node = _ht->_table[keyi];
					break;
				}
			}
			// 没找到，_node 返回空
			if (keyi == _ht->_table.size())
				_node = nullptr;
			return *this;
		}


		node* _node;
		HT* _ht;
	};

	template<class K, class T, class KOFT, class HASH>
	class HashBucket
	{
		using node = HashNode<T>;
		static const double rate;
		
	public:
		using iterator = __HashIterator<K, T, KOFT, HASH>;
		friend iterator;

		HashBucket(int n = 0)
		{
			_table.resize(n, nullptr);
		}

		// 设计前面的 iterator 可以帮助 运算符[], 拿到迭代器
		std::pair<iterator, bool> Insert(const T& val)
		{
			// 拿到 key 值
			KOFT kot;
			const K& key = kot(val);

			// 通过Find判断是否存在对应的 key
			iterator it = Find(key);
			if (it != end())
				return std::make_pair(it, false);

			int n = _table.size();
			if (_size >= n * rate)
			{
				// 如果 size 为空，设置初始容量为 4，否则新容量为原来的 2 倍
				int newcapacity = _size == 0 ? 4 : 2 * n;

				// 设置临时对象
				HashBucket temp(newcapacity);
				for (node* head : _table)
				{
					// 因为容量发生变化，所以所有数据的映射位置发生变化
					// 将所有数据重新插入 temp
					while (head)
					{
						temp.Insert(head->_val);
						head = head->_next;
					}
				}

				// 将 temp 中的资源换出来
				_table.swap(temp._table);
				_size = temp._size;
				n = newcapacity;
			}
			
			// 得到对应下标 keyi
			HASH hashfunc;
			int keyi = hashfunc(key) % n;

			// 创建新节点
			node* newnode = new node(val);

			// 头插
			newnode->_next = _table[keyi];
			_table[keyi] = newnode;

			// ++size
			++_size;

			return std::make_pair(iterator(newnode, this), true);
		}

		iterator begin()
		{
			// 找到第一个非空单链表的头
			for (auto head : _table)
			{
				if (head)
					return iterator(head, this);
			}

			return iterator(nullptr, this);
		}

		iterator end()
		{
			// 为空代表走到了结尾
			return iterator(nullptr, this);
		}

		iterator Find(const K& key)
		{
			if (_table.size() == 0)
				return end();
			// 得到对应下标 keyi
			HASH hashfunc;
			int keyi = hashfunc(key) % _table.size();

			KOFT kot;

			// 从单链表中查找值
			node* head = _table[keyi];
			while (head)
			{
				// 找到返回
				if (kot(head->_val) == key)
				{
					return iterator(head, this);
				}
				head = head->_next;
			}
			// 没找到返回 end()
			return end();
		}

		bool Erase(const K& key)
		{
			// 先进行查找，没找到直接返回
			iterator iter = Find(key);
			if (iter == end())
				return false;

			// 通过 key 得到下标
			HASH hashfunc;
			int keyi = hashfunc(key) % _table.size();

			KOFT kot;

			node* prev = nullptr;
			node* cur = _table[keyi];
			while (cur)
			{
				if (kot(cur->_val) == key)
				{
					if (prev == nullptr)
						_table[keyi] = cur->_next;
					else
						prev->_next = cur->_next;
					
					delete cur;
					break;
				}
				prev = cur;
				cur = cur->_next;
			}
			return true;
		}

		~HashBucket()
		{
			// 释放所有单链表的节点
			for (node* head : _table)
			{
				while (head)
				{
					node* next = head->_next;
					delete head;
					head = next;
				}
			}
		}

	private:
		std::vector<node*> _table;
		size_t _size;
	};

	template<class K, class T, class KOFT, class HASH>
	const double HashBucket<K, T, KOFT, HASH>::rate = 0.7;
}

五、通过哈希桶封装 unordered_map 和 unordered_set

        1、封装 unordered_set

        

// 设置哈希函数
template<class K>
class HashFunc
{
public:
	int operator()(const K& val)
	{
		return val;
	}
};
// 特化，string
template<>
int HashFunc<std::string>::operator()(const std::string& str)
{
	int key = 0;
	for (char ch : str)
	{
		key += ch;
	}

	return key;
}

// 通过 值 找 key
// 对于 unordered_set 关键字和值都是 key
template<class K>
class KOfT
{
public:
	const K& operator()(const K& key)
	{
		return key;
	}
};

// 哈希函数给了默认的，也可以外面传
// unordered_set<int> 第一个模版参数是 key
template<class K, class HASH= HashFunc<K>>
class unordered_set
{
public:
	// typedef
	using iterator = typename bucket::HashBucket<K, K, KOfT<K>, HASH>::iterator;

	// 插入、修改、查找等函数直接调用 哈希桶的接口即可
	std::pair<iterator, bool> Insert(const K& val)
	{
		return _ht.Insert(val);
	}

	bool Erase(const K& key)
	{
		return _ht.Erase(key);
	}

	iterator Find(const K& key)
	{
		return _ht.Find(key);
	}

	iterator begin()
	{
		return _ht.begin();
	}
	iterator end()
	{
		return _ht.end();
	}


private:
	// 关键字为 K, 值为 k
	bucket::HashBucket<K, K, KOfT<K>, HASH> _ht;
};

        2、封装 unordered_map

        哈希桶的 T 为值，在 unordered_set 中为 K，在 unordered_map 中为 pair<K, T> 

        unordered_map 中的 T 为第二个类型，如 unordered_map<string, int> 中，代表的是 int

// 设置的默认哈希函数
template<class K>
class HashFunc
{
public:
	int operator()(const K& val)
	{
		return val;
	}
};

// 特化
template<>
int HashFunc<std::string>::operator()(const std::string& str)
{
	int key = 0;
	for (char ch : str)
	{
		key += ch;
	}

	return key;
}

// 对于 unordered_map 关键字为 K, 值为 pair<K, T>
// 通过 KOfT 就可以实现 unordered_map 和 unordered_set 使用同一个类封装
template<class K, class T>
class KOfT
{
public:
	const K& operator()(const T& val)
	{
		return val.first;
	}
};

// unordered_map<string, int>
// K 为key，类型为string 
// T 类型为int
template<class K, class T, class HASH = HashFunc<K>>
class unordered_map
{
public:
	using iterator = typename bucket::HashBucket<K, std::pair<K, T>, KOfT<K, std::pair<K, T>>, HASH>::iterator;

	std::pair<iterator, bool> Insert(const std::pair<K, T>& val)
	{
		return _ht.Insert(val);
	}

	bool Erase(const K& key)
	{
		return _ht.Erase(key);
	}

	iterator Find(const K& key)
	{
		return _ht.Find(key);
	}

	T& operator[](const K& key)
	{
		// 运算符[] 就是如果存在，返回值引用；如果不存在，插入{key, 0}，并返回值引用
		// 因此，我们只要插入{key, 0} 即可
		std::pair<iterator, bool> ret = Insert(std::make_pair(key, 0));

		return ret.first->second;
	}

	iterator begin()
	{
		return _ht.begin();
	}
	iterator end()
	{
		return _ht.end();
	}
private:
	// 调用哈希桶时，key 为 K，值为pair<K, T>
	bucket::HashBucket<K, std::pair<K, T>, KOfT<K, std::pair<K, T>>, HASH> _ht;
};

        感谢观看♪(･ω･)ﾉ

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布