C++——哈希表详解

2401_87358782

1279人浏览 · 2025-05-09 20:08:55

2401_87358782 · 2025-05-09 20:08:55 发布

一.概念

哈希表就是为了解决查找必须遍历的问题而生

一般哈希表有两种形式

二.特点

1.线性探测表

1.1取余法

a.原理

index = key % capacity;

index:存放数据的位置下标
key:存放数据的key值
capacity:存放数据的空间大小

通过元素的关键码(key)与元素储存位置(index)建立一一映射的函数叫哈希函数

b.举例

现在有6个数据：2，18，22，23

2%10 = 2，所以2存放在下标为2的位置

18%10 = 8，所以18存放在下标为8的位置

22%10 = 2，所以22存放在下标为2的位置

但是，现在下标为2的位置已经有了一个值，这就是哈希冲突

（不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞）

这个位置冲突了，怎么办？那就放到后面没有冲突的位置。

下标为3的位置没有冲突，所以，放到3

23%10 = 3，所以23存放在下标为3的位置

但是，下标为3的位置已经有数据了。即所谓哈希冲突了。

很简单，往后挪，挪到没有冲突的位置。

所以，往后下标4的位置没有数据，所以23存在下标为4的位置

那么，如何取出数据呢？

取18，将18%10=8，然后到下标为8的位置取即可。

但是，22%10=2，但是22却不在下标为2的位置。往后找。

23呢？也不在下标为3的位置。还是往后找。

如果当前位置找不到值，就往后挨个查找，直到找到数据；遇到无数据存放的位置也停止查找。

往后找，就像是探测，而且是一个一个探测，是线性的查找。

这就是线性探测

所以，我们把这个表，就叫做线性探测表

1.2负载因子

随着数据的增多，冲突的概率增加，查找的成本越来越高。访问一个数据，老是要往后遍历，效率低。总的来说，问题源于数据太多，而空间不够。

这时候需要扩容。

用负载因子判断什么时候扩容

负载因子就是数据个数所占整个空间的比率

(eg.10个空间，有2个数据，负载因子就是0.2)

而一般来说，负载因子达到0.7就要进行扩容。

2.哈希桶

2.1意义

线性探测形式的哈希表有着致命的弱点：无法对余数相同的数据进行处理

冲突了，只有往后放。即我的位置冲突了，我就去放别人的位置，让别人冲突

2.2结构

哈希桶将冲突的值，放到同一个位置下，用单链表管理起来

极大的优化了线性探测表无法处理哈希冲突的缺点

同时，单链表的访问，其时间复杂度也控制在O(n)的量级

2.3扩容

哈希桶也存在负载因子的问题，和线性探测负载因子是一样的逻辑

同样，也是大于0.7就进行扩容

3.闭散列与开散列

3.1闭散列

闭散列：开放定址法（线性探测/二次探测）

二次检测：当数据比较集中的时候，查找会比较慢

补充：为了更快的查找，下一个位置查找偏移量不为1，可以为2次方

思路：我的位置被别人占了，我就去占别人得位置

特点：冲突越多，效率越低

因此，有人提出了开散列

3.2开散列

开散列：哈希桶/拉链法

4.减少哈希冲突的方法

哈希表的大小为素数，可以减少哈希冲突

以下为相差大约2倍的素数
static const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul,
25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul,
805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};

三.设计hash表

1.闭散列的设计

1.0增容

a.直接增容

建新的数组=>拷贝=>释放旧空间

//增容法一
//1.建新的数组
vector<HashData<T>> newtables;
size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
newtables.resize(newsize);
//2.拷贝
for (size_t i = 0; i < _tables.size(); ++i)
{
				if (_tables[i]._state == EXIST)
				{
					size_t index = koft(_tables[i]._data) % newsize;
					while (newtables[index]._state == EXIST)
					{
						index++;
						if (index == newtables.size())
						{
							index = 0;
						}
					}
					newtables[index] = _tables[i];
				
				}
				
}
//3.释放旧空间
_tables.swap(newtables);

