哈希表的实现（开放定址法）（万字）

发布于：2025-02-11 ⋅ 阅读:(54) ⋅ 点赞:(0)

哈希概念

哈希(hash)⼜称散列，是⼀种组织数据的⽅式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进⾏快速查找。

直接定址法（最简单最高效的哈希）

当关键字的范围⽐较集中时，直接定址法就是⾮常简单⾼效的⽅法，⽐如⼀组关键字都在[0,99]之间， 那么我们开⼀个100个数的数组，每个关键字的值直接就是存储位置D的下标。再⽐如⼀组关键字值都在 [a,z]的⼩写字⺟，那么我们开⼀个26个数的数组，每个关键字acsii码-aascii码就是存储位置的下标。 也就是说直接定址法本质就是⽤关键字计算出⼀个绝对位置或者相对位置。这个⽅法在计数排序中有，其次在string的OJ也有。
在这里插入图片描述

​
class Solution {
public:
 	int firstUniqChar(string s) 
    {
         // 每个字⺟的ascii码-'a'的ascii码作为下标映射到count数组，数组中存储出现的次数 
         int count[26] = {0};
         // 统计次数 
         for(auto ch : s)
         {
             count[ch-'a']++;
         }
         for(size_t i = 0; i < s.size(); ++i)
         {
             if(count[s[i]-'a'] == 1)
             return i;
         }
         return -1;
     }
};

​

映射0，b就映射1…… 这个数组里面存的就是次数

但是直接定址法也有一些问题，这只适合关键字的数据范围比较集中的整型（因为要直接算在数组中的下标）。

像浮点数、string这些就不行。这个方法有局限性

所以在实践中比较特别的场景其实才能用。

哈希冲突

直接定址法的缺点也⾮常明显，当关键字的范围⽐较分散时，就很浪费内存甚⾄内存不够⽤。假设我们只有数据范围是[0,9999]的N个值，我们要映射到⼀个M个空间的数组中(⼀般情况下M>=N)，那么 就要借助哈希函数(hash function)hf，关键字key被放到数组的h(key)位置，这⾥要注意的是h(key)计 算出的值必须在[0, M)之间。

这⾥存在的⼀个问题就是，两个不同的key可能会映射到同⼀个位置去，这种问题我们叫做哈希冲突， 或者哈希碰撞。理想情况是找出⼀个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的， 所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的⽅案。

负载因子

假设哈希表中已经映射存储了N个值，哈希表的⼤⼩为M，那么负载因子=N/M ，负载因⼦有些地⽅也翻译为载荷因⼦/装载因⼦等，他的英⽂为load factor。负载因⼦越⼤，哈希冲突的概率越⾼，空间 利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低；

将关键字转为整数

我们将关键字映射到数组中位置，⼀般是整数好做映射计算，如果不是整数，我们要想办法转换成整数，这个细节我们后⾯代码实现中再进⾏细节展⽰。下⾯哈希函数部分我们讨论时，如果关键字不是整数，那么我们讨论的Key是关键字转换成的整数。

在这里插入图片描述
需要说明的是，实践中也是⼋仙过海，各显神通，Java的HashMap采⽤除法散列法时就是2的整数 次幂做哈希表的⼤⼩M，这样玩的话，就不⽤取模，⽽可以直接位运算，相对⽽⾔位运算⽐模更⾼ 效⼀些。但是他不是单纯的去取模，⽐如M是2^16次⽅，本质是取后16位，那么⽤key’= key>>16，然后把key和key’异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围 内，但是尽量让key所有的位都参与计算，这样映射出的哈希值更均匀⼀些即可。所以我们上⾯建 议M取不太接近2的整数次冥的⼀个质数的理论是⼤多数数据结构书籍中写的理论，但是实践中， 灵活运⽤，抓住本质。
在这里插入图片描述

【代码实现】

基础大框

可以先写出基本的框架：

#include<vector>

enum State
{
	EXIST,
	EMPTY,
	DELETE
};

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

template<class K, class V>
class HashTable
{
public:
	//无参的构造
    HashTable()
	:_tables(11)
	, _n(0)
{}

    bool Insert(const pair<K,V>& kv)
    {
        size_t hash0 = kv.first % _tables.size();//这里绝对不能%capacity
    }
private:
	vector<HashData<K, V>> _tables;
	size_t _n = 0;  // 记录数据个数，因为数据是散列分布的，vector的size不能代表数据个数
};
  • 这里为什么不能%capacity?

