erase

bool Erase(const K&key){size_t hashi =key % _tables.size();Node* cur =_tables[hashi];Node* prev =nullptr;while(cur){if(cur->_data ==key){if(prev ==nullptr){_tables[hashi]=cur->_next;}else{prev->_next =cur->_next;}delete cur;_n--;returntrue;}prev =cur;cur =cur->_next;}returnfalse;}

对于删除的逻辑我们先找到映射位置，然后先定义一个prev标记前一个指针，然后遍历当前桶，如果当前位置的值和需要删除的值相同，则可以分出两种情况，第一种情况是头删，头删就说明prev是nullptr，则可以直接令头指针等于下一个节点，如果是删除中间的，则可以令prev指向cur的下一个节点，然后释放当前节点，注意：释放当前节点的时候需要_n—。
接下来我们来封装insert

insert

bool Insert(const pair<K, V>&kv){//去冗余	if(Find(kv.first)){returnfalse;}//扩容，通过负载因子来进行扩容	if(_n * 10/ _tables.size()==7)//负载因子为0.7的时候进行扩容	{//不能直接进行resize，因为扩容之后空间变化了，映射也要跟着变化		//创建一个新表是以前表的二倍		HashTable<K, V>newHT;newHT._tables.resize(_tables.size()* 2);for(size_t i =0;i <_tables.size();i++){if(_tables[i]._state ==EXIST){//直接复用insert				//这里不是自己调用自己，因为这里是两个对象				newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hs;//算起始位置	size_t hashi =hs(kv.first)% _tables.size();//状态存在则继续	while(_tables[hashi]._state ==EXIST){hashi++;//防止hashi越界		hashi %=_tables.size();}//添加值并且状态改为存在	_tables[hashi]._kv =kv;_tables[hashi]._state =EXIST;_n++;returntrue;}

要进行插入我们首先需要找到插入位置，假如当我们找到位置的时候，当前位置已经被占据了，所以我们只能向后移动。

哈希表的关键组成部分

1. 哈希函数 (Hash Function)：将输入的键（key）映射为哈希表的索引。在实际开发中，理解负载因子、它的核心思想是通过一个哈希函数（Hash Function）将输入数据（键）转换为数组中的索引，以便在常数时间内进行查找、

   如果我们直接扩容的话也不是不行，但是会很浪费我们的空间，所以我们可以不释放当前节点，直接把旧表的节点插入到新表映射的位置上去，就不用浪费空间了。

   find

   Node* Find(const K&key){size_t hashi =key % _tables.size();Node* cur =_tables[hashi];while(cur){if(cur->_data ==key){returncur		}cur =cur->_next;}returnnullptr;}

   对于查找来说直接找到映射位置遍历hash桶即可。掌握了这些知识后，相信你能够更加自信地在复杂应用中使用哈希表。
   在HashTables中_n表示hash表中插入了多少个数。

负载因子的影响

• 如果负载因子过高（接近 1 或大于 1），冲突会变得频繁，导致性能下降。字典等。

insert

bool Insert(const pair<K,V>&kv){if(Find()){returnfalse;}//找到插入的位置	size_t hashi =kv.first % _tables.size();//需要控制负载因子，hash桶的负载因子需要控制在1	if(_n ==_tables.size()){vector<Node*>newtables(_tables.size()* 2, nullptr);for(size_t i =0;i <_tables.size();i++){//将旧表中的节点进行复用，头插			Node* cur =_tables[i];while(cur){Node* next =cur->_next;//重新计算插入位置				size_t hashi =cur->_kv.first % newtables.size();cur->_next =newtables[hashi];//先指向第一个				newtables[hashi]=cur;//然后再成为第一个				cur =next;}_tables[i]=nullptr;}_tables.swap(newtables);}//头插,尾插也可以，但是尾插需要找到尾，所以这里我们选择头插不用找尾	Node* newnode =new Node(kv);newnode->_next =_tables[hashi];_tables[hashi]=newnode;_n++;returntrue;}

对于插入来说，我们可以直接算出插入位置，然后在当前桶中进行头插，为什么进行头插而不进行尾插呢？
因为头插可以直接插，而尾插则需要找到尾之后才能插入，大大影响了我们的插入效率，所以我们进行头插。如果两个不同的键通过哈希函数得到了相同的索引（称为哈希冲突），多个键可以通过链表或其他方式存储在同一个槽中。理想的哈希函数应该均匀分布键，避免过多冲突。二次探测等），将冲突的键存储在下一个可用的槽位中。插入和删除操作。

示例

假设一个哈希表的存储桶数量为 10：

• 当插入 5 个元素时，负载因子为：

$$\alpha =\frac{5}{10}=0.5$$

• 当插入 9 个元素时，负载因子为：

$$\alpha =\frac{9}{10}=0.9$$此时可能需要进行再散列操作来扩展哈希表的大小。常见的解决方法有：

• 链地址法 (Separate Chaining)：在每个槽中存储一个链表，冲突的键会被添加到链表中。
• 存储桶 (Bucket)：每个哈希表的槽位。再散列等概念，并针对具体场景合理调整这些参数，能够确保哈希表在性能和内存占用上的平衡。

  负载因子 (Load Factor)

  负载因子是指哈希表中已存储元素的数量与哈希表大小（存储桶数量）的比值，公式为：

  $$\alpha =\frac{n}{m}$$

  • n：哈希表中已存储的元素数量。

    ~HashTable()

    因为每个节点都是我们new出来的，所以需要我们手动释放，所以写一个析构函数，释放每个节点，遍历每个桶逐个释放

    ~HashTable(){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;}}

    总结

    通过对哈希表的封装，我们不仅提升了代码的可读性和复用性，还通过合理设计哈希函数和处理冲突机制，优化了哈希表的性能。

  • 负载因子越大：意味着哈希表中存储的元素越来越多，冲突的概率增加，查找和插入操作的效率下降。

    文章目录

    • hash表
    • • 哈希表的关键组成部分
      • 哈希表的优缺点
      • • 优点：
        • 缺点：
      • 常见应用场景
    • 开放定址法实现hash表
    • • 负载因子 (Load Factor)
      • • 负载因子的意义
        • 负载因子的影响
        • 再散列 (Rehashing)
        • 示例
      • 整体框架
      • insert
      • Find
      • erase
      • hash桶封装
      • 框架
      • insert
      • find
      • erase
      • ~HashTable()
    • 总结

    hash表

    哈希表是一种数据结构，它通过将键映射到存储桶或槽来快速查找数据。

  缺点：

  • 当发生大量冲突时，查找和插入的性能可能退化到 O(n)。这时通常会进行再散列 (rehashing)，即扩展哈希表的大小，并重新计算所有元素的哈希值。
    插入的逻辑说完之后，，我们也要扩容，对于hash桶实现hash表来说，我们的扩容的前提是当每个_n== 1的时候，意思就是每个桶都有一个节点的时候，_n==1的时候最好的情况是每个桶有一个节点，，这个情况的前提就是保证每个桶都有节点。

  例如，如果哈希表有 100 个存储桶，已存储了 60 个元素，那么负载因子为：

  $$\alpha =\frac{60}{100}=0.6$$

  负载因子的意义

  1. 负载因子越小：意味着哈希表中空槽越多，冲突（collisions）的概率越低，查找和插入操作的性能更好。
     
     插入的及基本逻辑经济就是如此，既然有插入那肯定有插入位置满的时候，所以插入逻辑中应该涉及到扩容，但是我们不能直接进行扩容，因为当我们扩容的时候，每个data的映射的位置也会随之而变化，这就涉及到我们应该找到新的映射位置，但是对于开放定址法来说，我们不是在插入位置满的时候扩容，而是在负载因子到达0.7的时候进行扩容。

     接下来我们将分别用开放定址法和哈希桶的方法来实现hash表

     开放定址法实现hash表

     首先我们在封装hash表之前要了解什么是负载因子。（注意：这里调用的不是同一个insert，因为是两个不同的对象）

     Find

     HashData<K, V>* Find(const K&key){Hash hs;//算起始位置	size_t hashi =hs(key)% _tables.size();//状态存在则继续	while(_tables[hashi]._state !=EMPTY){//这个状态不是DELETE才能进行查找		if(_tables[hashi]._state !=DELETE &&_tables[hashi]._kv.first ==key){return&_tables[hashi];}hashi++;//防止hashi越界		hashi %=_tables.size();}returnnullptr;}

     对于查找来说我们只需要找到当前需要查找的数据的所在的位置，然后从查找的位置对这个表进行遍历，如果遇到和当前值相等的则直接返回当前位置的地址，需要注意的是：我们还要考虑状态，当状态是DELETE的时候，但是当前值又等于查找的值，这个值是不能返回的，因为当前值已经删除了，所以这种情况需要排除，所以前面需要添加一个判断条件。

  2. 开放地址法 (Open Addressing)：通过重新计算索引（如线性探测、
     在HashTable中我们需要一个vector，这个vector的类型是Node*，相当于存放的是指针。

     hash桶封装

     框架

     template<class K,class V>struct HashNode{pair<K,V>_kv;HashNode<T>* _next;HashNode(const pair<K,V>&kv):_kv(kv),_next(nullptr){}};template<class K, class V>class HashTable{public:	typedef HashNode<K,V>Node;private:	//hash桶	//hash桶当中的Node节点是new出来的，需要写析构函数	vector<Node*>_tables;//表中存储的数据个数	size_t _n =0;};

     用hash桶来封装hash表我们需要一个结构体，结构体中包含指向下一个结构体的指针，还有一个存放数据的kv。
     
     上述代码描述的结构就是上面这种结构。

  3. m：哈希表的总存储桶（bucket）数量。

     整体框架

     //三种状态	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:	private:		//用一个Hash表来存储		vector<HashData<K, V>>_tables;//表中插入的数据个数		size_t _n =0;};

     在开放定址法中，我们需要用一个状态来表示hash表中每个位置的状态，由于每个位置的状态不止两种，所以我们不能使用布尔值来表示每个位置的状态，应该使用enum来定义多种状态，我们定义三种状态（EMPTY，EXIST，DELETE）分别表示空，存在，删除。

再散列 (Rehashing)

当负载因子达到阈值时，哈希表会增大存储桶的数量（通常是倍增），并重新计算所有已存储元素的哈希值，将它们放入新的存储桶中。

erase

bool Erase(const K&key){//找到删除位置	HashData<K, V>* ret =Find(key);if(ret){ret->_state =DELETE;returntrue;}returnfalse;}

对于删除某个值，我们首先需要查找，所以这里我们可以复用查找，用HashData<K,V>接收一下，如果当前指针是空指针就直接返回false，说明需要删除的值没在表中，如果当前指针不是空指针，则将状态设置为DELETE状态。

在扩容的时候，我们可以直接创建一个新表，然后在新表中重新映射数据，这里我们可以直接复用insert。