b.交换法

建新的哈希表=>复用Insert的单个插入的代码=>交换哈希表中的容器指针

//增容法二
//建新的哈希表
HashTable<K, T, KOfT> newht;
size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
newht._tables.resize(newsize);
for (size_t i = 0; i < _tables.size(); i++)
{
				if (_tables[i]._state == EXIST)
				{
                    //复用插入代码
					newht.Insert(_tables[i]._data);
				}
}
_tables.swap(newht._tables);

1.1插入

思路:

如果位置不被占，插入；如果位置被占，遇到空才插入

插入逻辑：

记录Hash表中数据的数量，插入前计算负载因子，若大于0.7就先增容

通过哈希函数找到映射位置，按照规则进行插入

1.2查找

遇到空位置才停止，但是如果中间位置因为删除存在有空位置，就查不到后面的位置，如何解决？

设置一个位置状态：EMPTY(空)、DELETE(删除)，EXIST(存在)

a.修改后的插入：

若映射位置状态为EMPTY或DELETE，直接插入
若映射位置状态为EXIST，向后探测，在状态为EMPTY或DELETE的位置上插入
（若探测到最后一个位置，就重新从第一个位置开始重新探测）

注：若遇到状态为EXIST且值相同的位置，则插入失败

b.修改后的查找：

从映射位置开始，向后查找，直到状态为EMPTY的位置停止

（若探测到最后一个位置，就重新从第一个位置开始重新探测）

若找到相同的值，检查其状态：
若状态为DELETE，则查找失败
若状态为EXIST，则查找成功，返回当前位置节点的指针

1.3删除

删除的值不必抹除，而是将状态设置为DELETE

（如果抹除，设置为什么值都不合适）

因此，删除是一个惰性删除，查找值时依旧能找到

1.4代码

//设置状态
enum State
{
	EMPTY,
	EXIST,
	DELETE
};

//设置节点内容
template<class T>
struct HashData
{
	T _data;
	State _state;
};

//设置仿函数，方便取出元素的关键码key
template<class K>
struct KeyOfSet
{
	const K& operator()(const K& k)
	{
		return k;
	}
};

//unordered_set<K,K> -> HashTable<K,K,KOfSet>
//unordered_map<K,pair<K,V>> -> HashTable<K,pair<K,V>,KOfMap>
template<class K, class T, class KOfT>
class HashTable
{
public:
	bool Insert(const T& data)
	{
        //仿函数实例化
		KOfT koft;
		//负载因子=表中数据量/表的大小 衡量哈希表满的程度
		//表越满，插入数据越容易冲突，效率越低
		//负载因子达到0.7左右就开始增容
		if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7)
		{
            //增容法一
            //1.建新的数组
            vector<HashData<T>> newtables;
            size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
            newtables.resize(newsize);
            //2.拷贝
            for (size_t i = 0; i < _tables.size(); ++i)
            {
				if (_tables[i]._state == EXIST)
				{
					size_t index = koft(_tables[i]._data) % newsize;
					while (newtables[index]._state == EXIST)
					{
						index++;
						if (index == newtables.size())
						{
							index = 0;
						}
					}
					newtables[index] = _tables[i];
				
				}
				
            }
            //3.释放旧空间
             _tables.swap(newtables);

			//增容法二
			//建新的哈希表
			HashTable<K, T, KOfT> newht;
			size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
			newht._tables.resize(newsize);
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i]._state == EXIST)
				{
                    //复用Insert的单个插入的代码
					newht.Insert(_tables[i]._data);
				}
			}
			_tables.swap(newht._tables);
		}

		//计算data在表中映射的位置
		size_t index = koft(data) % _tables.size();
		while (_tables[index]._state == EXIST)
		{
			if (koft(_tables[index]._data) == koft(data))
			{
				return false;
			}
			index++;
			if (index == _tables.size())
			{
				index = 0;
			}
		}
        //插入
		_tables[index]._data = data;
		_tables[index]._state = EXIST;
		_num++;
		return true;
	}

    //查找
	T* Find(const K& key)
	{
		KOfT koft;
		//计算key在表中映射的位置
		size_t index = key % _tables.size();
		while (_tables[index]._state != EMPTY)
		{
			if (koft(_tables[index]._data) == key)
			{
				if (_tables[index]._state == EXIST)
				{
					return &_tables[index]._data;
				}
				else if (_tables[index]._state == DELETE)
				{
					return nullptr;
				}
			}

			index++;
			if (index == _tables.size())
			{
				index = 0;
			}
		}
		return nullptr;
	}

    //删除
	bool Erase(const K& key)
	{
		HashData* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			_num--;
			return true;
		}
		else
		{
			return false;
		}

	}