在这里插入图片描述

因为这样%capacity后会得到大于size位置的结果，但我们不能往这样的位置里放数据，因为虽然后面是给我们预留的空间，但是vector这个数据结构要求线性存储，我们只能一个一个存储不能随机存储！简单说其实就是越界访问了。

我们尽量保证size和capacity是一样大的，否则capacity很多，用不了就浪费。

（要抓住一点：这里我们对vector的使用与之前push_back()来插入不一样，我们这里是用[]访问，所以我们能访问的区间在size之内）

线性探测

那么size_t hash0 = kv.first%_tables.size();，我们现在已经得到这个映射位置，我们得看这个位置有没有已经有值，如果有的话我们就得开启线性探测。

在这里插入图片描述

bool Insert(const pair<K,V>& kv)
{
	size_t hash0 = kv.first % _tables.size();//这里绝对不能%capacity
	size_t hashi = hash0;
	size_t i = 0;
	while (_tables[hashi] == EXIST)
	{
		hashi = hash0 + i;
		++i;
	}
}
回绕

写到这里时就要注意了，我们线性探测，i一直++会越界，所以我们要让它回绕，方式就是%size：

while (_tables[hashi] == EXIST)
{
	hashi = (hash0 + i)%_tables.size();
	++i;
}

那么我们就完成了一个初步（有瑕）的哈希表：

enum State
{
	EXIST,
	EMPTY,
	DELETE
};



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



template<class K, class V>
class HashTable
{
public:
	HashTable()
		:_tables(11)
		, _n(0)
	{}

	bool Insert(const pair<K,V>& kv)
	{
		size_t hash0 = kv.first % _tables.size();//这里绝对不能%capacity
		size_t hashi = hash0;
		size_t i = 0;
		while (_tables[hashi] == EXIST)
		{
			hashi = (hash0 + i)%_tables.size();
			++i;
		}
		//到这里就是删除或者空，可以放入值
		_tables[hashi]._kv = kv;
		_table[hashi]._state = EXIST;
		++_n;//别把这个忘了

		return true;
	}
		
private:
	vector<HashData<K, V>> _tables;
	size_t _n = 0;  // 记录数据个数，因为数据是散列分布的，vector的size不能代表数据个数
};
解决表满了的问题

但是很快我们就会发现一个问题，这个哈希表如果满了，我们的insert里面的循环就会死循环，因为_tables[hashi] == EXIST会恒成立。

负载因子

这里我们就要想起我们的负载因子的概念了。

在这里插入图片描述

一般，开放定址法里我们要把负载因子控制到一个比较低的数。

扩容

这⾥我们哈希表负载因⼦控制在0.7，当负载因⼦到0.7以后我们就需要扩容了，我们还是按照2倍扩容，但是同时我们要保持哈希表⼤⼩是⼀个质数，第⼀个是质数，2倍后就不是质数了。

那么如何解决呢，⼀种⽅案就是除法散列中JavaHashMap的使⽤2的整数冥，但是计算时不能直接取模的改进⽅法。另外⼀种⽅案是sgi版本的哈希表使⽤的⽅法，给了⼀个近似2倍的质数表，每次去质数表获取扩容后的⼤⼩。

