哈希表的底层实现(1)---C++版

2024-09-09 06:28
文章标签 c++ 实现 哈希 底层

本文主要是介绍哈希表的底层实现(1)---C++版,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

哈希表的基本原理

哈希表的优点

哈希表的缺点

应用场景

闭散列法

开散列法

开放定值法Open Addressing——线性探测的模拟实现

超大重点部分评析

链地址法Separate Chaining——哈希桶的模拟实现


哈希表(Hash Table)是一种数据结构,它通过将键(Key)映射到值(Value)的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希函数,该函数用于将输入的键转换为哈希值(通常是一个整数),并根据这个哈希值将数据存储在数组中的特定位置。

哈希表的基本原理

  1. 哈希函数:这是哈希表的关键部分,它接收一个键并返回一个整数(哈希值)。理想情况下,哈希函数会将不同的键均匀地分布到数组的不同位置上。

  2. 数组(桶,Bucket):哈希表通常是基于数组实现的,哈希函数的输出决定了键值对应该存储在数组中的哪个位置。

  3. 处理冲突:由于不同的键可能会生成相同的哈希值(称为哈希冲突),需要有机制来处理这些冲突。常见的处理方式包括:

    • 链地址法(Separate Chaining):每个数组位置存储一个链表,所有哈希值相同的键值对都存储在同一个链表中。
    • 开放地址法(Open Addressing):当冲突发生时,查找数组中的下一个空闲位置存储键值对,常见的方式包括线性探测、二次探测和双重散列。
  4. 查找和插入:哈希表允许以 O(1) 的时间复杂度进行查找和插入操作(在理想情况下),即只需一次哈希函数计算和一次数组访问即可找到或插入数据。

哈希表的优点

  • 快速的查找、插入和删除:在平均情况下,哈希表的查找、插入和删除操作都是常数时间(O(1)),这使其非常高效。
  • 简单实现:哈希表相对容易实现,且不需要复杂的数据结构操作。

哈希表的缺点

  • 空间浪费:如果哈希表的负载因子(存储的元素数量与数组大小的比值)较高,容易导致冲突增加,从而降低性能。为避免冲突,通常会使用更大的数组,这会导致空间浪费。
  • 无法有序遍历:哈希表中的数据是无序的,如果需要顺序访问数据,需要额外的处理。
  • 哈希函数质量:哈希表的性能高度依赖于哈希函数的质量,差劲的哈希函数可能导致较多的冲突。

应用场景

哈希表在许多场景中广泛使用,包括但不限于:

  • 字典实现:例如,Python 中的字典(dict)就是通过哈希表实现的。
  • 缓存:哈希表常用于实现缓存机制,如 LRU 缓存。
  • 集合操作:例如,在查找某个元素是否在集合中时,哈希表可以显著提高效率。
  • 位图:
  • 布隆过滤器:

通过哈希表,可以在大型数据集上快速执行查找、插入和删除操作,这使得它在实际应用中非常实用。

所以依照哈希表的基本原理可以看出哈希表的底层结构可以分为以下两种,这两种方法的本质都是除留余数法:

闭散列法

闭散列法也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有 空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置 呢? 比如2.1中的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,hashAddr为4, 因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

插入: 通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突, 使用线性探测找到下一个空位置,插入新元素。

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

上面有一个名词为线性探测,就是当待插入元素出现哈希冲突时,一个一个往下寻找空位置称为线性探测,每次n的固定次方倍往下找称为二次探测,两种探测的本质解决的问题完全一致,所有我们就只使用线性探测进行实现。

开散列法

开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地 址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链 接起来,各链表的头结点存储在哈希表中。代码总体实现的功能和上面的闭散列法差不多。

从上图可以看出,开散列中每个桶中放的都是发生哈希冲突的元素。

开放定值法Open Addressing——线性探测的模拟实现

#include<iostream>
#include<vector>
using namespace std;