private:
	vector<HashData<T>> _tables;
	size_t _num = 0;//存储的有效数据的数量
};

2.开散列的设计

2.1结构

表中存放单链表指针

若数据太多也可存放红黑树的根节点

2.2功能

插入：判断是否需要增容，链表头插
查找：遍历链表
删除：删除链表中的节点
清理：删除链表

2.3哈希函数

a.仿函数

哈希函数是将元素的关键码(key)与元素储存位置(index)建立一一映射关系的仿函数

（通过重载operator()，达到像函数一样的效果）

一般情况下，对于整型、浮点型、指针都进行size_t强转为整型，就可以取%，找到位置

但是，对于某些特殊的类型，常见的有string不可以转化为整型

b.哈希函数(特殊的仿函数)

下面讲解将string转化成整型的常见的哈希算法（仿函数的特化），而其他不能转化成整形的类型

需要自己写出特化的仿函数

将每一个字符的ASCII值*某个数值，累计加，得到整型

其中一种算法是乘以131，研究发现不同字符串得出的数字重复较少

//哈希算法
template<class K>
struct _Hash
{
	const K& operator()(const K& k)
	{
		return k;
	}
};
//特化string类
template<>
struct _Hash<string>
{
	size_t operator()(const string& str)
	{
		//转化后的数字
		size_t hash = 0;
		//BKDR Hash
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash = hash * 131 + str[i];
		}
		return hash;
	}
};

2.4代码

//节点
template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;
    //构造函数
	HashNode(const T& data)
		:_data(data)
		,_next(nullptr)
	{}
};

//哈希算法
template<class K>
struct _Hash
{
	const K& operator()(const K& k)
	{
		return k;
	}
};
//特化string类
template<>
struct _Hash<string>
{
	size_t operator()(const string& str)
	{
		//转化后的数字
		size_t hash = 0;
		//BKDR Hash
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash = hash * 131 + str[i];
		}
		return hash;
	}
};

//哈希表
template<class K,class T,class KOfT,class Hash =_Hash<K>>
class HashTable
{
public:
	typedef HashNode<T> Node;
	//析构函数
	~HashTable()
	{
		Clear();
	}
	//清理
	void Clear()
	{
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}

	}
    
    //哈希函数
	//由于某些类型的数据不能直接取模，所以需要仿函数将它转为整形
	size_t HashFunc(const K& k)
	{
		Hash hash;
		return hash(k);
	}


	//插入数据
	bool Insert(const T& data)
	{
		KOfT koft;
		//如果负载因子大于1，则增容
		if (_tables.size() == _num)
		{
			vector<Node*> newtables;
			size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
			newtables.resize(newsize);
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				//将旧表中的节点取下，重新插入到新表中
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					//头插
					size_t index = HashFunc(koft(cur->_data)) % _tables.size();
					cur->_next = _tables[index];
					_tables[index] = cur;

					cur = next;
				}
				//防止原表中出现野指针
				_tables[i] = nullptr;
			}
			_tables.swap(newtables);
		}

		//插入
		//计算映射位置
		size_t index = HashFunc(koft(data))%_tables.size();
		//先查找是否在表中
		Node* cur = _tables[index];
		while (cur)
		{
			if (koft(cur->_data) == koft(data))
			{
				return false;
			}
			else
			{
				cur = cur->_next;
			}
		}
		//不在表中，头插到挂着的链表中
		Node* newNode = new Node(data);
		newNode->_next = _tables[index];
		_tables[index] = newNode;
		_num++;
		return true;
	}

	//查找
	Node* find(const K& key)
	{
		KOfT koft;
		size_t index = HashFunc(key) % _tables.size();
		Node* cur = _tables[index];
		while (cur)
		{
			if (koft(cur->_data) == key)
			{
				return cur;
			}
			else
			{
				cur = cur->_next;
			}
		}
		return nullptr;
	}

	//删除
	bool Erase(const K& key)
	{
		KOfT koft;
		size_t index = HashFunc(key) % _tables.size();
		Node* prev = nullptr;
		Node* cur = _tables[index];
		while (cur)
		{
			if (koft(cur->_data) == key)
			{
				if (prev == nullptr)
				{
					//表示要删的为第一个节点
					_tables[index] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}
				delete cur;
				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}
		return false;
	}

private:
	vector<Node*> _tables;
	size_t _num = 0;//记录表中的数据个数
};

