C++:哈希表

哈希表概念

哈希表可以简单理解为:把数据转化为数组的下标,然后用数组的下标对应的值来表示这个数据。如果我们想要搜索这个数据,直接计算出这个数据的下标,然后就可以直接访问数组对应的位置,所以可以用O(1)的复杂度直接找到数据。

其中,这个数据对应的数字叫做关键码(Key),这个把关键码转化为下标的规则,叫做哈希函数(Hash)

要注意的是,有一些数据并不是整型,比如字符串,对象等等。对于这种数据,我们要先用一套规则把它们转化为整数(关键码),然后再通过哈希函数映射为数组下标。


哈希函数

哈希函数原则:

  1. 哈希函数转换后,生成的地址(下标)必须小于哈希表的最大地址(下标)
  2. 哈希函数计算出来的地址(下标)必须均匀地分布
  3. 哈希函数尽可能简单
直接定址法

取关键字的某个线性函数为哈希表的地址:

除留余数法

假设哈希表的地址数目为m,取Keym取模后得到的值作为下标


闭散列 - 开放定址法

闭散列,也叫做开放定址法,当发生哈希冲突时,如果哈希表没有被装满,说明哈希表中还有空位置,那么我们可以把发生冲突的数据放到下一个空位置去。

基本结构

首先我们需要一个枚举,来标识哈希表的不同状态:

enum State
{
    EMPTY,
    EXIST,
    DELETE
};

EMPTY:空节点
EXIST:数值存在
DELETE:数值被删除 

哈希表的基本结构:

enum State
{
    EMPTY,
    EXIST,
    DELETE
};

template<class K, class V>
struct HashData
{
    pair<K, V> _kv;
    State _state = EMPTY;//标记状态
};

template<class K, class V>
class HashTable
{
public:
    HashTable(size_t size = 10)
    {
        _tables.resize(size);
    }

private:
    vector<HashData<K, V>> _tables;//哈希表
    size_t _n = 0;//元素个数
};

HashTable构造函数:

HashTable(size_t size = 10)
{
    _tables.resize(size);
}

查找

想要在哈希表中查找数据,无非就遵顼以下规则:

通过哈希函数计算出数据对应的地址
去地址处查找,如果地址处不是目标值,往后继续查找
遇到EMPTY还没有找到,说明数据不存在哈希表中
遇到DELETEEXIST,继续往后查找

代码如下:

HashData<K, V>* Find(const K& key)
{
    size_t hashi = key % _tables.size();

    while (_tables[hashi]._state != EMPTY)
    {
        if (_tables[hashi]._kv.first == key
            && _tables[hashi]._state == EXIST)
            return &_tables[hashi];

        hashi++;
        hashi %= _tables.size();
    }

    return nullptr;
}

但是当前的代码存在一个问题:哈希表作用于泛型,key % _tables.size()有可能是违法的行为,因为key可能不是一个数字。

对此我们可以在模板中多加一个仿函数的参数,用户可以在仿函数中自定义数据 -> 整型的转换规则,然后我们在对这个整型使用除留余数法获取地址。

在那之前,我们可以先写一个仿函数,用于处理整型 -> 整型的转化:

struct HashFunc
{
    size_t operator()(const K& key)
    {
        return (size_t)key;
    }
};

在STL中,整型-> 整型转化的函数,被写为了一个模板,而这个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& e : s)//把字符串的每一个字符ASCII码值加起来
        {
            hash += e;
            hash *= 131; // 31, 131313(任意由1,3间断排列的数字)
        }

        return hash;
    }
};

我们将这个HashFunc<K>仿函数作为哈希表的第三个模板参数的默认值:

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{};

通过仿函数来统一获得整型,再进行除留余数操作:

Hash hs;
size_t hashi = hs(key) % _tables.size();

插入

插入的基本逻辑如下:

  1. 先通过Find接口,查找目标值在不在哈希表中,如果目标值已经存在,返回flse,表示插入失败
  2. 通过哈希函数计算出目标值对应的下标
  3. 向下标中插入数据:如果下标对应的位置已经有数据,往后查找,直到某一个位置为EMPTY或者DELETE.如果下标对应的位置没有数据,直接插入
  4. 插入后,把对应位置的状态转化为EXIST

代码如下:

bool Insert(const pair<K, V>& kv)
{
    if (Find(kv.first))
        return false;

    Hash hs;//仿函数实例化出的对象
    size_t hashi = hs(kv.first) % _tables.size();//获得目标值对应的下标

    while (_tables[hashi]._state == EXIST)//往后查找合适的位置插入
    {
        hashi++;
        hashi %= _tables.size();
    }

    _tables[hashi]._kv = kv;//插入
    _tables[hashi]._state = EXIST;//改变状态
    _n++;//哈希表中的元素个数+1

    return true;
}

当这个哈希表越满,我们查找数据的效率就越低,甚至说:如果查找一个不存在的数据,我们可能要用O(N)的复杂度遍历整个哈希表.因此我们因该把哈希表的负载率控制在一定值,当超过一定值,我们就要进行扩容操作。

if ((double)_n / _tables.size() >= 0.7)
{
    size_t newSize = _tables.size() * 2;

    HashTable<K, V, Hash> newHT(newSize);

    for (auto& e : _tables)
    {
        if (e._state == EXIST)
            newHT.Insert(e._kv);
    }

    _tables.swap(newHT._tables);
}

插入总代码:

bool Insert(const pair<K, V>& kv)
{
    if (Find(kv.first))
        return false;

    if ((double)_n / _tables.size() >= 0.7)
    {
        size_t newSize = _tables.size() * 2;

        HashTable<K, V, Hash> newHT(newSize);

        for (auto& e : _tables)
        {
            if (e._state == EXIST)
                newHT.Insert(e._kv);
        }

        _tables.swap(newHT._tables);
    }

    Hash hs;
    size_t hashi = hs(kv.first) % _tables.size();

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

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

    return true;
}
删除

先通过Find接口找到要删除的值

  • 如果没找到,返回false,表示删除失败
  • 如果找到,把对应节点的状态改为DELETE

最后再把哈希表的_n - 1,表示存在的节点数少了一个。

代码如下:

bool Erase(const K& key)
{
    HashData<K, V>* ret = Find(key);
    if (ret)
    {
        ret->_state = DELETE;
        _n--;
        return true;
    }

    return false;
}

总代码展示

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& e : s)//把字符串的每一个字符ASCII码值加起来
        {
            hash += e;
            hash *= 131; // 31, 131313(任意由1,3间断排列的数字)
        }

        return hash;
    }
};

enum State
{
    EMPTY,
    EXIST,
    DELETE
};

template<class K, class V>
struct HashData
{
    pair<K, V> _kv;
    State _state = EMPTY;//标记状态
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
    HashTable(size_t size = 10)
    {
        _tables.resize(size);
    }

    HashData<K, V>* Find(const K& key)
    {
        Hash hs;
        size_t hashi = hs(key) % _tables.size();

        while (_tables[hashi]._state != EMPTY)
        {
            if (_tables[hashi]._kv.first == key
                && _tables[hashi]._state == EXIST)
                return &_tables[hashi];

            hashi++;
            hashi %= _tables.size();
        }

        return nullptr;
    }

    bool Insert(const pair<K, V>& kv)
    {
        if (Find(kv.first))
            return false;

        if ((double)_n / _tables.size() >= 0.7)
        {
            size_t newSize = _tables.size() * 2;

            HashTable<K, V, Hash> newHT(newSize);

            for (auto& e : _tables)
            {
                if (e._state == EXIST)
                    newHT.Insert(e._kv);
            }

            _tables.swap(newHT._tables);
        }

        Hash hs;
        size_t hashi = hs(kv.first) % _tables.size();

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

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

        return true;
    }

    bool Erase(const K& key)
    {
        HashData<K, V>* ret = Find(key);
        if (ret)
        {
            ret->_state = DELETE;
            _n--;
            return true;
        }

        return false;
    }

private:
    vector<HashData<K, V>> _tables;
    size_t _n = 0;//元素个数
};

开散列 - 哈希桶

在STL库中,采用的是更加优秀的开散列方案。

哈希表的数组vector中,不再直接存储数据,而是存储一个链表的指针。当一个数值映射到对应的下标后,就插入到这个链表中。其中每一个链表称为一个哈希桶,每个哈希桶中,存放着哈希冲突的元素.

基本结构

对于每一个节点,其要存储当前节点的值,也要存储下一个节点的指针,基本结构如下:

template<class K, class V>
struct HashNode
{
    HashNode<K, V>* _next;
    pair<K, V> _kv;

    HashNode(const pair<K, V>& kv)
        :_kv(kv)
        ,_next(nullptr)
    {}
};

哈希表:

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
    typedef HashNode<K, V> Node;
public:
    HashTable(size_t size = 10)
    {
        _tables.resize(size);
    }
    
private:
    vector<Node*> _tables; //链表指针数组
    size_t _n = 0;//元素个数
};

析构函数,防止内存泄漏:

~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;
    }
}
查找

查找的基本逻辑如下:

  1. 先通过哈希函数计算出数据对应的下标
  2. 通过下标找到对应的链表
  3. 遍历链表,找数据:如果某个节点的数据匹配上了,返回该节点指针,如果遍历到了nullptr,返回空指针表示没找到

代码如下:

Node* Find(const K& key)
{
    Hash hs;
    size_t hashi = hs(key) % _tables.size();

    Node* cur = _tables[hashi];
    while (cur)
    {
        if (cur->_kv.first == key)
            return cur;

        cur = cur->_next;
    }

    return nullptr;
}
插入

插入的基本逻辑如下:

  1. 先通过Find接口,查找目标值在不在哈希表中,如果目标值已经存在,返回flse,表示插入失败
  2. 通过哈希函数计算出目标值对应的下标
  3. 向下标中插入数据

代码如下:

bool Insert(const pair<K, V>& kv)
{
    if (Find(kv.first))
        return false;

    Hash hs;
    size_t hashi = hs(kv.first) % _tables.size();//计算下标
    Node* newNode = new Node(kv);//创建节点

    newNode->_next = _tables[hashi];//头插
    _tables[hashi] = newNode;

    ++_n;//更新元素个数
    return true;
}

关于扩容:如果我们单纯的进行插入,就要把原先的所有节点释放掉,再创建新的节点。这样会浪费很多时间。我们最好把原先创建的节点利用起来,因此我们要重写一个逻辑,把原先的节点进行迁移。 

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 = hs(cur->_kv.first) % newTables.size();
            cur->_next = newTables[hashi];
            newTables[hashi] = cur;

            cur = next;
        }

        _tables[i] = nullptr; //防止移交的节点被析构
    }

    _tables.swap(newTables);
}
删除

删除逻辑:

  1. 通过哈希函数计算出对应的下标
  2. 到对应的哈希桶中查找目标值
  • 如果找到,删除对应的节点
  • 如果没找到,返回false表示删除失败
  • _n - 1表示删除了一个元素

代码如下:

bool Erase(const K& key)
{
    Hash hs;
    size_t hashi = hs(key) % _tables.size();

    Node* prev = nullptr;
    Node* cur = _tables[hashi];
    while (cur)
    {
        if (cur->_kv.first == key)
        {
            if (prev)
                prev->_next = cur->_next;
            else
                _tables[hashi] = cur->_next;

            delete cur;
            --_n;
            return true;
        }

        prev = cur;
        cur = cur->_next;
    }

    return false;
}

代码展示

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& e : s)//把字符串的每一个字符ASCII码值加起来
        {
            hash += e;
            hash *= 131; // 31, 131313(任意由1,3间断排列的数字)
        }

        return hash;
    }
};

template<class K, class V>
struct HashNode
{
    HashNode<K, V>* _next;
    pair<K, V> _kv;

    HashNode(const pair<K, V>& kv)
        :_kv(kv)
        ,_next(nullptr)
    {}
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
    typedef HashNode<K, V> Node;
public:
    HashTable(size_t size = 10)
    {
        _tables.resize(size);
    }

