标题：[数据结构] 开散列法 && 闭散列法 模拟实现哈希结构

个人主页：@水墨不写bug

---

---

目录

一、闭散列法

核心逻辑的解决

        i、为什么要设置位置状态？（伪删除法的使用）

        ii、哈希函数的设计

接口的实现 

1、插入（Insert）

仿函数取数值域的key

插入的 扩容逻辑

2、删除（Erase）

3、查找（Find）

---

正文开始：

        在之前的讲解中，我们已经了解到哈希结构的基本实现思路，具体讲解见这一篇：

《[数据结构] 哈希结构的哈希冲突&&解决哈希冲突》。实现哈希的方法主要区别在与哈希冲突的解决不同，我们知道常见的解决哈希冲突的方法有：

        闭散列法：找到下一个空位置存储；

        开散列法（链地址法、开链法）：通过一个链表（哈希桶）来解决哈希冲突的问题。

        本文将分别实现上述两种方法，以及其各自的实现思路，主要实现哈希表的主要功能：插入（Insert）、删除（Erase）、查找（Find）等的主要逻辑。

---

一、闭散列法

        闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

---

核心逻辑的解决

        i、为什么要设置位置状态？（伪删除法的使用）

        对于一个位置，如果发生哈希冲突，就需要把数据存放到下一个空位置中去，当我们下一次查找这个数据的时候，就需要走一遍和存储时一样的操作。

        比如，我们要在下面的这样的一个哈希表中存储一个数据：

        14%10 = 4：

        向后探测的条件可以猜测为：

        如果表中的不为空，就向后探测。

        但是当我们删除一个元素：这个元素是探测路径上的一个元素，那么下一次当我们查找14的时候，就找不到了。

        所以，我们在设计哈希数据的时候，就需要在每一个数据结构中设置一个状态值：

//哈希表位置的状态
enum State{EXIST,EMPTY,DELETE};

        这样，我们的状态体系就实现了：哈希表一个位置的默认状态为“EMPTY”；如果插入一个数据，那么这个位置的状态就需要更新为“EXIST”，在删除了一个数据之后，需要将这个位置的状态设置为“DELETE”。

        这样，我们就完美解决了删除数据后导致查找数据无法找到的问题。

        实现闭散列哈希需要一个顺序表，这里用vector即可。每一个数据位置存储的是一个自定义类型哈希数据（HashData），这个结构内部存储：

数据域、状态域

         数据域根据传入的模板参数决定：（比如传入的是int，或者pair<int,int>）

    //哈希表的数据
	template<class T>
	struct HashData
	{
		//默认构造，一般不会用到
		HashData()
			:_state(EMPTY)
			,_data(T())
		{}
		//插入数据时的构造函数
		HashData(const T& data)
			:_state(EXIST)
			,_data(data)
		{}
		T _data;
		State _state;
	};

        ii、哈希函数的设计

        对于一般的自定义类型（整形，浮点型，指针类型）可以强制转换为size_t类型，我们可以将默认的哈希函数设计为直接强制类型转换为size_t；

        对于常用自定义类型string， 我们设计如下的哈希类仿函数的特化版本：

//特化string版本
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (const auto& e : s)
		{
			hash += e;
			hash *= 31;
		}
		return hash;
	}
};

---

接口的实现 

1、插入（Insert）

仿函数取数值域的key

        在插入逻辑之前，我们首先需要知道 插入的数据类型V是不确定的，是通过类模板的参数决定的。（这涉及到了unordered_map和unordered_set的需要复用同一个哈希的封装）

        我们暂时不直接看底层实现，只需要知道有一种仿函数，可以取得数据域的key：

/*模板参数介绍
 *关键值:K 
 *数值域:V
 *得到Key的仿函数:KeyOfV 
 *hash值计算仿函数:Hash
 */
template<class K,class V,class KeyOfV,class Hash = HashFunc<K>>
class HashTable
{
    // 具体实现  
};

        由于插入的逻辑比较简单，这里不再解释，直接给出插入的核心逻辑：