四.封装map和set

1.hash表的基础功能介绍

一个哈希表要有的功能：插入、删除、遍历（迭代器）

2.对应的迭代器

2.1结构

哈希表的迭代器包含哈希表本身（方便找下一个链表），以及哈希表对应位置的节点

2.2operator++重载

先算出当前所在位置
同一链表下，当前位置的下一个位置不为空，那就直接返回
当前位置为空，要继续找后面的位置
若找不到就返回空指针

2.3代码

//节点
template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;
	HashNode(const T& data)
		:_data(data)
		,_next(nullptr)
	{}
};

//迭代器
template<class K, class T, class KOfT,class Hash>
struct __HashTableIterator
{
	typedef HashNode<T> Node;//节点
	typedef __HashTableIterator<K, T, KOfT,Hash> Self;//迭代器
	typedef  HashTable<K, T, KOfT, Hash> HT;//哈希表

	Node* _node;
	//为了找到下一个链表的起始位置而引入
	HT* _pht;

    //构造函数
	__HashTableIterator(Node* node, HT* pht)
		:_node(node)
		,_pht(pht)
	{}
    
    //重载运算符
	T& operator* ()
	{
		return _node->_data;
	}

	T* operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const Self& it)
	{
		return _node != it._node;
	}

	Self operator++()
	{
        //当前位置的下一个位置不为空
		if (_node->_next)
		{
			_node = _node->_next;
		}
        //当前位置的下一个位置为空
		else
		{
			//当前桶走完了，到下一个桶
			KOfT koft;
			//计算当前桶在映射表中的位置
			size_t index = _pht->HashFunc(koft(_node->_data)) % _pht->_tables.size();
            //下一个桶的位置
			++index;
			for (; index < _pht->_tables.size(); ++index)
			{
				Node* cur = _pht->_tables[index];
                 //找到下一个不为空的桶
				if (cur)
				{
					_node = cur;
					return *this;
				}
			}
            //未找到下一个不为空的桶，当前已经是最后一个节点
			_node = nullptr;
		}
		return *this;

	}
	
};

3.哈希表的改造

3.1迭代器的begin和end函数

iterator begin()
{
	for (size_t i = 0; i < _tables.size(); ++i)
	{
		if (_tables[i])
		{
			return iterator(_tables[i], this);
		}
	}
	//哈希表中无节点
	return end();
}

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

3.2Insert的返回值改造

bool=>pair<iterator,bool>

返回值是一个pair，第一个参数是迭代器，第二个参数是bool，判断是否添加成功

如果已经存在，返回已存在节点的迭代器，以及false

如果节点不存在，返回新插入节点的迭代器，以及true

4.map的【】方括号重载

方括号[]重载返回值为value

