【C++】哈希——unordered系列容器&哈希概念&哈希冲突(中)

简介: 【C++】哈希——unordered系列容器&哈希概念&哈希冲突(中)

3. 哈希函数


哈希结构最关键的点就是哈希函数的设置

哈希函数的设置原则

  • 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
  • 哈希函数计算出来的地址能均匀分布在整个空间中
  • 哈希函数应该比较简单


常见的哈希函数设置方法

1、直接定址法常用

直接定址法是最常用的哈希函数,就是根据key直接取到存储位置,这里的位置可能是绝对位置也可能是相对位置。

哈希函数:Hash(Key)= A*Key + B

例如对于统计字符串中某种字符出现的次数,key的范围比较小,所以这里可以直接映射

Hash(key) = 1 * ‘a’ - ‘a’,这里就把a映射给0,所以显而易见z映射给了26。

但是如果数据比较分散的话,就不适合使用直接定址法了,比如对于集合{1, 2, 3, 4,99, 999},就会造成很大的空间浪费


2、除留余数法常用

为了应对直接定址法中的数据较为分散造成空间浪费的情况,有人设计出了除留余数法,用于集中数据。设哈希表中允许的地址数为m,取一个不大于m,但最接近或者等于m的素数p作为除数,按照哈希函数,将关键码转换成哈希地址。

**哈希函数:**Hash(key) = key % p (p<=m)


3、平方取中法了解

假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址

适合:不知道关键字的分布,而位数又不是很大的情况


4、折叠法了解

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。

适合事先不需要知道关键字的分布,适合关键字位数比较多的情况


5、随机数法了解

选择一个随机函数,取关键字的随机函数值为它的哈希地址,

**哈希函数:**Hash(key) = random(key),其中 random为随机数函数。

通常应用于关键字长度不等时采用此法


6、数学分析法了解

设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定 相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散 列地址。

例如:假设要存储某家公司员工登记表,如果用手机号作为关键字,那么极有可能前7位都是 相同 的,那么我们可以选择后面的四位作为散列地址,如果这样的抽取工作还容易出现 冲突,还 可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。

适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均匀的情况


4. 哈希冲突


上面那个例子,使用哈希的方式解决,看起来这样的算法非常棒,但是,如果数据集中还有一个44需要被插入,怎么办呢?44对应的hashkey也是4,和4产生了冲突。这就是哈希冲突,也叫哈希碰撞

对于两个数据元素的关键字ki和kjimage.png即:不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突/哈希碰撞把具有不同关键码而具有相同哈希地址的数据元素称为同义词”。

哈希函数的设置决定了哈希冲突的产生可能性,哈希函数设置的越巧妙,越能够减小哈希冲突,但是哈希冲突是不可能被完全避免的


5. 哈希冲突的解决——开散列和闭散列


由于哈希冲突是不可避免的,所以当然要总结哈希冲突的解决方案,一般来说,解决方案分为两种——闭散列开散列


5.1 闭散列

闭散列也叫开放定址法:当发生哈希冲突的时候,如果哈希表还没有被装满,那么就有空余的位置存放,那么就可以把key存放到冲突位置的“下一个空位置”中


那么,怎么寻找下一个空位置呢?


这里同样有很多种方式,最经典的就是线性探测


同样的,针对上述的哈希冲突的例子,现在需要插入元素44,通过哈希函数计算出哈希地址为4,因此44理论上插入的位置是4,但是由于该位置已经存放了值为4的元素,出现哈希冲突,所以依次向后探测,直到寻找到下一个空位置为止。


所以,针对线性探测的插入和删除算法如下:

1、插入

  • 通过哈希函数获取到待插入元素在哈希表中的为止
  • 如果该位置没有元素就直接插入新元素,如果该位置有元素就继续找下一个空位置,插入新元素
  • 933633f3e8eb9624f3d037ba5d4faf38.png

2、删除

采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

所谓伪删除法就是用一个状态标志来代表此位置的状态

enum State {EMPTY, EXIST, DELETE};
// EMPTY此位置空, EXIST此位置已经有元素, DELETE元素已经删除


闭散列线性探测的哈希表代码实现插入删除查找

首先对于闭散列的哈希表,有以下的结构设计

1、由于伪删除法的存在,所以需要让表里面存放的数据中增加一个状态变量,这里使用一个枚举来给出状态情况

enum State { EMPTY, EXIST, DELETE };


2、表中的元素类型是一个KV结构的pair和一个状态变量state,所以哈希数据结构体设计如下

//HashData数据结构体
template<class K, class V>
struct HashData
{
    std::pair<K, V> _kv;
    State _state = EMPTY;
}


3、由于KV结构中的key是一个泛型,当我们在进行哈希映射的时候,需要先让其映射成为整型,然后才能够映射到哈希地址,所以这里提供一个仿函数,用于将key映射到整型家族

//仿函数,映射到整型
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return (size_t)key;
    }
};


由于string类型在哈希映射中使用的频率非常高,所以有人对string的哈希算法做了一些研究与总结,这里附上链接,有兴趣的小伙伴可以去看一看 [字符串哈希算法](各种字符串Hash函数 - clq - 博客园 (cnblogs.com)),下面是hash映射的string类型的特化

