为您推荐:
精华内容
最热下载
问答
  • 5星
    40KB weixin_51194902 2021-01-08 12:19:19
  • 一般用哈希表或二叉树存储 HashMap, HashSet, TreeMap, TreeSet 区别: HashMap/HashSet :查询的时间复杂度为O(1);乱序 TreeMap/TreeSet:查询的时间复杂度为O(log(n));排好序的 https://leetcode

    Map(映射)和Set(集合)

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    list:可重复,插入时间复杂度O(1),查询时间复杂度O(n);一般用数组或链表存储。
    map:key-value;
    set:不重复元素,查询时间为O(1)或O(log(n));一般用哈希表或二叉树存储

    HashMap, HashSet, TreeMap, TreeSet

    在这里插入图片描述
    区别:
    HashMap/HashSet :查询的时间复杂度为O(1);乱序
    TreeMap/TreeSet:查询的时间复杂度为O(log(n));排好序的

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    https://leetcode-cn.com/problems/valid-anagram/
    C++ 三种方法:1.直接用sort函数 2.map计数 3.效率最高

    class Solution {
    public:
        bool isAnagram(string s, string t) {
            sort(s.begin(),s.end());
            sort(t.begin(),t.end());
            return s==t;
        }
    };
    
    class Solution {
    public:
        bool isAnagram(string s, string t) {
            unordered_map<char,int> map;
            if (s.size() != t.size()) 
                return false;
            for(int i=0;i<s.size();i++){
                ++map[s[i]];
                --map[t[i]];
            }  
            for(unordered_map<char,int>::iterator it=map.begin();it!=map.end();it++){
                if(it->second!=0)
                    return false;
            }
            return true;
            
        }
    };
    
    class Solution {
    public:
        bool isAnagram(string s, string t) {
            int num[26]={0}; 
            if(s.length()!=t.length())
                return false;
            for(int i=0;s[i]!='\0';i++){
                num[s[i]-'a']++;
                num[t[i]-'a']--;
               
            }
            for(int i=0;i<26;i++)
                if(num[i]!=0)
                    return false;
            return true;
        }
    };
    

    在这里插入图片描述https://leetcode-cn.com/problems/two-sum/

    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            unordered_map<int, int> hashtable;
            for (int i = 0; i < nums.size(); ++i) {
                auto it = hashtable.find(target - nums[i]);
                if (it != hashtable.end()) {
                    return {it->second, i};
                }
                hashtable[nums[i]] = i;
            }
            return {};
        }
    };
    

    在这里插入图片描述
    https://leetcode-cn.com/problems/3sum/

    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            int n = nums.size();
            sort(nums.begin(), nums.end());
            vector<vector<int>> ans;
            // 枚举 a
            for (int first = 0; first < n; ++first) {
                // 需要和上一次枚举的数不相同
                if (first > 0 && nums[first] == nums[first - 1]) {
                    continue;
                }
                // c 对应的指针初始指向数组的最右端
                int third = n - 1;
                int target = -nums[first];
                // 枚举 b
                for (int second = first + 1; second < n; ++second) {
                    // 需要和上一次枚举的数不相同
                    if (second > first + 1 && nums[second] == nums[second - 1]) {
                        continue;
                    }
                    // 需要保证 b 的指针在 c 的指针的左侧
                    while (second < third && nums[second] + nums[third] > target) {
                        --third;
                    }
                    // 如果指针重合,随着 b 后续的增加
                    // 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
                    if (second == third) {
                        break;
                    }
                    if (nums[second] + nums[third] == target) {
                        ans.push_back({nums[first], nums[second], nums[third]});
                    }
                }
            }
            return ans;
        }
    };
    
    展开全文
    m0_37761144 2021-04-27 16:26:07
  •     最近在刷题以及做编程练习的作业时经常会用到哈希表,碰到一些想用的函数时每次都看别人的博客,现结合别人的博客对哈希表做个总结。 本篇哈希表的作用如何使用STL库中的哈希表STL中哈希表的常用函数 哈希表...

        最近在刷题以及做编程练习的作业时经常会用到哈希表,碰到一些想用的函数时每次都看别人的博客,现结合别人的博客对哈希表做个总结。

    1. 哈希表的定义

    (1)哈希表的作用
        哈希表就是在关键字和存储位置之间建立对应关系,使得元素的查找可以以O(1)的效率进行, 其中关键字和存储位置之间是通过散列函数建立关系,记为: L o c ( i ) = H a s h ( k e y i ) 。 Loc(i) = Hash(key_i)。 Loc(i)=Hash(keyi)
    关键字和存储地址之间的对应关系
    (2) 常见的散列函数
        1)线性定址法:直接取关键字的某个线性函数作为存储地址,散列函数为: H a s h ( k e y ) = a × k e y + b Hash(key) = a × key + b Hash(key)=a×key+b
        2)除留余数法:将关键字对某一小于散列表长度的数p取余的结果作为存储地址,散列函数为: H a s h ( k e y ) = k e y    m o d    p Hash(key) = key \;mod \; p Hash(key)=keymodp
        3)平方取中法:对关键字取平方,然后将得到结果的中间几位作为存储地址;
        4)折叠法:将关键字分割为几部分,然后将这几部分的叠加和作为存储地址。

    (3) 地址冲突解决方法
        通过以上方法构建的哈希表在理想的情况下能够做到一个关键字对应一个地址,但是实际情况是会有冲突发生,也就是散列函数会将多个关键字映射到同一个地址上。以下是一些解决冲突的方法:
      1)开放地址法:
        ①线性探测法:当发生冲突时,就顺序查看下一个存储位置,如果位置为空闲状态,就将该关键字存储在该位置上,如果还是发生冲突,就依次往后查看,当查看到存储空间的末尾时还是找不到空位置,就返回从头开始查看;
    在这里插入图片描述
        ②平方探测法:不同于前面线性探测法依次顺序查看下一个位置是否能存储元素,平方探测的规则是以 1 2 , − 1 2 , 2 2 , − 2 2 , . . . , 1^2, -1^2, 2^2, -2^2,..., 12,12,22,22,...探测新的存储位置能否存储元素;
        ③再散列法:利用两个散列函数,当通过第一个散列函数得到关键字的存储地址发生冲突时,再利用第二个散列函数计算出地址增量,地址计算方式如下:
    H i = ( H a s h 1 ( k e y ) + i ∗ H a s h 2 ( k e y ) ) % p H_i = (Hash_1(key)+i*Hash_2(key))\%p Hi=(Hash1(key)+iHash2(key))%p
        ④伪随机数法: 当发生地址冲突时,加入一个随机数作为地址增量寻找新的存储地址,地址计算方式如下:
    H i = ( H a s h ( k e y ) + d i ) % p ,    其 中 d i 为 随 机 数 H_i = (Hash(key)+d_i)\%p, \;其中d_i为随机数 Hi=(Hash(key)+di)%p,di
      2)拉链法
        将具有相同存储地址的关键字链成一单链表, m个存储地址就设m个单链表,然后用一个数组将m个单链表的表头指针存储起来,形成一个动态的结构,假设散列函数为 Hash(key) = key %13,其拉链存储结构为:

    在这里插入图片描述

    2. 如何使用STL库中的哈希表

    (1)导入头文件
      #include<unordered_map>
    (2)哈希表的声明和初始化
        1)声明

    unordered_map<elemType_1, elemType_2> var_name; //声明一个没有任何元素的哈希表,
    //其中elemType_1和elemType_2是模板允许定义的类型,如要定义一个键值对都为Int的哈希表:
    unordered_map<int, int> map;
    

        2)初始化
        以上在声明哈希表的时候并没有给unordered_map传递任何参数,因此调用的是unordered_map的默认构造函数,生成一个空容器。初始化主要有一下几种方式:
         a)在定义哈希表的时候通过初始化列表中的元素初始化:

    unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
    //如果知道要创建的哈希表的元素个数时,也可以在初始化列表中指定元素个数
    unordered_map<int, int> hmap{ {{1,10},{2,12},{3,13}},3 };
    

         b)通过下标运算来添加元素:

    //当我们想向哈希表中添加元素时也可以直接通过下标运算符添加元素,格式为: mapName[key]=value;
    //如:hmap[4] = 14;
    //但是这样的添加元素的方式会产生覆盖的问题,也就是当hmap中key为4的存储位置有值时,
    //再用hmap[4]=value添加元素,会将原哈希表中key为4存储的元素覆盖
    hmap[4] = 14;
    hmap[5] = 15;
    cout << hmap[4];  //结果为15
    

         c)通过insert()函数来添加元素:

    //通过insert()函数来添加元素的结果和通过下标来添加元素的结果一样,不同的是insert()可以避免覆盖问题,
    //insert()函数在同一个key中插入两次,第二次插入会失败
    hmap.insert({ 5,15 });
    hmap.insert({ 5,16 });
    cout << hmap[5];  //结果为15
    

         d)复制构造,通过其他已初始化的哈希表来初始新的表:

    unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
    unordered_map<int, int> hmap1(hmap);
    

    3. STL中哈希表的常用函数

    (1) begin( )函数:该函数返回一个指向哈希表开始位置的迭代器

    unordered_map<int, int>::iterator iter = hmap.begin(); //申请迭代器,并初始化为哈希表的起始位置
    cout << iter->first << ":" << iter->second;
    

    (2) end( )函数:作用于begin函数相同,返回一个指向哈希表结尾位置的下一个元素的迭代器

    unordered_map<int, int>::iterator iter = hmap.end();
    

    (3) cbegin() 和 cend():这两个函数的功能和begin()与end()的功能相同,唯一的区别是cbegin()和cend()是面向不可变的哈希表

    const unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
    unordered_map<int, int>::const_iterator iter_b = hmap.cbegin(); //注意这里的迭代器也要是不可变的const_iterator迭代器
    unordered_map<int, int>::const_iterator iter_e = hmap.cend();
    

    (4) empty()函数:判断哈希表是否为空,空则返回true,非空返回false

    bool isEmpty = hmap.empty();
    

    (5) size()函数:返回哈希表的大小

    int size = hmap.size();
    

    (6) erase()函数: 删除某个位置的元素,或者删除某个位置开始到某个位置结束这一范围内的元素, 或者传入key值删除键值对

    unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
    unordered_map<int, int>::iterator iter_begin = hmap.begin();
    unordered_map<int, int>::iterator iter_end = hmap.end();
    hmap.erase(iter_begin);  //删除开始位置的元素
    hmap.erase(iter_begin, iter_end); //删除开始位置和结束位置之间的元素
    hmap.erase(3); //删除key==3的键值对
    

    (7) at()函数:根据key查找哈希表中的元素

    unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
    int elem = hmap.at(3);
    

    (8) clear()函数:清空哈希表中的元素

    hmap.clear()
    
    (9) find()函数:以key作为参数寻找哈希表中的元素,如果哈希表中存在该key值则返回该位置上的迭代器,否则返回哈希表最后一个元素下一位置上的迭代器
    unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
    unordered_map<int, int>::iterator iter;
    iter = hmap.find(2); //返回key==2的迭代器,可以通过iter->second访问该key对应的元素
    if(iter != hmap.end())  cout << iter->second;
    

    (10) bucket()函数:以key寻找哈希表中该元素的储存的bucket编号(unordered_map的源码是基于拉链式的哈希表,所以是通过一个个bucket存储元素)

    int pos = hmap.bucket(key);
    

    (11) bucket_count()函数:该函数返回哈希表中存在的存储桶总数(一个存储桶可以用来存放多个元素,也可以不存放元素,并且bucket的个数大于等于元素个数)

    int count = hmap.bucket_count();
    

    (12) count()函数: 统计某个key值对应的元素个数, 因为unordered_map不允许重复元素,所以返回值为0或1

    int count = hmap.count(key);
    

    (13) 哈希表的遍历: 通过迭代器遍历

    unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
    unordered_map<int, int>::iterator iter = hmap.begin();
    for( ; iter != hmap.end(); iter++){
     cout << "key: " <<  iter->first  << "value: " <<  iter->second <<endl;
    }
    
    展开全文
    Peealy 2021-05-16 16:41:34
  • 哈希表(哈希查找) ​ 前面对于顺序表进行查找时,在判断当前数据是否是要查找的数据时,需要去通过“=”来进行判断,直到有了相等的关键字才返回地址。在这种查找方式中,“比较”是必不可免的,那么是否有一种...

    哈希表(哈希查找)

    ​ 前面对于顺序表进行查找时,在判断当前数据是否是要查找的数据时,需要去通过“=”来进行判断,直到有了相等的关键字才返回地址。在这种查找方式中,“比较”是必不可免的,那么是否有一种方法可以避免比较,即通过关键字的某种形式来存储该数据的地址,这样在查找时,将待查询的关键字通过一定计算就可以得到目的数据的地址。

    哈希表概念

    哈希表,也被称为散列表,就是应用了上述的存储方法,即在查找某个数据时,直接通过关键字计算数据存放的地址,然后直接访问。它在关键字与存储位置之间建立了一个映射。

    ​ 根据上述定义,其实也可以理解为关键字与存储地址存在一个函数关系,这个函数就被称为哈希函数。

    ​ 哈希函数在记录的关键字与记录的存储地址之间建立一种对应关系,可以写成以下形式:
    a d d r ( d a t a i ) = H ( k e y i ) addr\left( data_i \right) =H\left( key_i \right) addr(datai)=H(keyi)
    ​ 其中, H ( . ) H(.) H(.)是哈希函数, k e y i key_i keyi是元素 d a t a i data_i datai的关键字, a d d r ( d a t a i ) addr(data_i) addr(datai)是元素 d a t a i data_i datai的存储地址。

    ​ 在有了上述工具之后,就可以使用哈希表来辅助进行查找。哈希查找也被称为散列查找,是利用哈希函数继续宁查找的过程。过程也十分简单,首先利用哈希函数及记录的关键字计算出记录的存储地址,然后直接到指定地址进行查找。整个过程不需要经过比较,一次存取就能得到所查元素。

    ​ 查找过程虽然简单,但是还是会存在问题,那就是不同的记录,其关键字通过哈希函数的计算,可能会得到相同的地址。这个问题是十分常见的,把不同的记录映射到同一个散列地址上,这种现象被称为冲突。在哈希表中同样也有解决冲突的办法,具体要结合对应的哈希函数来进行解决。

    哈希函数构造方法

    根据设定的哈希函数 H(key) 和所选中的处理冲突的方法将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上并以关键字在地址集中的“象”作为相应记录在表中的存储位置如此构造所得的查找表称之为“哈希表”

    ​ 在一个哈希表中,如何选择一个好的哈希函数是最为重要的一件事情。

    哈希函数实现的一般是从一个大的集合(部分元素,空间位置上一般不连续)到一个小的集合(空间连续)的映射。

    ​ 一个好的哈希函数,对于记录中的任何关键字,将其映射到地址集合中任何一个地址的概率应该是相等的。即关键字经过哈希函数得到一个“随机的地址”。

    ​ 所以对于一个哈希函数来说,有以下几个要求:

    1. 哈希函数应是简单的,能在较短的时间内计算出结果。
    2. 哈希函数的定义域尽可能包括需要存储的全部关键字,如果散列表允许有 m m m 个地址时,其值域必须在 0 到 m − 1 m-1 m1之间。
    3. 散列函数计算出来的地址应能均匀分布在整个地址空间中。

    接下来就对一些常用的哈希函数进行学习。

    直接定址法

    ​ 直接定址法中,哈希函数取关键字的线性函数,即
    H ( k e y ) = a ⋅ k e y + b H\left( key \right) =a\cdot key+b H(key)=akey+b
    其中 a a a b b b都是常数。

    ​ 直接定址法思路比较简单,直接使用一个单调的一次函数来作为哈希函数。这里给出一个例子,如下所示。
    在这里插入图片描述

    这样的散列表的有点在于比较简单,均匀,也不会产生冲突,但是问题也很明显,就是需要事先知道关键字的分布情况,适合查找表较小且连续的情况,由于这样的限制,在现实应用中,此方法虽然简单,但是并不常用。

    数字分析法

    ​ 数字分析法主要是提取出所有关键字中,可以用于区分每个关键字的部分当作哈希函数。

    ​ 假设关键字集合中每个关键字都是由 s s s位数组组成 ( u 1 , u 2 , . . . , u s ) (u_1,u_2,...,u_s) (u1,u2,...,us),数字分析法就是分析关键字集中的全体,从中提取出分布均匀的若干位或它们的组合作为地址。

    ​ 接下来通过一个例子对数字分析法进行进一步理解。
    在这里插入图片描述

    ​ 如上所示,对于该关键字,只需要采用4567列中任意两列和另两位的叠加作为哈希地址即可,即可唯一识别一个记录,且分布较为均匀。

    ​ 数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字分布较均匀,则可以考虑使用这个办法。

    ​ 数字分析法完全依赖于关键码集合,如果换一个关键码集合,选择哪几位作为哈希地址就需要重新决定。

    平方取中法

    ​ 平方取中法,顾名思义,就是将关键字的平方值的中间几位取出作为存储地址。

    ​ 这里之所以要用关键字的平方主要是为了扩大差别,同时平方值的中间各位又能收到整个关键字中各位的影响。

    ​ 接下来通过一个例子对平方取中法进行理解。
    在这里插入图片描述

    ​ 平方取中法是较为常用的构造哈希函数的方法,适合于关键字中每一位都有某些数字重复出现且频度很高的情况,中间所取的位数,由哈希表长决定。

    折叠法

    ​ 折叠法就是将关键字分割成位数相同的若干部分(最后部分的倍数可以不同),然后取它们的叠加和(舍去进位)为哈希地址。其实叠加简单分为两种:

    1. 移位叠加:将分割后的几部分低位对齐相加。
    2. 间界叠加:从一端沿分割界来回折送,然后对齐相加。

    接下来通过一个例子对于折叠法进行理解。
    在这里插入图片描述

    ​ 折叠法适合于关键字的数字位数特别多,而且每一位上数字分布大致均匀的情况。

    除留余数法

    ​ 除留余数法是最常用的一种构造哈希函数的方法。除留余数法的做法是取关键字被某个不大于哈希表长 m m m的数 p p p除后所得余数为哈希地址
    H ( k e y ) = k e y    M O D    p H\left( key \right) =key\,\,MOD\,\,p H(key)=keyMODp
    其中 m m m为哈希表长, p p p为不大于 m m m的素数或是不含20以下质因子的合数,且 p ⩽ m p \leqslant m pm

    ​ 接下来通过一个例子来对该方法进行理解。
    在这里插入图片描述

    从上述例子中也可以看出,除留余数法并不能确保每个关键字的哈希函数值都是不同的,这也就会增加“冲突”的可能。

    处理冲突

    ​ 处理冲突的实际含义是:为产生冲突的地址寻找下一个哈希地址。在构建哈希表的时候,如果有两个关键字的哈希函数值相同,也就代表这两个关键字应该放的位置相同,但是这样是明显不可取的,因为一个位置只能放一个数据。那么在后面一个数据想要放在已经放数据的位置上时,只能重新找一个空闲的位置进行放置了。而这个重新找空闲位置的过程,就是处理冲突的过程。

    开放定址法

    ​ 所谓的开放定址法,就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。

    ​ 开放定址法在遇到重复的地址时,为产生冲突的地址 H ( k e y ) H(key) H(key)求得一个地址序列: H 0 , H 1 , . . . , H s , 1 ⩽ s ⩽ m H_0,H_1,...,H_s,1\leqslant s \leqslant m H0,H1,...,Hs,1sm,其中每地址的计算公式如下所示。
    H i = ( H ( k e y ) + d i )    M O D    m , i = 1 , . . . , s H_i=\left( H\left( key \right) +d_i \right) \,\,MOD\,\,m, i=1,...,s Hi=(H(key)+di)MODm,i=1,...,s
    其中 H ( k e y ) H(key) H(key)为哈希函数, m m m为哈希表长。根据其中 d i d_i di的取法可以简单讲开放定址法分为两种,即线性探测和二次探测。

    线性探测

    d i = 1 , 2 , 3 , . . . , m − 1 d_i=1,2,3,...,m-1 di=1,2,3,...,m1时,称这种开放定址法为线性探测再散列。

    接下来通过一个例子来对线性探测进行理解。
    在这里插入图片描述

    接下来简单分析一下上述过程:

    1. 19   m o d   11 = 8 19\ mod \ 11=8 19 mod 11=8,该位置为空,直接放置即可。
    2. 1   m o d   11 = 1 1\ mod\ 11=1 1 mod 11=1,该位置为空,直接放置即可。
    3. 23   m o d   11 = 1 23\ mod\ 11=1 23 mod 11=1,该位置已经放置了元素, ( 1 + 1 ) m o d   11 = 2 (1+1)mod\ 11=2 (1+1)mod 11=2,2处没有放置元素,直接放入即可。
    4. 14   m o d   11 = 3 14\ mod\ 11=3 14 mod 11=3,该位置为空,直接放置即可。
    5. 55   m o d   11 = 0 55\ mod \ 11=0 55 mod 11=0,该位置为空,直接放置即可。
    6. 68   m o d   11 = 2 68\ mod\ 11=2 68 mod 11=2,该位置放置了元素23,需要重新计算, ( 2 + 1 ) m o d   11 = 3 (2+1)mod\ 11=3 (2+1)mod 11=3,该位置放置了元素14,还需要重新计算, ( 2 + 2 ) m o d   11 = 4 (2+2)mod\ 11=4 (2+2)mod 11=4,该位置为空,故放置到位置4。
    7. 11   m o d   11 = 0 11\ mod\ 11=0 11 mod 11=0,该位置已经放置了元素55,故需要继续计算,这里省略过程,需要从1一直加到5才有空闲位置,故放在位置5。
    8. 82   m o d   1 = 5 82\ mod\ 1=5 82 mod 1=5,位置5放置了元素11,故需要重新计算, ( 5 + 1 ) m o d   11 = 6 (5+1)mod\ 11=6 (5+1)mod 11=6,位置6为空,故放置在位置6即可。
    9. 36   m o d   11 = 3 36\ mod\ 11=3 36 mod 11=3,位置3已经放置为元素14,故需要重新计算,这里省略过程,需要从1一直加到4才能有空闲位置,故放在位置7。

    假设每个关键字的查找概率相同,则上述查找的 A S L ASL ASL为:
    A S L = 1 + 1 + 2 + 1 + 1 + 3 + 6 + 2 + 5 9 = 22 9 ASL=\frac{1+1+2+1+1+3+6+2+5}{9}=\frac{22}{9} ASL=91+1+2+1+1+3+6+2+5=922

    在实现线性冲突的时候,主要按照上述的流程进行实现,每取一个 d i d_i di都需要取判断一下当前是否找到了一个空闲位置,同时还需要考虑哈希表是否已经满的情况。

    // 线性探测初始化哈希表
    void init_hash_table_linear(int data[], int n, int hash_table[], int m, int p)
    {
        /// <summary>
        /// 建立哈希表(使用线性探测处理冲突)
        /// </summary>
        /// <param name="data">关键字集合</param>
        /// <param name="n">关键字个数</param>
        /// <param name="hash_table">哈希表</param>
        /// <param name="m">哈希表长度</param>
        /// <param name="p">除留余数法的参数</param>
        
        // 将哈希表的值全部初始化为-1,代表每个位置都没有放数据
        for (int i = 0; i < m; i++)
            hash_table[i] = -1;
    
        // 将每个<哈希地址,关键字>添加到哈希表中
        for (int i = 0; i < n; i++)
        {
            // 计算该关键字的哈希地址
            int addr = Hash_Func(data[i], p);   // 注意这里是对哈希函数参数p取模
            
    
            // 判断当前哈希地址是否为空,若发生冲突则线性探索
            if (hash_table[addr] != -1)
            {
                int flag = 0;   // 判断是否哈希表已满
    
                for (int i = 1; i < m; i++)
                {
                    int next = Hash_Func(addr + i, m);  // 下一个地址
                    if (hash_table[next] == -1)
                    {
                        flag = 1;   // 未满,有位置可以添加
                        addr = next;    // 地址赋值
                        break;  // 立即退出,找到第一个即可
                    }
                }
    
                // 对表满情况做处理
                if (flag == 0)
                {
                    cout << "FULL" << endl;
                    return;
                }
            }
            
            // 找到空闲位置后才放置关键字
            hash_table[addr] = data[i];
        }
    }
    

    如果在处理冲突的时候使用的是线性探测,那么在对应的查找的时候如果第一次根据哈希函数获得地址,但是地址中的关键字内容与查找的关键字不同,这时就需要使用对应的处理冲突方法来进行下一个地址的判断。同时也需要考虑查找失败的问题,查找失败有一个最好的判断方法就是如果找到了一个空地址(该地址中未装入关键字),那么说明查找失败。即哈希查找的整个流程如下所示。
    在这里插入图片描述

    故使用线性探测对应的查找代码如下所示。

    // 线性探索查找
    void Search_linear(int hash_table[], int m, int key, int p)
    {
        /// <summary>
        /// 线性探索查找
        /// </summary>
        /// <param name="hash_table">哈希表</param>
        /// <param name="m">哈希表表长</param>
        /// <param name="key">待查询关键字</param>
        /// <param name="p">哈希函数参数</param>
    
        // 初始哈希地址
        int index = Hash_Func(key, p);
        int count = 1;  // 统计比较次数
        if (hash_table[index] == -1)    // 没找到
        {
            cout << "NOT FOUND!" << endl;
            cout << "比较次数:" << count << endl;
            return;
        }
    
        if (hash_table[index] != key)   // 需要线性探索
        {
            int flag = 0;   // 判断是否查找到
            for (int i = 1; i < m; i++)
            {
    
                int next = Hash_Func(index + i, m);  // 下一个地址
    
                count++;
    
                if (hash_table[next] == -1) // 判断当前位置有无元素
                {
                    break;
                }
    
                if (hash_table[next] == key)
                {
                    flag = 1;   // 找到了
                    index = next;
                    break;  // 立即退出
                }
    
                
                
            }
            if (flag)   // 找到了
            {
                cout << "FOUND IT!!!" << endl;
                cout << "比较次数:" << count << endl;
                cout << "位置:" << index << endl;
    
            }
            else    // 没找到
            {
                cout << "NOT FOUND!" << endl;
                cout << "比较次数:" << count << endl;
            }
        }
        else // 不需要线性探索
        {
            cout << "FOUND IT!!!" << endl;
            cout << "比较次数:" << count << endl;
            cout << "位置:" << index << endl;
        }
    }
    
    

    二次探测

    d i = 1 2 , − 1 2 , 2 2 , − 2 2 , . . . d_i=1^2,-1^2,2^2,-2^2,... di=12,12,22,22,...时,称这种开放定址法为二次探测再散列。

    接下来通过一个例子对二次探测再散列进行理解。
    在这里插入图片描述

    接下来简单分析上述过程:

    1. 19   m o d   11 = 8 19\ mod \ 11=8 19 mod 11=8,该位置为空,直接放置即可。
    2. 1   m o d   11 = 1 1\ mod\ 11=1 1 mod 11=1,该位置为空,直接放置即可。
    3. 23   m o d   11 = 1 23\ mod\ 11=1 23 mod 11=1,该位置已经放置了元素, ( 1 + 1 ) m o d   11 = 2 (1+1)mod\ 11=2 (1+1)mod 11=2,2处没有放置元素,直接放入即可。
    4. 14   m o d   11 = 3 14\ mod\ 11=3 14 mod 11=3,该位置为空,直接放置即可。
    5. 55   m o d   11 = 0 55\ mod \ 11=0 55 mod 11=0,该位置为空,直接放置即可。
    6. 68   m o d   11 = 2 68\ mod\ 11=2 68 mod 11=2,该位置放置了元素23,需要重新计算, ( 2 + 1 ) m o d   11 = 3 (2+1)mod\ 11=3 (2+1)mod 11=3,该位置放置了元素14,还需要重新计算, ( 2 − 1 ) m o d   11 = 1 (2-1)mod\ 11=1 (21)mod 11=1,该位置放置了元素1,还需要重新计算, ( 2 + 4 ) m o d   11 = 6 (2+4)mod\ 11=6 (2+4)mod 11=6,该位置为空,故放置在位置6上。
    7. 11   m o d   11 = 0 11\ mod\ 11=0 11 mod 11=0,该位置已经放置了元素55,故需要继续计算, ( 0 + 1 ) m o d   11 = 1 (0+1)mod\ 11=1 (0+1)mod 11=1,位置1已经放置为元素1,故需要重新计算; ( 0 − 1 ) m o d   11 = 10 (0-1)mod\ 11=10 (01)mod 11=10,位置10为空,故放在位置10。
    8. 82   m o d   11 = 5 82\ mod\ 11=5 82 mod 11=5,该位置为空,直接放置即可。
    9. 36   m o d   11 = 3 36\ mod\ 11=3 36 mod 11=3,该位置已经放置了元素14,故需要重新计算, ( 3 + 1 ) m o d   11 = 4 (3+1)mod\ 11=4 (3+1)mod 11=4,位置4为空,故放置在位置4即可。

    假设每个关键字的查找概率相同,则上述查找的 A S L ASL ASL为:
    A S L = 1 + 1 + 2 + 1 + 1 + 4 + 3 + 1 + 2 9 = 16 9 ASL=\frac{1+1+2+1+1+4+3+1+2}{9}=\frac{16}{9} ASL=91+1+2+1+1+4+3+1+2=916

    ​ 实现二次探测的时候也很简单,重点在于如何构造出 d i = 1 2 , − 1 2 , 2 2 , − 2 2 , . . . d_i=1^2,-1^2,2^2,-2^2,... di=12,12,22,22,...这样一个序列,我得想法是每次循环中分别对正数和负数都进行一次判断,这样对于参数的变换较为简单,只需要一个底数每次循环时变换即可。

    // 二次探测初始化哈希表
    void init_hash_table_square(int data[], int n, int hash_table[], int m, int p)
    {
        /// <summary>
        /// 建立哈希表(使用二次探测处理冲突)
        /// </summary>
        /// <param name="data">关键字集合</param>
        /// <param name="n">关键字个数</param>
        /// <param name="hash_table">哈希表</param>
        /// <param name="m">哈希表长度</param>
        /// <param name="p">除留余数法的参数</param>
    
        // 将哈希表的值全部初始化为-1,代表每个位置都没有放数据
        for (int i = 0; i < m; i++)
            hash_table[i] = -1;
    
        // 将每个<哈希地址,关键字>添加到哈希表中
        for (int i = 0; i < n; i++)
        {
            // 计算该关键字的哈希地址
            int addr = Hash_Func(data[i], p);   // 注意这里是对哈希函数参数p取模
    
    
            // 判断当前哈希地址是否为空,若发生冲突则二次探索
            if (hash_table[addr] != -1)
            {
                int flag = 0;   // 判断是否哈希表已满
                for (int i = 0; i < m; i++)
                {
                    if (hash_table[i] == -1)    // 查找空位
                    {
                        flag = 1;
                        break;
                    }
                }
                // 对表满情况做处理
                if (flag == 0)
                {
                    cout << "FULL" << endl;
                    return;
                }
    
                int next = addr;    // 新的地址
                int i = 1;  // 底数
                int k = 1;  // 指数
                while (hash_table[next] != -1)
                {
                    // 正数
                    next = (int)pow(-1, k + 1) * (int)pow(i, 2) + addr;
                    next = Hash_Func(next, m);
                    if (hash_table[next] == -1) // 如果加正数就可以成功,则直接退出
                        break;
    
                    // 加负数
                    next = (int)pow(-1, k) * (int)pow(i, 2) + addr;
                    next = Hash_Func(next, m);
                    // 下一轮,底数++
                    i++;
                }
                addr = next;    // 地址赋值
            }
    
            // 找到空闲位置后才放置关键字
            hash_table[addr] = data[i];
        }
    }
    

    结合上述实现方法,二次探测对应的查找代码如下所示。

    // 二次探索查找
    void Search_square(int hash_table[], int m, int key, int p)
    {
        /// <summary>
        /// 二次探索查找
        /// </summary>
        /// <param name="hash_table">哈希表</param>
        /// <param name="m">哈希表表长</param>
        /// <param name="key">待查询关键字</param>
        /// <param name="p">哈希函数参数</param>
    
        // 初始哈希地址
        int index = Hash_Func(key, p);
        int count = 1;  // 统计比较次数
        if (hash_table[index] == -1)    // 没找到
        {
            cout << "NOT FOUND!" << endl;
            cout << "比较次数:" << count << endl;
            return;
        }
    
        if (hash_table[index] != key)   // 需要线性探索
        {
            int flag = 0;   // 判断是否查找到
    
            int next = index;   // 新地址
            int i = 1;  // 底数
            int k = 1;  // 指数
            while (true)
            {
                count++;
                // 正数
                next = (int)pow(-1, k + 1) * (int)pow(i, 2) + index;
                next = Hash_Func(next, m);
                if (hash_table[next] == -1) // 没找到
                {
                    break;
                }
    
                if (hash_table[next] == key) // 如果加正数就可以找到,则直接退出
                {
                    flag = 1;
                    break;
                }
    
                count++;
                // 加负数
                next = (int)pow(-1, k) * (int)pow(i, 2) + index;
                next = Hash_Func(next, m);
                if (hash_table[next] == -1) // 没找到
                {
                    break;
                }
    
                if (hash_table[next] == key) // 如果加正数就可以找到,则直接退出
                {
                    flag = 1;
                    break;
                }
    
                // 下一轮,底数++
                i++;
            }
            index = next;
            if (flag)   // 找到了
            {
                cout << "FOUND IT!!!" << endl;
                cout << "比较次数:" << count << endl;
                cout << "位置:" << index << endl;
    
            }
            else    // 没找到
            {
                cout << "NOT FOUND!" << endl;
                cout << "比较次数:" << count << endl;
            }
        }
        else // 不需要线性探索
        {
            cout << "FOUND IT!!!" << endl;
            cout << "比较次数:" << count << endl;
            cout << "位置:" << index << endl;
        }
    }
    

    ​ 这里需要补充一下,因为涉及到负数的求模运算,最终我们需要的肯定是一个正数,故这里对求模运算进行一定的改进,如下所示。

    // 哈希函数
    int Hash_Func(int key, int p)
    {
        /// <summary>
        /// 哈希函数,计算对应的地址
        /// </summary>
        /// <param name="key">关键字</param>
        /// <param name="p">除留余数法中除数</param>
        /// <returns>计算的地址</returns>
    
        return (key % p + p) % p;
    }
    

    再哈希法

    ​ 除了开放定址法之外,还可以使用再哈希法来处理冲突。再哈希法就是构造若干个哈希函数,当发生冲突时,计算下一个哈希地址,直到冲突不再发生,即:
    H i = R H i ( k e y ) , i = 1 , 2 , . . . , k H_i=RH_i\left( key \right) , i=1,2,...,k Hi=RHi(key),i=1,2,...,k
    其中 R H i RH_i RHi代表不同的哈希函数。

    ​ 使用再哈希法的特点在于,不易产生聚集,但是需要增加计算时间。

    链地址法

    ​ 上述思路均为遇到相同的地址就换一个新的地址,那么是否可以讲所有的数据存放在一起呢。这里可以参考链表的做法,将所有哈希地址相同的记录都链接再同一个链表中,这种方法被称为链地址法。

    ​ 不过既然涉及到链表的插入,那么必然就会分为头插和尾插,这里分别举一个例子。
    在这里插入图片描述

    在这里插入图片描述

    ​ 这里主要对表后插入的那一组例子计算一次 A S L ASL ASL,如下所示。
    A S L = 1 + 2 + 1 + 2 + 1 + 1 + 2 + 1 + 1 9 = 12 9 ASL=\frac{1+2+1+2+1+1+2+1+1}{9}=\frac{12}{9} ASL=91+2+1+2+1+1+2+1+1=912

    链地址法的实现基本可以参考前面链表的实现方法,首先根据哈希函数的参数开辟对应的头结点数组,然后根据关键字数组将所有的关键字添加到对应的链表上面,插入方法这里选择的是尾插法。查找的时候也十分简单,先获取哈希地址,然后将那一根链表拿出,从头遍历即可。这里同时也实现了哈希增补的功能,即如果没有查找到对应的关键字,则将对应的关键字添加到对应的链表中。

    // 结点
    typedef struct Node
    {
        int data;   // 数据域
        Node* next; // 下一个结点
        // 构造函数
        Node()
        {
            data = -1;
            next = NULL;
        }
    }Node;
    
    
    // 链表
    typedef struct List
    {
        Node** head;    // 头结点数组
        Node** tail;    // 尾结点指针
        int len;    // 头结点数组长度
        // 构造函数
        List()
        {
            head = NULL;
            len = 0;
            tail = NULL;
        }
    
    
        // 初始化
        void init_List(int p, int num[], int n)
        {
            /// <summary>
            /// 初始化链表
            /// </summary>
            /// <param name="p">哈希函数参数</param>
            /// <param name="num">关键字数组</param>
            /// <param name="n">关键字个数</param>
            len = p;
            head = new Node * [p];  // 头指针数组
            tail = new Node * [p];  // 尾指针数组
            // 初始化头结点和尾指针
            for (int i = 0; i < len; i++)
            {
                head[i] = new Node();   // 头结点
                head[i]->data = i;
                head[i]->next = NULL;
                tail[i] = head[i];
            }
    
            // 逐个数据添加
            for (int i = 0; i < n; i++)
            {
                int addr = Hash_Func(num[i], p);    // 获取哈希地址
                Node* t = new Node();   // 创建新节点
                t->data = num[i];   
                t->next = NULL;
                // 尾插法
                tail[addr]->next = t;   
                tail[addr] = t;
            }
               
        }
    
    
        // 查找
        void search(int key, int p)
        {
            int count = 1;  // 查找次数
            int addr = Hash_Func(key, p);   // 哈希地址
            Node* t = head[addr]->next; // 找到对应的链表
            // 不断遍历
            while (t)
            {
                count++;
                if (t->data == key) // 找到则退出
                    break;
                t = t->next;
            }
            if (t)
            {
                
                cout << "FOUNT IT!!!" << endl;
                cout << addr << endl;
                cout << "次数:" << count << endl << endl;
            }
            else
            {
                Node* s = new Node();
                s->data = key;
                s->next = NULL;
                tail[addr]->next = s;
                tail[addr] = s;
                cout << "NOT FOUNT!!" << endl << endl;
            }
        }
    
    
        // 输出所有链表
        void display_all()
        {
            for (int i = 0; i < len; i++)
            {
                Node* t = head[i]->next;
                cout << i << ":";
                while (t)
                {
                    cout << t->data << "->";
                    t = t->next;
                }
                cout << endl;
                
            }
        }
    
    }List;
    

    性能分析

    ​ 决定哈希表查找 A S L ASL ASL的因素有:

    1. 选用的哈希函数
    2. 选用的处理冲突的方法
    3. 哈希表 装填因子

    其中哈希表的装填因子是哈希表中填入的记录数与哈希表的长度的比值,即:
    α = 哈希表中填入的记录数 哈希表长度 \alpha =\frac{\text{哈希表中填入的记录数}}{\text{哈希表长度}} α=哈希表长度哈希表中填入的记录数
    装填因子 α \alpha α标志哈希表的装满程度,直观来看,装填因子 α \alpha α越小,发生冲突的可能性越小,装填因子 α \alpha α越大,发生冲突的可能性就越大。

    线性探测再散列的哈希查找成功时:
    A S L ≈ 1 2 ( 1 + 1 1 − α ) ASL\approx \frac{1}{2}\left( 1+\frac{1}{1-\alpha} \right) ASL21(1+1α1)
    二次探测再散列的哈希表查找成功时:
    A S L ≈ − 1 α ln ⁡ ( 1 − α ) ASL\approx -\frac{1}{\alpha}\ln ^{\left( 1-\alpha \right)} ASLα1ln(1α)
    链地址法处理冲突的哈希表查找成功时:
    A S L ≈ ( 1 + α 2 ) ASL\approx \left( 1+\frac{\alpha}{2} \right) ASL(1+2α)

    展开全文
    weixin_44267007 2021-08-28 14:07:36
  • 目录 背景 哈希概念 哈希概念 哈希操作 哈希冲突 哈希函数 负载因子 解决哈希冲突 闭散列 概念 线性探测 二次探测 实现 开散列 概念 迭代器 实现 最优哈希表长度 不是整形元素数据类型怎么处理 背景 在 C++98 中,...

    背景

    • 在 C++98 中,STL 提供了底层为红黑树结构的一系列关联式容器,这些容器在进行查询时的效率最坏也只有 log2N,最差情况也就是需要比较红黑树的高度次,虽然这样的效率已经非常高了,但是当树中的节点非常非常多时,查询效率也就变得不理想了;
    • 而理想中最好的查询是,进行很少的比较次数就能够将元素找到,因此在 C++11 中,STL 又提供了四个unordered系列的关联式容器,这四个容器与红黑树系列的四个关联式容器使用方式基本类似,只是其底层结构不同,这四个容器分别是unordered_mapunordered_setunordered_multimap以及unordered_multiset,这些容器的底层结构采用了哈希结构,本篇博客就让我们来细细看看哈希是怎么一回事;

    哈希概念

    哈希概念

    • 之前的结构:顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较,而顺序表中查找时间复杂度为 O(N),平衡树中查找时间复杂度为树的高度 O(log2N),这些结构进行搜索的效率取决于搜索过程中元素的比较次数,这样的效果并不是很理想;
    • 现在的结构:构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一 一映射的关系,那么在查找时通过该函数可以很快找到指定元素,也就是不经过任何比较,通过一次计算得到待查找元素在表中的位置;
    • 哈希:上面所说的方式即为哈希 (散列) 方法,哈希方法中使用的转换函数 (计算函数) 称为哈希 (散列) 函数,构造出来的结构称为哈希表 (Hash Table 或者称为散列表);

    哈希操作

    • 插入元素:根据待插入元素的关键码,通过哈希函数计算出该元素的存储位置,并按此位置在哈希表中进行存放;
    • 搜索元素:对元素的关键码进行同样的计算,把求得的结果当做元素在哈希表中的的存储位置,然后在哈希表中拿到此位置的元素并进行比较,若关键码相等,则搜索成功;
    • 举例:数据—— {1, 7, 6, 4, 5, 9},哈希函数——hash(key) = key % capacity,也就是元素关键码对哈希表容量取余计算;
      在这里插入图片描述

    哈希冲突

    • 概念:对于两个数据元素的关键字 m 和 n,虽然有 m != n,但是却有:Hash(m) == Hash(n),即:不同关键字通过相同哈希函数计算出了相同的哈希地址,该种现象称为哈希冲突或哈希碰撞,把具有不同关键码而具有相同哈希地址的数据元素称为——同义词;
    • 性质:哈希冲突可以被减小,但是不能被避免;
    • 原因之一:引起哈希冲突的某个可能的原因是——哈希函数设计不够合理;

    哈希函数

    • 哈希函数设计原则:
      • 哈希函数的定义域必须包括需要存储的全部关键码,而如果哈希表允许有 m 个地址时,其值域必须在 0 ~ m-1 之间;
      • 哈希函数计算出来的地址最好能均匀分布在整个空间中;
      • 哈希函数的计算最好比较简单;
    • 常见哈希函数
      1. 直接定制法:取关键字的某个线性函数为散列地址,即 Hash (Key) = A * Key + B,适合查找比较小且连续的情况;
      2. 除留余数法:设散列表中允许的地址数为 m,取一个不大于 m,但最接近或者等于 m 的质数 p 作为除数,然后按照哈希函数:Hash (key) = key % p (p<=m),将关键码转换成哈希地址;
      3. 平方取中法:假设关键字为 1234,对它平方就是 1522756,抽取中间的 3 位 227 作为哈希地址;再比如关键字为 4321,对它平方就是 18671041,抽取中间的 3 位 671 (或 710) 作为哈希地址,适合不知道关键字的分布,而位数又不是很大的情况;
      4. 折叠法:折叠法是将关键字从左到右分割成位数相等的几部分 (最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址,适合事先不需要知道关键字的分布,适合关键字位数比较多的情况;
      5. 随机数法:选择一个随机函数,取关键字的随机函数值为它的哈希地址,即 H(key) = random(key),其中 random 为随机数函数,通常关键字长度不等时采用此法;
      6. 数学分析法:设有 n 个 d 位数,每一位可能有 r 种不同的符号,这 r 种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现,可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址;

    负载因子

    • 概念:用哈希表中的有效元素个数除以哈希表的总容量得到的值被称为负载因子,该值往往小于 1;
    • 原因:哈希表中的元素个数越少,那么产生哈希冲突的几率也就越小,因此在向哈希表中插入元素时,我们需要检查哈希表的负载因子是否合适,避免将元素插入到一个冲突较大的位置,使得查找时时间复杂度较高;
    • 增容:在负载因子超过某一阈值时(阈值可由自己决定,一般 0.5 ~ 0.8 合适),我们需要对哈希表进行增容,该过程为:创建新的容量大的哈希表——>将原表中的元素一个一个重新插入新表;

    解决哈希冲突

    闭散列

    概念
    • 概念:闭散列也叫开放定址法,当发生哈希冲突时,由于负载因子的存在,所以哈希表永远有空位置,那么可以把 key 存放到冲突位置后的 “下一个” 空位置中去,这里的下一个并不是真正意义上的下一个,而是从冲突位置向后找到的第一个空位置再插入;
    线性探测
    • 概念:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止;
    • 插入
      1. 通过哈希函数获取待插入元素在哈希表中的位置;
      2. 如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素;
      3. 在插入的过程中走到了表尾仍没有找到,那么循环到表头继续查找;
        在这里插入图片描述
    • 查找
      • 先使用哈希函数查找到待查找元素的位置,然后从该位置开始取每一个表中元素的 key 和待插入元素的 key 进行比较,如果相等则找到,如果不相等则向后继续,直到找到一个为空的位置都没有找到,那么则说明表中没有这个元素;
    • 删除
      • 采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索,因为删除元素的前提是查找到该元素,如果直接删除某一个元素就会使得查找元素时很容易遇到空位置,这样就会导致查找结束从而找不到待删除元素;
      • 因此线性探测法采用标记的伪删除法来删除一个元素,就是每个节点都有一个状态标志,分别为:EXIST——有效结点,DELETE——被删除,EMPTY——空节点,初始时,每个节点都是 EMPTY 标志,插入结点后改为 EXIST 标志,删除时改为 EMPTY 标志而不要动哈希结构;
    • 优点:实现的代码非常简单;
    • 缺点:一旦发生哈希冲突,所有的冲突将会连在一起,这样容易产生数据“堆积”,即:不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要许多次比较,导致搜索效率降低;
    二次探测
    • 概念:线性探测的缺陷是产生冲突的数据堆积在一块,这是因为产生冲突时我们是顺序的向后查找一个空位置,所以会差生堆积,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为:h = ( idx + i2 ) % m 或者 h = ( idx - i2 ) % m,其中:i = 1,2,3…,h 为最后得到的结果,idx 是通过散列函数 Hash(x) 对元素的关键码 key 进行计算得到的位置,m 是表的大小;
      在这里插入图片描述
    实现
    #include<iostream>
    #include<vector>
    using namespace std;
    
    //一个标志位,用来指明当前节点的状态:有元素、被删除、为空
    enum STATE {
    	EXIST,
    	DELETE,
    	EMPTY
    };
    
    //哈希元素节点
    template<class K, class V>
    struct HashNode{
    	//存放数据
    	pair<K, V> _val;
    	//状态位
    	STATE _state;
    
    	//构造函数
    	HashNode(const pair<K, V>& val)
    		:_val(val)
    		,_state(EMPTY)
    	{}
    };
    
    //哈希表
    template<class K, class V>
    class HashTable {
    public:
    	typedef HashNode<K, V> Node;
    	typedef HashTable<K, V> Table;
    
    	//构造函数
    	HashTable(const int num = 10)
    		:_ht(num)
    		,_size(0)
    	{}
    
    	//插入操作
    	bool insert(const pair<K, V>& val) {
    		//检查容量
    		CheckCapacity();
    		//计算元素位置
    		int idx = val.first % _ht.size();
    		//判断是否存在重复元素以及找到实际插入位置
    		while (_ht[idx]._state != EMPTY) {
    			//如果当前节点是被删除的或者该节点的值不等于插入的节点,那么就继续寻找
    			if (_ht[idx]._state == DELETE || _ht[idx]._val.first != val.first)
    				idx++;
    			//否则就是说明遇到了相同节点,那么插入失败
    			else
    				return false;
    			//当走到idx > _ht.size(),那么就从表的头部开始继续查找
    			if (idx == _ht.size())
    				idx = 0;
    		}
    		//能走到这说明遇到空的位置了,将数据插入
    		_ht[idx]._val = val;
    		//并将该节点状态置为EXIST
    		_ht[idx]._state = EXIST;
    		//更新变量
    		++_size;
    		return true;
    	}
    
    	//检查容量操作
    	void CheckCapacity() {
    		//检查负载因子是否超过阈值:0.7(阈值自己定,一般0.5~0.8)
    		//超过阈值或者此时哈希表为空,那么就需要增容
    		if (_ht.size() == 0 || _size * 10 / _ht.size() > 7) {
    			int newc = _ht.size() == 0 ? 10 : 2 * _ht.size();
    			//创建新的哈希表,这里为什么不创建新的数组而是选择创建新的哈希表
    			//创建数组的话需要重新插入每一个元素,而创建哈希表的话,可以直接调用insert接口
    			HashTable<K, V> newht(newc);
    			//将原有元素重新放入新表
    			for (int i = 0; i < _ht.size(); i++) {
    				if (_ht[i]._state == EXIST)
    					newht.insert(_ht[i]._val);
    			}
    			//重新插入完成后,在交换新旧哈希表的内容
    			Swap(newht);
    		}
    	}
    
    	//交换接口
    	void Swap(Table& t) {
    		swap(_ht, t._ht);
    		swap(_size, t._size);
    	}
    
    	//查找接口
    	Node* find(const K& key) {
    		//无元素直接返回
    		if (_size == 0)
    			return nullptr;
    		//计算位置
    		int idx = key % _ht.size();
    		//循环查找,找到则返回,找到空的位置则失败
    		while (_ht[idx]._state != EMPTY) {
    			//如果状态是存在且等于待查找元素,则找到返回
    			if (_ht[idx]._state == EXIST && _ht[idx]._val.first == key)
    				return &_ht[idx];
    			//否则就继续向后查找
    			idx++;
    			//当走到末尾之后,那么就重置到起始位置
    			if (idx == _ht.size())
    				idx = 0;
    		}
    		//走到这说明没找到,返回空
    		return nullptr;
    	}
    
    	//删除操作
    	bool erase(const K& key) {
    		//没有元素就算删除成功
    		if (_size == 0)
    			return true;
    		//找到待删除元素的位置
    		Node* cur = find(key);
    		//如果返回的是空,则说明没有,删除失败,否则就将其状态置为EMPTY,成功
    		if (cur) {
    			cur->_state = EMPTY;
    			--_size;
    			return true;
    		}
    		return false;
    	}
    private:
    	vector<Node> _ht;
    	int _size; //有效元素个数
    };
    
    int main() {
    
    	return 0;
    }
    

    开散列

    概念
    • 概念:开散列法又叫链地址法(开链法),首先对关键码集合用哈希函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中;
      在这里插入图片描述
    • 插入
      • 先使用哈希函数计算插入位置;
      • 然后从计算出的位置处,拿到链表的头结点,然后遍历该单链表,检测是否存在 key 值相同的元素,如果存在则插入失败;
      • 如果不存在相同元素则插入,因为元素本身无序,所以在计算出的位置处,将元素以头插的方式插入单链表中即可,无需进行尾插;
    • 查找
      • 先计算位置;
      • 然后从计算出的位置处,拿到链表的头结点,然后向后遍历,一 一比对 key,相同则说明找到了;
    • 删除
      • 先计算位置;
      • 然后从计算出的位置处,拿到链表的头结点,然后向后遍历,找到待删除元素后,将其从链表上拿下来,然后重新链接链表结点的指针;
    • 增容
      • 哈希表中桶的个数是一定的,随着元素的不断插入,每个桶中元素的个数不断增多,极端情况下,可能会导致一个桶中链表节点非常多,会影响的哈希表的性能,因此在一定条件下需要对哈希表进行增容,那该条件怎么确认呢?
      • 开散列最好的情况是:每个哈希桶中刚好挂一个节点,每个桶都挂入一个节点后,再继续插入元素时,每一次都会发生哈希冲突,因此,在元素个数刚好等于桶的个数时,可以给哈希表增容,也就是负载因子为 1 时就进行增容;
    迭代器
    • 开散列哈希表的迭代器并不是简单的节点地址,而是和链表的迭代器一样,是一个封装了节点的结构体,在这个结构体中比较复杂的接口就是++运算符,因为结构中存在单链表,所以不是连续的,因此在迭代器++的时候可能需要跳转,具体看下面的分析:
      在这里插入图片描述
    实现
    #include<iostream>
    #include<vector>
    using namespace std;
    
    //哈希结点
    template<class V>
    struct HashNode {
    	//数据
    	V _val;
    	//指向下一个节点的指针
    	HashNode<V>* _next;
    	//构造函数
    	HashNode(const V& val = V())
    		:_val(val)
    		,_next(nullptr)
    	{}
    };
    
    //对于那些不是整形的数据,要将他们的key值转换为能进行计算的整数数据
    template<class K>
    struct hashfun {
    	size_t operator()(const K& key) {
    		return key;
    	}
    };
    //对于如果是string类型,那么就对上面的模板进行特化
    template<>
    struct hashfun<string> {
    	size_t operator()(const string& key) {
    		size_t h = 0;
    		for (auto& e : key)
    			h = h * 131 + e;
    		return (h & 0x7FFFFFFF);
    	}
    };
    
    //哈希表的前置声明,这样在迭代器中就可以使用了
    template<class K, class V, class keyofval, class hashfun = hashfun<K>>
    class HashTable;
    
    //哈希表的迭代器
    template<class K, class V, class keyofval, class hashfun = hashfun<K>>
    struct HashIterator {
    	typedef HashNode<V> Node;
    	typedef HashIterator<K, V, keyofval,hashfun> Self;
    	//当前迭代器中封装的结点指针
    	Node* _node;
    	//拿到哈希表中的数组,这样就可以进行遍历访问了
    	vector<Node*> _vht;
    
    	//构造函数
    	HashIterator(Node* node, vector<Node*> vht)
    		:_node(node)
    		,_vht(vht)
    	{}
    
    	//重载 * 运算符
    	V& operator*() {
    		return _node->_val;
    	}
    
    	//重载 -> 运算符
    	V* operator->(){
    		return &(_node->_val);
    	}
    
    	//重载 != 运算符
    	bool operator!=(const Self& it) {
    		return _node != it._node;
    	}
    
    	//重载 ++ 运算符
    	Self& operator++() {
    		//如果当前迭代器中的结点的_next指针不为空,则就更新到_next
    		if (_node->_next)
    			_node = _node->_next;
    		//如果当前迭代器中的结点的_next为空,那么需要进入哈希表中向后查找
    		else {
    			//首先拿到当前节点在哈希表中的位置的后一个位置
    			hashfun fun;
    			keyofval kov;
    			int idx = fun(kov(_node->_val)) % _vht.size() + 1;
    			//然后从哈希表的这个位置向后查找,找到第一个不为空的指针
    			while (idx < _vht.size() && _vht[idx] == nullptr) {
    				idx++;
    			}
    			//然后判断这个位置是否超出哈希表的大小
    			if (idx < _vht.size())
    				//如果小于,则更新到这个位置
    				_node = _vht[idx];
    			else
    				//否则,令其为空
    				_node = nullptr;
    		}
    		return *this;
    	}
    };
    
    //哈希表
    template<class K, class V, class keyofval, class hashfun>
    class HashTable {
    public:
    	typedef HashNode<V> Node;
    	typedef HashIterator<K, V, keyofval, hashfun> iterator;
    
    	//构造函数
    	HashTable(const int n = 10)
    		:_ht(n)
    		,_size(0)
    	{}
    
    	//begin()迭代器
    	iterator begin() {
    		//begin迭代器封装了哈希表中第一个不为空的结点指针
    		int idx = 0;
    		while (idx < _ht.size()) {
    			if (_ht[idx]) {
    				return iterator(_ht[idx], _ht);
    			}
    			idx++;
    		}
    		return iterator(nullptr, _ht);
    	}
    
    	//begin()迭代器
    	iterator end() {
    		//end迭代器中就是封装了nullptr指针
    		return iterator(nullptr, _ht);
    	}
    
    	//插入操作,成功与否都返回一个pair<iterator, bool>键值对
    	//成功返回(插入的迭代器位置,bool),失败返回(已存在的迭代器位置,false)
    	pair<iterator, bool> insert(const V& val) {
    		//检查容量
    		CheckCapacity();
    		//计算在哈希表中的位置
    		hashfun fun;
    		keyofval kov;
    		int idx = fun(kov(val)) % _ht.size();
    		//然后开始插入,先创建节点
    		Node* cur = new Node(val);
    		//再检查哈希表中是否已存入相同节点
    		Node* tmp = _ht[idx];
    		while (tmp) {
    			if (fun(kov(tmp->_val)) == fun(kov(val)))
    				return make_pair(iterator(tmp, _ht), false);
    			tmp = tmp->_next;
    		}
    		//如果没有查找到相同的结点,那么就插入表中
    		cur->_next = _ht[idx];
    		_ht[idx] = cur;
    		_size++;
    		return make_pair(iterator(cur, _ht), true);
    	}
    
    	//容量检查
    	void CheckCapacity() {
    		//开散列哈希表的负载因子可以为1,所以就以1为基准
    		if (_size == _ht.size()) {
    			//先查看原先容量的情况,然后再适量分配
    			int newc = _ht.size() == 0 ? 10 : 2 * _size;
    			vector<Node*> newht(newc);
    			//将原先哈希表的内容重新插入新表中
    			for (int i = 0; i < _ht.size(); i++) {
    				//遍历每一个以哈希结点为头的单链表
    				Node* cur = _ht[i];
    				//非空就开始遍历
    				while (cur) {
    					//先保留节点的下一个节点
    					Node* temp = cur->_next;
    					//计算节点在新表中的位置
    					hashfun fun;
    					keyofval kov;
    					int idx = fun(kov(cur->_val));
    					//插入新表中
    					cur->_next = newht[idx];
    					newht[idx] = cur;
    					cur = temp;
    				}
    				//将旧表中的指针置为空
    				_ht[i] == nullptr;
    			}
    			//此时交换两个表,这样新表就成为当前哈希对象的成员
    			swap(_ht, newht);
    		}
    	}
    private:
    	vector<Node*> _ht;
    	int _size;
    };
    
    //用开散列的哈希表来实现unordered_map
    template<class K, class V>
    class unorderedmap {
    	//这就是提供给底层结构的仿函数,作用就是获取到存入元素的key值
    	struct keyofval {
    		const K& operator()(const pair<K, V>& val) {
    			return val.first;
    		}
    	};
    	//成员变量
    	HashTable<K, pair<K, V>, keyofval> _ht;
    public:
    	//因为这是泛型参数未确定的类的迭代器,所以编译器识别不了,因此需要加上一个typename,告诉编译器这个类的泛型参数可以延迟确定,所以这个迭代器可以使用
    	typedef typename HashTable<K, pair<K, V>, keyofval>::iterator iterator;
    	//插入操作
    	pair<iterator, bool> insert(const pair<K, V>& val) {
    		return _ht.insert(val);
    	}
    	//[]操作
    	V& operator[](const K& key) {
    		pair<iterator, bool> ret = _ht.insert(make_pair(key, V()));
    		return ret.first->second;
    	}
    	//迭代器
    	iterator begin() {
    		return _ht.begin();
    	}
    	iterator end() {
    		return _ht.end();
    	}
    };
    
    //用开散列的哈希表来实现unordered_set
    template<class V>
    class unorderedset {
    	//这就是提供给底层结构的仿函数,作用就是获取到存入元素的key值
    	struct keyofval {
    		const V& operator()(const V& val) {
    			return val;
    		}
    	};
    	//成员变量
    	HashTable<V, V, keyofval> _ht;
    public:
    	//因为这是泛型参数未确定的类的迭代器,所以编译器识别不了,因此需要加上一个typename,告诉编译器这个类的泛型参数可以延迟确定,所以这个迭代器可以使用
    	typedef typename HashTable<V, V, keyofval>::iterator iterator;
    	//插入操作
    	pair<iterator, bool> insert(const V& val) {
    		return _ht.insert(val);
    	}
    	//迭代器
    	iterator begin() {
    		return _ht.begin();
    	}
    	iterator end() {
    		return _ht.end();
    	}
    };
    
    int main() {
    	unorderedmap<string, int> mp;
    	mp.insert(make_pair("123", 6));
    	mp.insert(make_pair("456", 4));
    	mp.insert(make_pair("123", 7));
    	mp.insert(make_pair("789", 3));
    	for (auto e : mp) {
    		cout << e.first << "->" << e.second << endl;
    	}
    	return 0;
    }
    

    最优哈希表长度

    • 研究表明,当表的长度为质数且表的负载因子 a 不超过 0.5 时,新的元素一定能够一次性插入,任何一个位置都不会被探查两次,因此只要表中有一半的空位置,就不会存在表满的问题;
    • 在搜索时可以不用考虑表装满的情况,但在插入时需要考虑这个问题,因此最好确保表的负载因子 a 不超过 0.5,如果超出就要考虑增容了,否则效率就会降低,因此闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷;
    • 自己实现的哈希表的增容是二倍的增长,但是源码中并不是这样的,因为空间容量为一个质数时效率更高,哈希冲突更小,所以一般是在增容时,先确定所需的容量 num,然后再拿到一个大于 num 的质数 newnum,然后将 newnum 作为增容的大小进行增容,具体操作如下:
    const int PRIMECOUNT = 28;
    const size_t primeList[PRIMECOUNT] =
    {
    	53ul, 97ul, 193ul, 389ul, 769ul,
    	1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    	49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    	1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    	50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    	1610612741ul, 3221225473ul, 4294967291ul
    };
    size_t GetNextPrime(size_t prime){
    	size_t i = 0;
    	for(; i < PRIMECOUNT; ++i){
    		if(primeList[i] > primeList[i])
    		return primeList[i];
    	}
    	return primeList[i];
    }
    

    不是整形元素数据类型怎么处理

    • 对于不是整形的数据的数据类型,一般处理是将其转化为整型值,至于怎么转化,这些请自行查阅资料,这里面涉及到了许多数学原理来减少哈希冲突,所以不多介绍;
    • 这里就是说一下怎么来将其转化:思路就是写一个转化函数,然后将其当做泛型参数传入哈希表中,然后在对哈希结点计算存储位置时,先使用传入的函数对其进行转化(我们写的这个函数是一个泛型模板,也就是说能能将任何数据类型的数转化为整型数值返回),然后再通过转化的值来确定哈希位置;
    展开全文
    Jokersorry 2021-05-25 21:00:02
  • weixin_40535588 2021-11-22 21:07:08
  • u010608296 2021-10-02 13:11:15
  • linping_ 2021-04-23 20:55:16
  • qq_51214556 2021-11-21 10:01:06
  • weixin_57023347 2021-09-09 10:44:43
  • qq_42897364 2021-01-03 20:06:32
  • qq_40223983 2021-03-05 09:16:47
  • qq_49306008 2021-10-19 18:21:13
  • qq_51604330 2021-10-18 21:15:07
  • weixin_27442001 2021-05-24 03:36:32
  • qq_34105990 2021-02-20 14:29:38
  • weixin_42529366 2021-01-19 16:17:20
  • qq_45859087 2021-05-20 12:22:07
  • Worthwhile_DUT 2021-12-03 13:25:05
  • ych9527 2021-06-12 09:29:06
  • qq_32727095 2021-03-08 09:54:03
  • weixin_44120785 2021-10-29 13:37:00
  • qq_48201696 2021-08-05 00:46:39
  • qq_42186650 2021-08-22 23:47:33

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 372,990
精华内容 149,196
关键字:

哈西表