    ~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;
        }
    }

    Node* Find(const K& key)
    {
        Hash hs;
        size_t hashi = hs(key) % _tables.size();

        Node* cur = _tables[hashi];
        while (cur)
        {
            if (cur->_kv.first == key)
                return cur;

            cur = cur->_next;
        }

        return nullptr;
    }

    bool Insert(const pair<K, V>& kv)
    {
        if (Find(kv.first))
            return false;

        Hash hs;

        //哈希桶情况下,负载因子到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 = hs(cur->_kv.first) % newTables.size();
                    cur->_next = newTables[hashi];
                    newTables[hashi] = cur;

                    cur = next;
                }

                _tables[i] = nullptr; //防止移交的节点被析构
            }

            _tables.swap(newTables);
        }

        size_t hashi = hs(kv.first) % _tables.size();
        Node* newNode = new Node(kv);

        newNode->_next = _tables[hashi];
        _tables[hashi] = newNode;

        ++_n;
        return true;
    }

    bool Erase(const K& key)
    {
        Hash hs;
        size_t hashi = hs(key) % _tables.size();

        Node* prev = nullptr;
        Node* cur = _tables[hashi];
        while (cur)
        {
            if (cur->_kv.first == key)
            {
                if (prev)
                    prev->_next = cur->_next;
                else
                    _tables[hashi] = cur->_next;

                delete cur;
                --_n;
                return true;
            }

            prev = cur;
            cur = cur->_next;
        }

        return false;
    }

private:
    vector<Node*> _tables; //链表指针数组
    size_t _n = 0;//元素个数
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/797918.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Dataset for Stable Diffusion

1.Dataset for Stable Diffusion 笔记来源&#xff1a; 1.Flickr8k数据集处理 2.处理Flickr8k数据集 3.Github&#xff1a;pytorch-stable-diffusion 4.Flickr 8k Dataset 5.dataset_flickr8k.json 6.About Train, Validation and Test Sets in Machine Learning Tarang Shah …

提升机器视觉与机器学习软件安全性的实践策略

在近几年科技爆发中&#xff0c;机器学习&#xff08;ML&#xff09;和机器视觉&#xff08;MV&#xff09;的结合正在改变各行各业。机器学习通过数据驱动的算法让计算机能够自我学习&#xff0c;而机器视觉赋予计算机识别和理解图像的能力。这种结合使得计算机可以高效地执行…

fastadmin后台无法删除文件,如何解决?

&#x1f3c6;本文收录于《CSDN问答解答》专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&…

牛客小白月赛98 (个人题解)(补全)

前言&#xff1a; 昨天晚上自己一个人打的小白月赛&#xff08;因为准备数学期末已经写烦了&#xff09;&#xff0c;题目难度感觉越来越简单了&#xff08;不在像以前一样根本写不了一点&#xff0c;现在看题解已经能看懂一点了&#xff09;&#xff0c;能感受到自己在不断进步…

智算网络谜题,与“解密者”新华三

根据高盛研究公司&#xff08;GSR&#xff09;数据报告显示&#xff0c;AIGC将推动全球国民生产总值&#xff08;GDP&#xff09;增长7%&#xff0c;带来近7万亿美元的GDP增长&#xff0c;并在未来使生产力提高1.5%。面对如此巨大的价值涌现&#xff0c;每个行业、每家企业都希…

JAVASE进阶day07(泛型,集合,Set,TreeSet,枚举,数据结构)

