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

相关文章

windos server2022里的DFS配置的实现

windos server2022里的DFS配置的实现

《windosserver2022里的DFS配置的实现》DFS是WindowsServer操作系统提供的一种功能,用于在多台服务器上集中管理共享文件夹和文件的分布式存储解决方案,本文就来介绍一下wi... 目录什么是DFS？优势：应用场景：DFS配置步骤什么是DFS？DFS指的是分布式文件系统（Distr
阅读更多...
NFS实现多服务器文件的共享的方法步骤

NFS实现多服务器文件的共享的方法步骤

《NFS实现多服务器文件的共享的方法步骤》NFS允许网络中的计算机之间共享资源,客户端可以透明地读写远端NFS服务器上的文件,本文就来介绍一下NFS实现多服务器文件的共享的方法步骤,感兴趣的可以了解一... 目录一、简介二、部署1、准备1、服务端和客户端：安装nfs-utils2、服务端：创建共享目录3、服
阅读更多...
C#使用yield关键字实现提升迭代性能与效率

C#使用yield关键字实现提升迭代性能与效率

《C#使用yield关键字实现提升迭代性能与效率》yield关键字在C#中简化了数据迭代的方式,实现了按需生成数据,自动维护迭代状态,本文主要来聊聊如何使用yield关键字实现提升迭代性能与效率,感兴... 目录前言传统迭代和yield迭代方式对比yield延迟加载按需获取数据yield break显式示迭
阅读更多...
Python实现高效地读写大型文件

Python实现高效地读写大型文件

《Python实现高效地读写大型文件》Python如何读写的是大型文件,有没有什么方法来提高效率呢,这篇文章就来和大家聊聊如何在Python中高效地读写大型文件,需要的可以了解下... 目录一、逐行读取大型文件二、分块读取大型文件三、使用 mmap 模块进行内存映射文件操作（适用于大文件）四、使用 pand
阅读更多...
python实现pdf转word和excel的示例代码

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1，PDF转Word2，PDF转Excel三、前端页面效果展示总结一
阅读更多...
Python xmltodict实现简化XML数据处理

Python xmltodict实现简化XML数据处理

《Pythonxmltodict实现简化XML数据处理》Python社区为提供了xmltodict库,它专为简化XML与Python数据结构的转换而设计,本文主要来为大家介绍一下如何使用xmltod... 目录一、引言二、XMLtodict介绍设计理念适用场景三、功能参数与属性1、parse函数2、unpa
阅读更多...
C#实现获得某个枚举的所有名称

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi
阅读更多...
Go语言实现将中文转化为拼音功能

Go语言实现将中文转化为拼音功能

《Go语言实现将中文转化为拼音功能》这篇文章主要为大家详细介绍了Go语言中如何实现将中文转化为拼音功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 有这么一个需求：新用户入职 创建一系列账号比较麻烦，打算通过接口传入姓名进行初始化。想把姓名转化成拼音。因为有些账号即需要中文也需要英
阅读更多...
C# 读写ini文件操作实现

C# 读写ini文件操作实现

《C#读写ini文件操作实现》本文主要介绍了C#读写ini文件操作实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录一、INI文件结构二、读取INI文件中的数据在C#应用程序中，常将INI文件作为配置文件，用于存储应用程序的
阅读更多...
C#实现获取电脑中的端口号和硬件信息

C#实现获取电脑中的端口号和硬件信息

《C#实现获取电脑中的端口号和硬件信息》这篇文章主要为大家详细介绍了C#实现获取电脑中的端口号和硬件信息的相关方法,文中的示例代码讲解详细,有需要的小伙伴可以参考一下... 我们经常在使用一个串口软件的时候，发现软件中的端口号并不是普通的COM1，而是带有硬件信息的。那么如果我们使用C#编写软件时候，如
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2