【C++】 哈希

文章目录

• • 1. 哈希概念
  • 2. 哈希表
  • • 直接定址法(常用)
    • 除留余数法(常用)
    • 解决哈希冲突方法1 ——闭散列
    • 解决哈希冲突方法2 ——开散列
  • 3. 闭散列的实现
  • • 如何处理删除数据？
    • 定义数据结构
    • insert
    • • len为 _tables.size() 还是 _tables.capacity()？
      • 线性探测
      • 负载因子
      • 扩容
    • Find
    • Erase
    • 完整代码
  • 4. 开散列的实现
  • • 定义数据结构结构
    • insert
    • • 扩容
    • Find
    • Erase
    • 针对传入string的情况
    • 使用特化避免传入仿函数
    • 完整代码

1. 哈希概念

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立
一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置
取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称
为哈希表(Hash Table)(或者称散列表)

2. 哈希表

key跟存储位置建立映射(关联)关系

直接定址法(常用)

每一个值都有一个唯一位置
特点：适用于范围比较集中的数据

除留余数法(常用)

特点：范围不集中，分布分散

当前数据非常分散，虽然最大值已经达到1000，但是空间使用效率太低，所以不应该开1000个空间储存
所以想要把分散的数据，映射到固定的空间中

key值跟存储位置的关系，是模出来的
不同的值有可能映射到相同的位置 即哈希冲突
如55与15取模后的值都为5

解决哈希冲突方法1 ——闭散列

闭散列又称 开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明哈希表中必然还有空位置，则可以把key存放到冲突位置中的下一个位置去

如何寻找下一个位置？
线性探测

若有两个取模相同的值，则将先进来的占住当前取模位置，后进来的向后探测，若有空位置则放入

因为是先将2取模，所以2占住了映射2的位置，而当将102取模时，由于位置被2占住，所以向后寻找空位置，即在映射4的位置

hashi=key%len
len代表 表的长度
若当前位置已经被占住，hashi+i (i>=0)
i从0开始，不断增加直到找到一个没有占住的位置，超过该表的长度

解决哈希冲突方法2 ——开散列

开散列法又称为链地址法，对关键码集合用散列函数计算散列地址，具有相同地址码归于同一个子集合
每一个子集称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头节点存储在哈希表中

相比于闭散列，哈希冲突减少了

3. 闭散列的实现

当使用除留余数法解决问题时
不同的值映射在相同的位置，即哈希冲突/哈希碰撞

使用线性探测处理，依次找后面位置存储 hashi + i (1，2，3，4)

如何处理删除数据？

假设要删除33，因为33取余后为3，所以先去位置为3的地方去找，没有找到，则继续向后寻找
寻找到空才结束

假设把33直接删除，当再次查找13时，由于提前遇到空，则直接结束
所以找到后，并不能直接删除，因为会影响查找
设置三种状态： 空、存在、删除

定义数据结构

需要使用枚举来表示三种状态 删除 存在 空

表示状态的state 也应该默认设为空，不然有可能造成 映射位置 没有数据但是 状态为存在的情况

insert

hashi=key%len
len代表 表的长度
若当前位置已经被占住，hashi+i (i>=0)

len为 _tables.size() 还是 _tables.capacity()？

假设将hashi的大小设为capacity
若当前位置为空，则将值填入进去，并且将状态设置为存在，会造成越界
在vector中 operator[] 会做越界检查，下标是否小于size