哈希表的底层实现(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。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2