//namespace hashbucket//包一个命名空间就可以调用了
//{

    template<class K>
    struct Hashfunc
    {
        size_t operator()(const K& key)
        {
            return (size_t)key;
//由于像当K为string时不可以直接强制转换成整型,所以如果哈希表需要插入string类型的数据就需要写string的特化版本,如下
        }
    };
    
//struct StringHashFunc
    //{
    //    size_t operator()(const string& s)
    //    {
    //        size_t hash = 0;
    //        for (auto e : s)
    //        {
    //            hash *= 31;
    //            hash += e;
    //        }
    //
    //        return hash;
    //    }
    //};

    template<>
    struct Hashfunc<string>
//可以直接在这里写,模板的特化前提是前面有写过了,且名称一样,遇到和特化吻合的会优先匹配特化版本
    {
        size_t operator()(const string& key)
        {
            size_t hash = 0;
            for (auto e : key)
            {
                hash += e;
                hash *= 31;
//根据某篇文章可得多乘31可以有效避免很多重复
            }
            return hash;
        }
    };
    enum status
    {
        EXIST,
        EMPTY,
        DELETE
//三个状态,这里定义了哈希表中的数据的多个状态,在红黑树的模拟实现中有用过,这样方便判断此位置的数据状态,方便以后的线性探测和删除数据等
    };

    template<class K, class V>
    struct Hashdata
    {
        pair<K, V> _kv;
        status s = EMPTY;
//刚开始时所有空位的状态都是EMPTY
    };


    template<class K, class V, class Hash = Hashfunc<K>>
    class Hashtable
    {
    public:
        Hashtable()
        {
            _table.resize(10);
//直接在初始化时开10个空间
        }
        Hash ha;
//仿函数
        bool insert(const pair<K, V>& kv)
        {
            if (Find(kv.first))
            {
                return false;
            }
            if (10 * n / _table.size() >= 7)
            {
                
//vector<HashData<K, V>> newTables(_tables.size() * 2);
                 遍历旧表, 将所有数据映射到新表
                 ...
                //_tables.swap(newTables);
                //以上方法无法复用insert

                Hashtable<K, V, Hash> newht;//是KV
                newht._table.resize(2 * _table.size());//_table肯定是类里的,不然要指定的
                for (int i = 0; i < _table.size(); i++)
                {
                    newht.insert(_table[i]._kv);
//复用
                }
                _table.swap(newht._table);
//交换
            }
            size_t hashi = ha(kv.first) % _table.size();
//非整型不能取%,所以使用仿函树转换一下
            while (_table[hashi].s == EXIST)
            {
                hashi++;
                hashi %= _table.size();
//hashi不断的++的时候有可能会超出整个vector的数据的长度,所以需要再%_table.size()使其处在最后时下一步回到数据的开头,所以可以看出hashi是不断循环的。
            }
            _table[hashi]._kv = kv;
            _table[hashi].s = EXIST;
            n++;
//每成功插入一个数据,其负载因子就加1
            return true;
        }
        vector<Hashdata<K, V>>* begin() const
        {
            return &_table[0];
        }

        vector<Hashdata<K, V>>* end() const
        {
            return &_table[_table.size()];
        }
        Hashdata<K, V>* Find(const K& key)
        {
            size_t hashi = ha(key) % _table.size();
            size_t n = hashi;
            while (_table[hashi].s != DELETE)
            {
                if (_table[hashi]._kv.first == key && _table[hashi].s == EXIST)
//由于下面的删除逻辑为不删除数据只改名数据的状态所以当找到相等时,这个数据有可能会有两种状态:EXIST和DELETE
                {
                    return &_table[hashi];
                }
                hashi++;
                hashi = hashi % _table.size();
                if (hashi == n)
                {
                    return nullptr;
                }
            }
            return nullptr;
        }

        bool Erase(const K& key)//只要传一个K就可以了
        {
            Hashdata<K, V>* ret = Find(key);
            if (ret)
            {
                ret->s == DELETE;
                return true;
            }
            return false;
        }
    private:
        vector<Hashdata<K, V>> _table;
        size_t n = 0;
//表中存储数据个数, n为负载因子
    };

    