直接对insert进行复用，插入key，通过iterator找到pair<key,value>，返回value

5.代码

a.HashTable

//节点
template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;
	HashNode(const T& data)
		:_data(data)
		,_next(nullptr)
	{}
};


//迭代器
//编译时只会向前找，不认识HashTable,需要前置声明
template<class K, class T, class KOfT, class Hash>
class HashTable;

template<class K, class T, class KOfT,class Hash>
struct __HashTableIterator
{
	typedef HashNode<T> Node;
	typedef __HashTableIterator<K, T, KOfT,Hash> Self;
	typedef  HashTable<K, T, KOfT, Hash> HT;

	Node* _node;
	//为了找到下一个桶的起始位置而引入
	HT* _pht;

	__HashTableIterator(Node* node, HT* pht)
		:_node(node)
		,_pht(pht)
	{}

	T& operator* ()
	{
		return _node->_data;
	}

	T* operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const Self& it)
	{
		return _node != it._node;
	}

	Self operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else
		{
			//如果当前桶走完了，到下一个桶
			KOfT koft;
			//计算当前桶在映射表中的位置
			size_t index = _pht->HashFunc(koft(_node->_data)) % _pht->_tables.size();
			++index;
			for (; index < _pht->_tables.size(); ++index)
			{
				Node* cur = _pht->_tables[index];
				if (cur)
				{
					_node = cur;
					return *this;
				}
			}
			_node = nullptr;
		}
		return *this;

	}
	
};

template<class K,class T,class KOfT,class Hash =_Hash<K>>
class HashTable
{
public:
	typedef HashNode<T> Node;
	typedef __HashTableIterator<K, T, KOfT, Hash> iterator;
	//友元关系，要访问私有成员
	friend struct __HashTableIterator<K, T, KOfT, Hash>;

	iterator begin()
	{
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			if (_tables[i])
			{
				return iterator(_tables[i], this);
			}
		}
		//哈希表中无节点
		return end();
	}
	iterator end()
	{
		return iterator(nullptr,this);
	}

	//析构函数
	~HashTable()
	{
		Clear();
	}
	//清理
	void Clear()
	{
		for (size_t i = 0; i < _tables.size(); ++i)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}

	}
    
    //哈希函数
	//由于某些类型的数据不能直接取模，所以需要仿函数将它转为整形
	size_t HashFunc(const K& k)
	{
		Hash hash;
		return hash(k);
	}


	//插入
	pair<iterator, bool> Insert(const T& data)
	{
		KOfT koft;
		//如果负载因子大于1，则增容
		if (_tables.size() == _num)
		{
			vector<Node*> newtables;
			size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
			newtables.resize(newsize);
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				//将旧表中的节点取下，重新插入到新表中
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					//头插
					size_t index = HashFunc(koft(cur->_data)) % _tables.size();
					cur->_next = _tables[index];
					_tables[index] = cur;

					cur = next;
				}
				//防止原表中出现野指针
				_tables[i] = nullptr;
			}
			_tables.swap(newtables);
		
		}

		//插入数据
		//计算映射位置
		size_t index = HashFunc(koft(data))%_tables.size();
		//先查找是否在表中
		Node* cur = _tables[index];
		while (cur)
		{
			if (koft(cur->_data) == koft(data))
			{
				return make_pair(iterator(cur,this),false);
			}
			else
			{
				cur = cur->_next;
			}
		}
		//头插到挂的链表中
		Node* newNode = new Node(data);
		newNode->_next = _tables[index];
		_tables[index] = newNode;
		_num++;
		return make_pair(iterator(newNode, this), true);
	}

	//查找
	Node* find(const K& key)
	{
		KOfT koft;
		size_t index = HashFunc(key) % _tables.size();
		Node* cur = _tables[index];
		while (cur)
		{
			if (koft(cur->_data) == key)
			{
				return cur;
			}
			else
			{
				cur = cur->_next;
			}
		}
		return nullptr;
	}

	//删除
	bool Erase(const K& key)
	{
		KOfT koft;
		size_t index = HashFunc(key) % _tables.size();
		Node* prev = nullptr;
		Node* cur = _tables[index];
		while (cur)
		{
			if (koft(cur->_data) == key)
			{
				if (prev == nullptr)
				{
					//表示要删的为第一个节点
					_tables[index] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}
				delete cur;
				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}
		return false;
	}

private:
	vector<Node*> _tables;
	size_t _num = 0;//记录表中的数据个数
};