泛型 1.泛型的基本使用 限制集合存储的数据类型 package com.lu.day07.generics;/*** 定义了一个泛型类* E 泛型通配字母(不固定代替真实数据类型A-Z都可以)* 常见的泛型通配字母:* E:element 元素* T:type 类型* R:return 返回值类型* K:key 键* …

CV09_深度学习模块之间的缝合教学(4)--调参

深度学习就像炼丹。炉子就是模型&#xff0c;火候就是那些参数&#xff0c;材料就是数据集。 1.1 参数有哪些 调参调参&#xff0c;参数到底是哪些参数&#xff1f; 1.网络相关的参数&#xff1a;&#xff08;1&#xff09;神经网络网络层 &#xff08;2&#xff09;隐藏层…

SvANet:微小医学目标分割网络,增强早期疾病检测

SvANet&#xff1a;微小医学目标分割网络&#xff0c;增强早期疾病检测 提出背景前人工作医学对象分割微小医学对象分割注意力机制 SvANet 结构图SvANet 解法拆解解法逻辑链 论文&#xff1a;SvANet: A Scale-variant Attention-based Network for Small Medical Object Segmen…

PHP7.4安装使用rabbitMQ教程(windows)

&#xff08;1&#xff09;&#xff0c;安装rabbitMQ客户端erlang语言 一&#xff0c;erlang语言安装 下载地址1—— 下载地址2——https://www.erlang.org/patches/otp-27.0 二&#xff0c;rabbitMQ客户端安装 https://www.rabbitmq.com/docs/install-windows &#xff08…

Python+wxauto=微信自动化?

Pythonwxauto微信自动化&#xff1f; 一、wxauto库简介 1.什么是wxauto库 wxauto是一个基于UIAutomation的开源Python微信自动化库。它旨在帮助用户通过编写Python脚本&#xff0c;轻松实现对微信客户端的自动化操作&#xff0c;从而提升效率并满足个性化需求。这一工具的出现&…

【Linux】重定向 | 为什么说”一切皆文件?“

目录 前言 1.文件描述符分配规则 2.dup2 重定向接口 3.重定向 3.1>输出重定向 3.2>>追加重定向 3.3<输入重定向 3.4 shell 模拟实现< > 3.5 理解> 4. 理解“Linux 下一切皆文件” 前言 问&#xff1a;fd 为什么默认从 3 开始&#xff0c;而不是…

深度学习-6-自编码器和去噪自动编码器和变分自编码器

参考keras基于自编码器的语音信号降噪 参考今天来介绍一下什么是去噪自动编码器(DenoisingAutoencoder) 1 keras实现自编码器图像去噪 自编码器是一种简单的人工神经网络 (ANN),经过训练可以学习输入数据的编码表示,这种无监督机制不需要标签。自编码器由两个神经网络组…

【练习】分治--归并排序

&#x1f3a5; 个人主页&#xff1a;Dikz12&#x1f525;个人专栏&#xff1a;算法(Java)&#x1f4d5;格言&#xff1a;吾愚多不敏&#xff0c;而愿加学欢迎大家&#x1f44d;点赞✍评论⭐收藏 目录 归并排序 代码实现 交易逆序对的总数 题目描述 ​编辑 题解 代码实…

前端Vue组件化实践:打造灵活可维护的地址管理组件

随着前端技术的不断演进&#xff0c;复杂度和开发难度也随之上升。传统的一体化开发模式使得每次小小的修改或功能增加都可能牵一发而动全身&#xff0c;严重影响了开发效率和维护成本。组件化开发作为一种解决方案&#xff0c;通过模块化、独立化的开发方式&#xff0c;实现了…

云计算【第一阶段(29)】远程访问及控制

一、ssh远程管理 1.1、ssh (secureshell)协议 是一种安全通道协议对通信数据进行了加密处理&#xff0c;用于远程管理功能SSH 协议对通信双方的数据传输进行了加密处理&#xff0c;其中包括用户登录时输入的用户口令&#xff0c;建立在应用层和传输层基础上的安全协议。SSH客…

SQL 多变关联使用子查询去重

不去重状态 select a.*,b.recon_amt from free_settlement_first aleft join free_settlement_second b on a.settlement_first_id b.settlement_first_id 有2条数据出现了重复 使用子查询去重 select a.*,b.recon_amt from free_settlement_first aleft join free_settlem…

谈谈软件交互设计

谈谈软件交互设计 交互设计的由来 交互设计(Interaction Design)这一概念,最初是由IDEO创始人之一Bill.Moggridge(莫格里奇)1984年在一次会议上提出。他设计了世界上第一台笔记本电脑Compass,并写作出版了在交互设计领域影响深远的《Designing Interactions》一书,被称…

Azcopy Sync同步Azure文件共享

Azcopy Sync同步Azure文件共享 一、工作原理二、安装 AzCopy在 Windows 上在 Linux 上 三、资源准备1. 创建源和目标 Azure 存储账户2. 创建源和目标文件共享3. 确定路径4. 生成源和目的存储账户的共享访问签名&#xff08;SAS&#xff09;令牌配置权限示例生成的 URL 四、Azco…

AI算法14-套索回归算法Lasso Regression | LR

套索回归算法概述 套索回归算法简介 在统计学和机器学习中&#xff0c;套索回归是一种同时进行特征选择和正则化&#xff08;数学&#xff09;的回归分析方法&#xff0c;旨在增强统计模型的预测准确性和可解释性&#xff0c; 正则化是一种回归的形式&#xff0c;它将系数估…

课程的概述

课程概述 课程类型 课程理论流派 制约课程开发的因素 课程设计的概念及两种模式 课程内容 课程评价 新课程改革理念