//}

超大重点部分评析

这边说一下扩容的逻辑,由于插入逻辑里面hashi是不断循环的,所以当哈希表里面数据都占满时,hashi会陷入死循环,但是就算没有全部占满,如果已占数据过多就会使得下一个数据在插入时哈希冲突过多使时间复杂度变大,所以为了避免这种情况,引入负载因子,当插入数据占比>=百分之70时,也就是负载因子/空间数据容纳最大个数 == 0.7时,将容器的容量扩大成原来的双倍。

再观察上面的扩容代码,为什么不能直接再原空间之间扩容呢,需要另开一个空间再交换回去,因为如果之间在原空间扩容,会使得size(数据最大个数)变大使得原本的数据的映射乱了。像现在这种扩容写法交换swap之后,由于新创建的临时变量newht出函数体就会销毁了,也就会顺带释放掉swap交给它的原空间,这样扩容之后的空间就保留下来了,所以不需要考虑旧表没有被释放的问题。

最后注意一下这个Erase的写法,很多人可能会认为删除某个元素需要像之前顺序表的那种写法(毕竟每个数据就在顺序表里面),删除了这个数据,让这个数据后面的数据依次往前移,时间复杂度就是O(n),这里不是不可以,但是如果你这么写就麻烦了,因为每个数据都外带了一个数据状态,按顺序表那么写的话就忽略的状态这个东西。

链地址法Separate Chaining——哈希桶的模拟实现

预知后事如何,请持续关注本系列内容!!!

这篇关于哈希表的底层实现(1)---C++版的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1150411

相关文章

Redis客户端连接机制的实现方案

《Redis客户端连接机制的实现方案》本文主要介绍了Redis客户端连接机制的实现方案,包括事件驱动模型、非阻塞I/O处理、连接池应用及配置优化,具有一定的参考价值,感兴趣的可以了解一下... 目录1. Redis连接模型概述2. 连接建立过程详解2.1 连php接初始化流程2.2 关键配置参数3. 最大连

Python实现网格交易策略的过程

《Python实现网格交易策略的过程》本文讲解Python网格交易策略,利用ccxt获取加密货币数据及backtrader回测,通过设定网格节点,低买高卖获利,适合震荡行情,下面跟我一起看看我们的第一... 网格交易是一种经典的量化交易策略,其核心思想是在价格上下预设多个“网格”,当价格触发特定网格时执行买

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法:临时设置(Windows用`set`,Linux/macOS用`export`)、永久设置(系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量(适用于当前会话)永久设置环境变量(Windows系统

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发;同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali

Spring Security 单点登录与自动登录机制的实现原理

《SpringSecurity单点登录与自动登录机制的实现原理》本文探讨SpringSecurity实现单点登录(SSO)与自动登录机制,涵盖JWT跨系统认证、RememberMe持久化Token... 目录一、核心概念解析1.1 单点登录(SSO)1.2 自动登录(Remember Me)二、代码分析三、

PyCharm中配置PyQt的实现步骤

《PyCharm中配置PyQt的实现步骤》PyCharm是JetBrains推出的一款强大的PythonIDE,结合PyQt可以进行pythion高效开发桌面GUI应用程序,本文就来介绍一下PyCha... 目录1. 安装China编程PyQt1.PyQt 核心组件2. 基础 PyQt 应用程序结构3. 使用 Q

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF(BinaryLoggingFormat)作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析:从文件遍历到数据导出1. 环境准备与依赖库

linux下shell脚本启动jar包实现过程

《linux下shell脚本启动jar包实现过程》确保APP_NAME和LOG_FILE位于目录内,首次启动前需手动创建log文件夹,否则报错,此为个人经验,供参考,欢迎支持脚本之家... 目录linux下shell脚本启动jar包样例1样例2总结linux下shell脚本启动jar包样例1#!/bin