b.unordered_set

//哈希函数
//使类型可以取模
template<class K>
struct _Hash
{
	const K& operator()(const K& k)
	{
		return k;
	}
};
//特化string类
template<>
struct _Hash<string>
{
	size_t operator()(const string& str)
	{
		//转化后的数字
		size_t hash = 0;
		//BKDR Hash
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash = hash * 131 + str[i];
		}
		return hash;
	}
};

//unordered_set类
template<class K, class Hash = _Hash<K>>
class unordered_set
{
public:
	struct KOfSet
	{
		const K& operator()(const K& k)
		{
			return k;
		}
	};
	//类未实例化找不到类中的对象，需要明确是类型名
	typedef typename HashTable<K, K, KOfSet, Hash>::iterator iterator;

	iterator begin()
	{
		return _ht.begin();
	}
	iterator end()
	{
		return _ht.end();
	}
	pair<iterator, bool> insert(const K& k)
	{
		return _ht.Insert(k);
	}
private:
	HashTable<K, K, KOfSet,Hash> _ht;
};

c.unordered_map

//哈希函数
//使类型可以取模
template<class K>
struct _Hash
{
	const K& operator()(const K& k)
	{
		return k;
	}
};
//特化string类
template<>
struct _Hash<string>
{
	size_t operator()(const string& str)
	{
		//转化后的数字
		size_t hash = 0;
		//BKDR Hash
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash = hash * 131 + str[i];
		}
		return hash;
	}
};

//unodered_map类
template<class K, class V, class Hash = _Hash<K>>
class unordered_map
{
public:
	struct KOfMap
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};
	//类未实例化找不到类中的对象，需要明确是类型名
	typedef typename HashTable<K, pair<K, V>, KOfMap, Hash>::iterator iterator;

	iterator begin()
	{
		return _ht.begin();
	}
	iterator end()
	{
		return _ht.end();
	}
	pair<iterator, bool> insert(const pair<K, V>& kv)
	{
		return _ht.Insert(kv);
	}
	V& operator[](const K& k)
	{
		pair<iterator, bool> ret = _ht.Insert(make_pair(k, V()));
		return ret.first->second;
	}
private:
	HashTable<K, pair<K, V>, KOfMap, Hash> _ht;
};

五.位图

1.概念

位图就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。

通常是用来判断某个数据存不存在的

2.实现

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态

那么可以使用一个二进制比特位来代表数据是否存在的信息：

为1代表存在
为0代表不存在

存放数据实例：

使用一个整形作为一个位图(有32个比特位)，通过修改该整形的比特位，实现数据的存储

3.代码

class bitset
{
public:
    //构造函数
	bitset(size_t N)//表示存储范围为0-N的数
	{
		bits.resize(N / 32 + 1, 0);
		_num = 0;
	}
    //插入数据x
	void set(size_t x)
	{
		size_t index = x / 32;//算出映射的位置在第几个整形
		size_t pos = x % 32;//算出映射的位置在该整形的第几个位
		bits[index] |= (1 << pos);
		_num++;
	}
    //删除数据x
	void reset(size_t x)
	{
		size_t index = x / 32;//算出映射的位置在第几个整形
		size_t pos = x % 32;//算出映射的位置在该整形的第几个位
		bits[index] &= ~(1 << pos);
		_num--;
	}
    //查找x是否在其中
	bool test(size_t x)
	{
		size_t index = x / 32;//算出映射的位置在第几个整形
		size_t pos = x % 32;//算出映射的位置在该整形的第几个位
		return bits[index] & (1 << pos);
	}
private:
	vector<int> bits;
	size_t _num;//存储的数据数量
};