bool Insert(const V& data)
{    
    //仿函数，得到数据的关键值
    KeyOfV kov;
    Hash hs;

    //如果有重复数据，插入失败
    //Find是通过key来查找的，如果插入的时候哈希表中已经存在，则返回false，插入失败
    if (Find(kov(data)) != nullptr)
	    return false;

    //...

    size_t hashi = hs(kov(data)) % _table.size();
    while (_table[hashi]._state == EXIST)
    {
	    ++hashi;
	    hashi %= _table.size();
    }
    _table[hashi]._data = data;
    _table[hashi]._state = EXIST;
    _n++;
    
    return 0;
}

插入的 扩容逻辑

        《[数据结构] 哈希结构的哈希冲突&&解决哈希冲突》讲解中，我们了解到载荷因子是反应哈希表装载程度的量：用载荷因子和size（）的比值来决定什么时候要扩容。

        我们界定：载荷因子*10/size（） >= 0.7的时候需要扩容。

        扩容就需要进行数据的转移。

        为了体现复用（实际上是懒），我们可以new一个新的表，再遍历旧表的数据，一个一个插入新表即可，最终交换新表和旧表的vector即可：

//检查是否需要扩容
if (_n * 10 / _table.size() >= 7)
{
	//新建哈希表，容量为2倍
	HashTable<K,V,KeyOfV> newHT;
	newHT._table.resize(_table.size() * 2);

	//将旧表的数据移动到新表
	for (int i = 0; i < _table.size(); ++i)
	{
		if (_table[i]._state == EXIST)
		{
			newHT.Insert(_table[i]._data);
		}
	}
	_table.swap(newHT._table);
}

插入：

//插入数据
bool Insert(const V& data)
{
	//仿函数，得到数据的关键值
	KeyOfV kov;
	Hash hs;

	//如果有重复数据，插入失败
	if (Find(kov(data)) != nullptr)
		return false;

	//检查是否需要扩容
	if (_n * 10 / _table.size() >= 7)
	{
		//新建哈希表，容量为2倍
		HashTable<K,V,KeyOfV> newHT;
		newHT._table.resize(_table.size() * 2);

		//将旧表的数据移动到新表
		for (int i = 0; i < _table.size(); ++i)
		{
			if (_table[i]._state == EXIST)
			{
				newHT.Insert(_table[i]._data);
			}
		}
		_table.swap(newHT._table);
	}

	size_t hashi = hs(kov(data)) % _table.size();
	while (_table[hashi]._state == EXIST)
	{
		++hashi;
		hashi %= _table.size();
	}
	_table[hashi]._data = data;
	_table[hashi]._state = EXIST;
	_n++;

	return true;
}

2、删除（Erase）

         删除的逻辑比较简单，我们需要先借助find根据key找到需要删除的数据的应该存在的哈希表的位置，再一个一个向后限行探测即可；如果找到，伪删除，修改状态为DELETE，如果没有找到，返回nullptr：

bool Erase(const K key)
{
	HashData<V>* ret = Find(key);
	if (ret == nullptr)
		return false;
	else
	{//修改数据状态表示删除
		ret->_state = DELETE;
		return true;
	}
}

3、查找（Find）

         查找的逻辑也是不复杂的；首先找到数据应该存在的表中的位置，如果一个一个向后限行探测即可；唯一需要注意的是状态为DELETE的时候，需要继续往后查找：

//根据key查找数据
HashData<V>* Find(const K key)
{
	KeyOfV kov;//得到data的关键值
	Hash hs;//哈希函数

	size_t hashi = hs(key) % _table.size();
	while (_table[hashi]._state != EMPTY)
	{
		if (_table[hashi]._state == EXIST && kov(_table[hashi]._data) == key)
			return &_table[hashi];
		hashi++;
		hashi %= _table.size();
	}
	return nullptr;
}

---

 待续~

未经作者同意禁止转载