//模版特化,针对string类型
template<>
struct HashFunc<std::string>
{
    size_t operator()(const std::string& key)
    {
        //采用了特殊方法把各元素的值放在一起
        size_t hash = 0;
        for (auto ch : key)
        {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};

4、闭散列哈希表的结构

  • 由于哈希表是KV模型,所以模板参数中肯定要有KV,除此之外,由于哈希映射的key要求是整型,所以一定需要提供一个仿函数来把key映射给整型
  • 哈希表本身使用一个vector来管理,再加上一个整型的n用来存放哈希表中的有效数据个数

所以哈希表的结构就显而易见了

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
    HashTable()//由于哈希表需要根据容量来判断哈希地址,所以_tables必须要先初始化,所以这里显示写构造函数
        :_n(0)
  {
    _tables.resize(10);
  }
private:
    std::vector<Data> _tables;//表里面存储的是HashData,HashData内部是一个KV结构和一个状态
    size_t _n = 0;//存储表中的有效数据个数
};


5、插入

//插入
bool Insert(const std::pair<K,V>& kv)
{
    if(Find(kv.first))//如果已经存在,插入失败返回false
        return false;
    //扩容:判断是否扩容的方式是判断负载因子大小 负载因子 = 存放有效个数/哈希表容量(一般对于线性探测来说都是小于1的)
    if(_n * 10 / _tables.size() >= 7)//负载因子大于0.7时扩容
    {
        //这里采用二倍的方式扩容,实际上不是这样扩容的,在上文中说明按照
        HashTable<K, V, Hash> newTable;
        newTable._tables.resize(2 * _tables.size());//重新创建一个哈希表,大小是原表的二倍
        for(auto& e : _tables)//遍历原表,如果有数据的话就在新表中插入
        {
            if(e._state == EXIST)
            {
                newTable.Insert(e._kv);
            }
        }
        _tables.swap(newTable._tables);//交换二者的表(vector对象),这里调用的是vecotr库里的swap
    }
    //插入数据
    size_t hashi = Hash()(kv.first) % _tables.size();//通过Hash的匿名对象映射出一个整形,通过这个整型除留余数从而定址
    while(_tables[hashi]._state == EXIST)//映射的位置已经有值,出现哈希冲突,进行线性探测
    {
        ++hashi;
        hashi %= _tables.size();//++之后可能大于size,所以需要 模等一下
    }
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    ++_n;
    return true;
}


删除

//删除
bool Erase(const K& key)
{
    //由于直接删除该位置的值会引发后面的值的映射错误(会导致在找的时候提前找到空,所以不能直接删除,要使用伪删除法删除,即给一个DELETE状态)
    Data* ret = Find(key);
    if(ret)//找到值
    {
        //将该位置的值状态置为DELETE,然后n--
        ret->_state = DELETE;
        --_n;
        return true;//返回true表示删除成功
    }
    else//哈希表中没有该值,返回false
    {
        return false;
    }
}


查找

//查找
Data* Find(const K& key)
{
    //按照哈希函数的方式计算,得到哈希地址
    size_t hashi = Hash()(key) % _tables.size();
    //从该地址向后寻找,由于线性探测的问题,所以该地址不一定是实际存放要找的位置的值,所以需要继续向后找,直到遇到EMPTY为止
    while(_tables[hashi]._state != EMPTY)
    {
        if(_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)
            return &_tables[hashi];//找到了返回地址
        else//否则++hashi继续寻找
        {
            ++hashi;
            hashi %= _tables.size();
        }
    }
    return nullptr;//最终遇到EMPTY都没找到,返回空指针
}


相关文章
|
2月前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
53 2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
|
2月前
|
存储 C++ 容器
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器1
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
55 5
|
2月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
59 2
|
2月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
3月前
|
运维 Cloud Native Devops
云原生架构的崛起与实践云原生架构是一种通过容器化、微服务和DevOps等技术手段,帮助应用系统实现敏捷部署、弹性扩展和高效运维的技术理念。本文将探讨云原生的概念、核心技术以及其在企业中的应用实践,揭示云原生如何成为现代软件开发和运营的主流方式。##
云原生架构是现代IT领域的一场革命,它依托于容器化、微服务和DevOps等核心技术,旨在解决传统架构在应对复杂业务需求时的不足。通过采用云原生方法,企业可以实现敏捷部署、弹性扩展和高效运维,从而大幅提升开发效率和系统可靠性。本文详细阐述了云原生的核心概念、主要技术和实际应用案例,并探讨了企业在实施云原生过程中的挑战与解决方案。无论是正在转型的传统企业,还是寻求创新的互联网企业,云原生都提供了一条实现高效能、高灵活性和高可靠性的技术路径。 ##
219 3
|
2月前
|
程序员 C++ 开发者
C++入门教程:掌握函数重载、引用与内联函数的概念
通过上述介绍和实例,我们可以看到,函数重载提供了多态性;引用提高了函数调用的效率和便捷性;内联函数则在保证代码清晰的同时,提高了程序的运行效率。掌握这些概念,对于初学者来说是非常重要的,它们是提升C++编程技能的基石。
23 0
|
4月前
|
Linux 持续交付 虚拟化
在Linux中,Docker和容器虚拟概念是什么?
在Linux中,Docker和容器虚拟概念是什么?
|
4月前
|
消息中间件 Kubernetes 数据库
在k8S中,初始化容器(init container)概念原理是什么?
在k8S中,初始化容器(init container)概念原理是什么?
|
4月前
|
安全 编译器 容器
C++STL容器和智能指针
C++STL容器和智能指针
|
4月前
|
C++ 容器
C++中自定义结构体或类作为关联容器的键
C++中自定义结构体或类作为关联容器的键
42 0