4.扩展

判断在或不在是两种状态，可用一个比特位表示
若有3种状态，可用两位表示
若有更多种状态，可用更多位表示，或者，直接用两个或多个位图表示

六.布隆过滤器

1.出现

哈希表存储数据，缺点：数据类型不变，直接存入，浪费空间

位图存储数据，缺点：位图一般只能处理整形，如果数据类型是字符串等，就无法处理了。

将哈希与位图结合，即布隆过滤器

2.实现

数据通过不同的哈希算法转化成不同的整型，分别存入位图的比特位中

当位图中该数据转化的整型全部存在，代表数据存在
当位图中该数据转化的整型部分存在，代表数据不存在

3.缺点

a.不支持删除

布隆过滤器不支持删除，因为不同元素转化的整形可能部分相同，比特位刚好有重叠，删除会互相影响

b.存在误判

不同元素转化的整形可能完全相同，比特位完全重叠，存在误判

例如：假设某个元素的3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但该元素是不存在的。

所以，布隆过滤器如果说某个元素不存在时，该元素一定不存在；如果该元素存在时，该元素可
能存在，因为有些哈希函数存在一定的误判。

4.代码

//3种string的哈希算法
struct HashStr1
{
	//BKDR
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash *= 131;
			hash += str[i];
		}
		return hash;
	}
};

struct HashStr2
{
	//BKDR
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		size_t magic = 63689;
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash *= magic;
			hash += str[i];
			magic *= 378551;
		}
		return hash;
	}
};

struct HashStr3
{
	//BDBMHash
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (size_t i = 0; i < str.size(); ++i)
		{
			hash *= 65599;
			hash += str[i];
		}
		return hash;
	}
};

//布隆过滤器
template<class K=string, class Hash1=HashStr1, class Hash2=HashStr2, class Hash3=HashStr3>
class bloomfilter
{
public:
	bloomfilter(size_t num)//要存的数据个数
		:_bs(5*num)
		,_N(5*num)
	{}
    //插入数据
	void set(const K& key)
	{
        //存放位置
		size_t index1 = Hash1()(key) % _N;
		size_t index2 = Hash2()(key) % _N;
		size_t index3 = Hash3()(key) % _N;
		_bs.set(index1);
		_bs.set(index2);
		_bs.set(index3);
	}
    //查找数据
	bool test(const K& key)
	{
		size_t index1 = Hash1()(key) % _N;
		if (_bs.test(index1) == false)
		{
			return false;
		}
		size_t index2 = Hash2()(key) % _N;
		if (_bs.test(index2) == false)
		{
			return false;
		}
		size_t index3 = Hash3()(key) % _N;
		if (_bs.test(index3) == false)
		{
			return false;
		}
		//这里也不是一定存在，可能有误判
		return true;
	}
private:
	bitset _bs;//位图
	size_t _N;//位图的最大存放数据
};

5.增加删除功能

a.思路

将布隆过滤器中的每个比特位扩展成一个小的计数器，而不是简单的 0 或 1 。
计数器长度一般为一个字节或两个字节，分别可以记录的次数上限为2^8和2^16
每个计数器用于记录一个或多个哈希值对应的位置。

b.实现

将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一；删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

c.缺陷

若记录的次数过多也可能会溢出，但是，如果使用更大的空间映射一个位置，消耗的空间也会变大

七.哈希的运用

1.哈希切割

a.思路

将大文件切割为可以放进内存的小文件 ：

根据哈希算法，将大文件中的数据放进不同编号的小文件，每个小文件的大小可能不同

若某一小文件中的数据过多，也可能导致文件过大，需要分成更多份

b.好处

哈希切割的好处：每份小文件都可以放进内存直接处理

c.举例

比方说有10G存放IP地址的文件，而内存只有1G