bool Insert(const pair<K,V>& kv)
{
	//负载因子>=0.7扩容
	if (_n / _tables.size()>=0.7)
	{

	}

注意一个这样的问题，我们在计算负载因子时，整数/整数只能得到整数，会舍弃小数部分，所以我们无法与0.7比较，所以得修改一下。

两种解决方法：

1.把分子、分母其中一个转成浮点数，这样另一个也就自动转了。

2.让分子与0.7都*10，变成if(_n*10/_tables.size()>=7)

扩容逻辑

我们具体怎么扩容呢？

这里我们先不管扩2倍后不是素数的问题，就扩2倍。

我们能扩容后直接把旧数据拷贝到新的空间里吗？不能！因为我们映射时根据的就是_tables.size()，而现在这个size都变了，我们直接拷贝下来无法对应新的映射关系，会导致无法正常查找删除等操作。

我们得把原来的值全部重新映射到新的表中。原本不冲突的可能冲突，原本冲突的可能继续冲突。

对比两种扩容方式
新vector

这里我们先看一种可能容易一下先想到的扩容方式，也就是创建一个新的vector

bool Insert(const pair<K,V>& kv)
{
	//负载因子>=0.7扩容
	if (_n / _tables.size()>=0.7)
	{
		vector<HashData<K, V>> newtables(_tables.size() * 2);
		//遍历旧表
		for (auto& e : _tables)
		{
			if (e._state == EXIST)
			{
				size_t hash0 = e._kv.first % newtables.size();
				size_t hashi = hash0;
				size_t i = 1;
				while (newtables[hashi] == EXIST)
				{
					hashi = (hashi + i) % newtables.size();
					++i;
				}
				newtables[hashi] = e._kv.first;
				newtables[hashi]._state = EXIST;
				
			}
		}
		newtables.swap(_tables);//局部对象出了作用域刚好把旧的表释放
	}

	size_t hash0 = kv.first % _tables.size();//这里绝对不能%capacity
	size_t hashi = hash0;
	size_t i = 1;
	while (_tables[hashi] == EXIST)
	{
		hashi = (hash0 + i)%_tables.size();
		++i;
	}
	//到这里就是删除或者空，可以放入值
	_tables[hashi]._kv = kv;
	_table[hashi]._state = EXIST;
	++_n;//别把这个忘了

	return true;
}

可以看到，我们其实在扩容的时候把线性探测的逻辑给重复写了一遍。

这样的代码水平难免略显低下，其实有更好的办法：

新HashTable
bool Insert(const pair<K,V>& kv)
{
	//负载因子>=0.7扩容
	if (_n / _tables.size()>=0.7)
	{
		//better way
		HashTable<K,V> newht;//注意newht对象就可以调用成员函数Insert了
		newht._tables.resize(2 * _tables.size());
		for (auto& e : _tables)
		{
			if (e._state == EXIST)
			{
				newht.Insert(e._kv);
			}
		}
		_tables.swap(newht._tables);
	}

	size_t hash0 = kv.first % _tables.size();//这里绝对不能%capacity
	size_t hashi = hash0;
	size_t i = 1;
	while (_tables[hashi] == EXIST)
	{
		hashi = (hash0 + i)%_tables.size();
		++i;
	}
	//到这里就是删除或者空，可以放入值
	_tables[hashi]._kv = kv;
	_table[hashi]._state = EXIST;
	++_n;//别把这个忘了

	return true;
}

这样的方法当我们把线性探测改成二次探测、双重探测等，就不需要扩容里也改一次，直接就跟着改了。

（插入第8个数据时，因为在插入的逻辑里我们是先计算负载因子，最后++_n;所以这时我们还是用70/11来和7比较的，还没有大于等于7，所以还不会扩容。当插入第9个数据时就会扩容了。）

这里我们用swap效率高，而赋值是一种深拷贝，深拷贝的代价比较大。

Find

要注意如果在Find里面，_tables[hashi]._kv.first==key我们就return找到的话，没有排除掉这个值已经被删掉的情况，因为我们删除的逻辑是直接把_state改成DELETE。

一种错误写法：

HashData<K, V>* Find(const K& key)
{
	size_t hash0 = key % _tables.size();
	size_t hashi = hash0;
	size_t i=1;
	//这样写会导致遇到EMPTY与DELETE就都返回找不到了，
	// 但是有可能我们要找的还在后面，这个位置被删了不影响它存在
	while (_tables[hashi]._state == EXIST)
	{
		if (_tables[hashi]._kv.first == key)
			return &_tables[hashi];
		hashi = (hash0 + i) % _tables.size();
		++i;
	}
	return nullptr;

}

正确：

while (_tables[hashi]._state != EMPTY)
{
	if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
		return &_tables[hashi];
    //走到这里要么是这个位置存在但值不是我们要的，要么是有值已被删除
	hashi = (hash0 + i) % _tables.size();
	++i;
}
return nullptr;

有了Find之后我们要把Insert再完善一下，因为我们现在要让这个哈希表不允许冗余：

bool Insert(const pair<K,V>& kv)
{
    if(Find(kv.first))
        return false;
    //……
}
Erase
bool Erase(const K& key)
{
	HashData<K, V>* ret = Find(key);
	if (ret)
	{
		ret->_state = DELETE;
		return true;
	}
	return false;
	
}

但是线性探测的问题其实挺多的，会有群积现象。

改善方式

二次探测

和线性探测十分类似

区别在于线性探测是+i，二次探测是 + ‾ i 2 \underline{+}i^2 +​i2，

所以二次的意思是二次方

h a s h i = ( h a s h 0 ± i 2 ) hashi = (hash0 ± i^2 ) % M hashi=(hash0±i2)，i={1,2,3,…, M 2 \frac{M}{2} 2M​}

要注意的是，当$hashi = (hash0 − i )%M $得到hashi<0时，需要hashi+=M

这样就可以避免把一片都堵了，可以更分散

变成二次探测
size_t hash0 = kv.first % _tables.size();
size_t hashi = hash0;
size_t i = 1;
while (_tables[hashi] == EXIST)
{
	hashi = (hash0 + i*i)%_tables.size();
	++i;
}

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

也可以实现出+一下再-一下：

size_t hash0 = kv.first % _tables.size();
size_t hashi = hash0;
size_t i = 1;
int flag=1;
while (_tables[hashi] == EXIST)
{
	hashi = (hash0 + (i*i*flag))%_tables.size();
	++i;
    flag*=-1;
}

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

这样写乍一看是对的，其实有一个问题，这样写每次不管flag正还是负都++了，会导致其实第一次进循环是hash0+1，第二次是hash0-4，第三次是hash0+9，没有做到+1，-1，+4，-4，+9…这样的效果。

所以我们应该这样写才对：

size_t hash0 = kv.first % _tables.size();
size_t hashi = hash0;
size_t i = 1;
int flag=1;
while (_tables[hashi] == EXIST)
{
	hashi = (hash0 + (i*i*flag))%_tables.size();
	if(flag<0)
    {
        flag=1;
        ++i;
    }
    else
    {
        flag=-1;
    }
}

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

因为如果是hash0-n的话，就是往左找空位，如果hash0-n<0时我们其实是从最后开始往前回绕的。而如果是hash0+n越界是从头开始往后走，所以hash0-n的回绕是+M，hash0+n的回绕方式是%M（画一下图会更好理解）

为什么+M就可以保证变回正的？因为hashi = (hash0 + (i*i*flag))%_tables.size();这里我们得到的负的hashi是mod过M（即size）的，所以这个绝对值是比M小的，所以+M可以保证变为正。

while (_tables[hashi] == EXIST)
{
	hashi = (hash0 + (i*i*flag))%_tables.size();
    if(hashi<0)
    	hashi+=_tables.size();
	if(flag<0)
    {
        flag=1;
        ++i;
    }
    else
    {
        flag=-1;
    }
}

不过简单一点的话，不用+一下-一下也行。直接+二次方就行

扩容后还要是素数

两种解决方法。

sgi版本的哈希表

⼀种⽅案是sgi版本的哈希表使⽤的⽅法，给了⼀个近似2倍的质数表，每次 质数表获取扩容后的⼤⼩。（它给的素数是不太接近2的幂，接近2倍的）

inline unsigned long __stl_next_prime(unsigned long n)
{
     // Note: assumes long is at least 32 bits.
     static const int __stl_num_primes = 28;
     static const unsigned long __stl_prime_list[__stl_num_primes] =
     {
         53, 97, 193, 389, 769,
         1543, 3079, 6151, 12289, 24593,
         49157, 98317, 196613, 393241, 786433,
         1572869, 3145739, 6291469, 12582917, 25165843,
         50331653, 100663319, 201326611, 402653189, 805306457, 
         1610612741, 3221225473, 4294967291

     };
     const unsigned long* first = __stl_prime_list;
     const unsigned long* last = __stl_prime_list + __stl_num_primes;
     const unsigned long* pos = lower_bound(first, last, n);
     return pos == last ? *(last - 1) : *pos;
}
lower_bound

在这里插入图片描述

  • 在 C++ 的标准模板库（STL）中，lower_bound是一个非常有用的函数。它用于在一个已排序的区间（可以是数组、vector等支持随机访问迭代器的容器）中查找第一个大于或等于给定值的元素的位置。

如果范围内所有元素的比较值都小于 val，函数返回最后一个元素。所以我们会写：

return pos == last ? *(last - 1) : *pos;

因为如果pos得到的是last说明表中没有比n大的了，那么就返回表中的最后一个值也就是last-1位置的值。

可以看到这个函数的作用就是返回第一个大于等于n的素数，如果n比表中值都大就返回表中最后一个值。

所以我们现在可以把我们的哈希表的默认构造给的缺省值以及扩容的逻辑修改：

HashTable()
	:_tables(__stl_next_prime(0))
	, _n(0)
{}

if (_n / _tables.size()>=0.7)
{
	HashTable<K,V> newht;
	newht._tables.resize(__stl_next_prime(_tables.size()+1);//+1，否则获取大于等于一直获取到当前的获取不到下一个
	for (auto& e : _tables)
	{
       //……
Java中的方式

Java的HashMap采⽤除法散列法时就是2的整数次幂做哈希表的⼤⼩M，这样玩的话，就不⽤取模，⽽可以直接位运算，相对⽽⾔位运算⽐模更⾼效⼀些。

但是他不是单纯的去取模，⽐如M是2^16次⽅，本质是取后16位，那么⽤key’= key>>16，然后把key和key’异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围内，但是尽量让key所有的位都参与计算，这样映射出的哈希值更均匀⼀些即可。所以我们上⾯建议M取不太接近2的整数次幂的⼀个质数，对于这种方法来说就不需要了。

这种方法扩容就是2倍扩。

（按位与运算符“&”是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位都为1时，结果位才为1。参与运算的两个数均以补码出现。
当且仅当两个输入值不同时，异或运算输出为真（1），否则输出为假（0），即“同为 0，异为 1”。）

我们也可以采取一下这种方式看看
大致思路：

size_t HashFunc(const key& key)
{
	//size_t hash = key % _tables.size();//相当于保留了后size位
	//但实践中不喜欢这样写，而是转化为更高效的做法，除转换为右移，模转换为保留后多少位
	size_t hash = key & (_tables.size() - 1);//这样是保留后size位
	hash ^= (key >> (32 - _m));
	return hash;
}
如果key不是整型

回到我们sgi版本的哈希表，还有一个重要问题没有解决
指针、浮点数还能强转成整型但string这样的强转也转不了。
解决办法是加一个仿函数。

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

template<class K,class V,class Hash = HashFunc<K>>
class HashTable
{
public:
	HashTable()
		:_tables(__stl_next_prime(0))
		, _n(0)
	{}
//……

//是整型还是返回整型，不是整型会强转成整型
Hash hash;
size_t hash0 = hash(kv.first) % _tables.size();

size_t hashi = hash0;
size_t i = 1;
while (_tables[hashi] == EXIST)
{
	hashi = (hash0 + i*i)%_tables.size();
	++i;
}
//……

	HashData<K, V>* Find(const K& key)
	{
		Hash hash;
		size_t hash0 = hash(key) % _tables.size();
		//……

string的：

struct StringHahFunc
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
		}
		return hash;
	}
};

int main()
{
	const char* a[]={"abcd","sort","insert"};
	HashTable<string,string,StringHashFunc> ht;
	for(auto& e:a)
	{
		ht.insert({e,e});
	}
	return 0;
特化string

因为string太常用了，所以其实可以不传这个仿函数，也就是我们给string写一个特化

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

template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
		}
		return hash;
	}
};
解决abc与acd得到hash值一样的问题

也就是，如果key是其他类型会走上面这个模版，如果是string就会走下面这个特化的
但现在我们的代码，abcd 和 acbd会得到一样的结果，所以还得再优化：
在这里插入图片描述
（别少写一个括号，因为是匿名对象去调用operator()）
这三条都会得到相同hash值

怎么解决？
BKDR（可以网上查）
比如我们可以每次加上一个ch值后将hash乘上一个固定的值
在这里插入图片描述
在这里插入图片描述
现在结果就不同了
97131+98与98131+97，肯定是不一样的
在这里插入图片描述
哈希表对key的要求是，自定义类型要传转成整型的仿函数，同时这个自定义类型要能支持==
红黑树对key的要求是要支持比较大小，至少支持一个<，不支持要重载对应的仿函数

在这里插入图片描述
这还有个模版参数Pred是因为如果我们的Key是个日期类，而且是别人写的，我们不方便改他的代码，我们可以再写一个仿函数传给unordered_map，来支持==
所以不支持整型就写个仿函数支持，不支持等于也写个仿函数支持
外部可控

小总结

哈希表的整个设计逻辑围绕着减少哈希冲突，直接定址法，局限性强，现实中不好用；开放定址法有很多种方法（实践中除留余数法用得多）难以避免冲突，本质还是一种“内耗”，去占其他人的位置；链地址法（哈希桶）比较好。

网站公告

今日签到

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

热门文章

最新发布