这时可以分成100份小文件，idx = HashFunc(IP) % 100，idx是几就把IP放进几号文件中

这样不一样的IP可能分进同一个小文件中，但是同一个IP一定会分进同一个小文件

为后续处理做准备

d.应用

现在有两份存放IP地址的文件，找它们的交集

将他们用同一种哈希切割后，只需分别比较相同编号的小文件

2.一致性哈希

假设有大量的数据需要放到多个服务器中

a.映射方式一

原来的映射位置：index = HashFunc(x) % number

number：服务器的数量

一个编号映射一台服务器

b.映射方式二

现在的映射位置：index = HashFunc(x) % y

y：特别大的数字（2^32......）

一段范围的编号映射一台服务器

这种映射方式的好处：增加机器时，不用重新计算映射位置，数据大量迁移，只需改变映射范围，迁移极小部分数据

乐奇 Rokid 开放社区

更多推荐

Word Embedding ：从分布式假设到神经网络语言模型

Word Embedding（词嵌入）是一种将离散的词汇符号映射到连续的低维稠密向量空间的技术。在这个向量空间中，语义相似的词在几何距离上彼此接近，从而实现了从"符号匹配"到"语义计算"的跨越。核心定义词嵌入是将单词（或多词短语）表示为固定维度的实值向量，这些向量之间的距离（例如余弦相似度）反映了单词之间的相关性，这种相关性基于单词通常出现的上下文。分布式假设（1954）↓统计共现分析（LSA/S

乐奇 Rokid 开放社区

3 分钟装好 foobox 皮肤：foobar2000 界面升级安装教程

foobox 是一个 foobar2000 的 DUI 皮肤配置，装好后默认界面就变成带亮、暗两套主题的多面板播放器。它适合已经用 foobar2000、只想换界面不想改播放习惯的 Windows 用户：皮肤只动外观，不碰播放器核心。## 先看适不适合你- 你在 Windows 10 1607 或更高版本上用 foobar2000，想要更顺眼的界面；- 你的曲库不小，想要分组管理和搜索；

乐奇 Rokid 开放社区

AI视频生成环境配置指南:ComfyUI-LTXVideo 装通 LTX-2 的避坑与调优清单

这份教程写给刚把 ComfyUI-LTXVideo 放进 custom_nodes、准备本地跑 LTX-2 模型的人:显卡档位怎么对、插件装完为什么没有节点、dev 和 distilled 版本怎么选、FP8 量化开在哪、生成慢和显存爆掉怎么调。每个环节都给了一条能核对的命令和预期输出,照着做就能自检。## 预算档位怎么选显卡:12GB、24GB、48GB 各能跑什么 🎛️把别人给的 d

乐奇 Rokid 开放社区

所有评论(0)

查看更多评论

2401_87358782

@2401_87358782

已为社区贡献1条内容

C++——哈希表详解

2401_87358782

一.概念

二.特点

1.线性探测表

1.1取余法

1.2负载因子

2.哈希桶

2.1意义

2.2结构

2.3扩容

3.闭散列与开散列

3.1闭散列

3.2开散列

4.减少哈希冲突的方法

三.设计hash表

1.闭散列的设计

1.0增容

1.1插入

1.2查找

1.3删除

1.4代码

2.开散列的设计

2.1结构

2.2功能

2.3哈希函数

2.4代码

四.封装map和set

1.hash表的基础功能介绍

2.对应的迭代器

2.1结构

2.2operator++重载

2.3代码

3.哈希表的改造

3.1迭代器的begin和end函数

3.2Insert的返回值改造

4.map的【】方括号重载

5.代码

a.HashTable

b.unordered_set

c.unordered_map

五.位图

1.概念

2.实现

3.代码

4.扩展

六.布隆过滤器

1.出现

2.实现

3.缺点

a.不支持删除

b.存在误判

4.代码

5.增加删除功能

七.哈希的运用

1.哈希切割

2.一致性哈希

所有评论(0)

温馨提示：您尚未绑定手机号

2401_87358782