精华内容
下载资源
问答
  • C++哈希表使用的好文章-Hash_Map

    热门讨论 2010-05-17 12:38:24
    hash_map基于hash table(哈希表)。 哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间...
  • C++哈希表使用教程(STL)

    万次阅读 2013-07-29 11:29:41
    哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也...


    0 为什么需要hash_map

    用过map吧?map提供一个很常用的功能,那就是提供key-value的存储和查找功能。例如,我要记录一个人名和相应的存储,而且随时增加,要快速查找和修改:

    
    
    岳不群-华山派掌门人,人称君子剑 张三丰-武当掌门人,太极拳创始人 东方不败-第一高手,葵花宝典 ...

    这些信息如果保存下来并不复杂,但是找起来比较麻烦。例如我要找"张三丰"的信息,最傻的方法就是取得所有的记录,然后按照名字一个一个比较。如果要速度快,就需要把这些记录按照字母顺序排列,然后按照二分法查找。但是增加记录的时候同时需要保持记录有序,因此需要插入排序。考虑到效率,这就需要用到二叉树。讲下去会没完没了,如果你使用STL 的map容器,你可以非常方便的实现这个功能,而不用关心其细节。关于map的数据结构细节,感兴趣的朋友可以参看学习STL map, STL set之数据结构基础。看看map的实现:

    
    
    #include <map> #include <string> using namespace std; ... map<string, string> namemap;
    //增加。。。
    namemap["岳不群"]="华山派掌门人,人称君子剑";
    namemap["张三丰"]="武当掌门人,太极拳创始人";
    namemap["东方不败"]="第一高手,葵花宝典";
    ...
    //查找。。
    if(namemap.find("岳不群") != namemap.end()){
    ...
    }

    不觉得用起来很easy吗?而且效率很高,100万条记录,最多也只要20次的string.compare的比较,就能找到你要找的记录;200万条记录事,也只要用21次的比较。

    速度永远都满足不了现实的需求。如果有100万条记录,我需要频繁进行搜索时,20次比较也会成为瓶颈,要是能降到一次或者两次比较是否有可能?而且当记录数到200万的时候也是一次或者两次的比较,是否有可能?而且还需要和map一样的方便使用。

    答案是肯定的。这时你需要has_map. 虽然hash_map目前并没有纳入C++ 标准模板库中,但几乎每个版本的STL都提供了相应的实现。而且应用十分广泛。在正式使用hash_map之前,先看看hash_map的原理。

    1 数据结构:hash_map原理

    这是一节让你深入理解hash_map的介绍,如果你只是想囫囵吞枣,不想理解其原理,你倒是可以略过这一节,但我还是建议你看看,多了解一些没有坏处。

    hash_map基于hash table(哈希表)。哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。

    其基本原理是:使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数,也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标,hash值)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储在相应“类”所对应的地方,称为桶。

    但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。

    hash_map,首先分配一大片内存,形成许多桶。是利用hash函数,对key进行映射到不同区域(桶)进行保存。其插入过程是:

    1. 得到key
    2. 通过hash函数得到hash值
    3. 得到桶号(一般都为hash值对桶数求模)
    4. 存放key和value在桶内。

    其取值过程是:

    1. 得到key
    2. 通过hash函数得到hash值
    3. 得到桶号(一般都为hash值对桶数求模)
    4. 比较桶的内部元素是否与key相等,若都不相等,则没有找到。
    5. 取出相等的记录的value。

    hash_map中直接地址用hash函数生成,解决冲突,用比较函数解决。这里可以看出,如果每个桶内部只有一个元素,那么查找的时候只有一次比较。当许多桶内没有值时,许多查询就会更快了(指查不到的时候).

    由此可见,要实现哈希表, 和用户相关的是:hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。

    2 hash_map 使用

    2.1 一个简单实例

    不要着急如何把"岳不群"用hash_map表示,我们先看一个简单的例子:随机给你一个ID号和ID号相应的信息,ID号的范围是1~2的31次方。如何快速保存查找。

    
    
    #include <hash_map> #include <string> using namespace std; int main(){
    hash_map<int, string> mymap;
    mymap[9527]="唐伯虎点秋香";
    mymap[1000000]="百万富翁的生活";
    mymap[10000]="白领的工资底线";
    ...
    if(mymap.find(10000) != mymap.end()){
    ...
    }

    够简单,和map使用方法一样。这时你或许会问?hash函数和比较函数呢?不是要指定么?你说对了,但是在你没有指定hash函数和比较函数的时候,你会有一个缺省的函数,看看hash_map的声明,你会更加明白。下面是SGI STL的声明:

    
    
    template <class _Key, class _Tp, class _HashFcn = hash<_Key>, class _EqualKey =
    equal_to<_Key>,
    class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
    class hash_map
    {
    ...
    }

    也就是说,在上例中,有以下等同关系:

    
    
    ...
    hash_map<int, string> mymap;
    //等同于:
    hash_map<int, string, hash<int>, equal_to<int> > mymap;


    另外一个介绍博文


    Map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据处理能力,由于这个特性,它完成有可能在我们处理一对一数据的时候,在编程上提供快速通道。这里说下map内部数据的组织,map内部自建一颗红黑树(一种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,所以在map内部所有的数据都是有序的,后边我们会见识到有序的好处。

    下面举例说明什么是一对一的数据映射。比如一个班级中,每个学生的学号跟他的姓名就存在着一一映射的关系,这个模型用map可能轻易描述,很明显学号用int描述,姓名用字符串描述(本篇文章中不用char *来描述字符串,而是采用STL中string来描述),下面给出map描述代码:

    Map<int, string> mapStudent;

    1.       map的构造函数

    map共提供了6个构造函数,这块涉及到内存分配器这些东西,略过不表,在下面我们将接触到一些map的构造方法,这里要说下的就是,我们通常用如下方法构造一个map:

    Map<int, string> mapStudent;

    2.       数据的插入

    在构造map容器后,我们就可以往里面插入数据了。这里讲三种插入数据的方法:

    第一种:用insert函数插入pair数据,下面举例说明(以下代码虽然是随手写的,应该可以在VC和GCC下编译通过,大家可以运行下看什么效果,在VC下请加入这条语句,屏蔽4786警告  #pragma warning (disable:4786) )

    #include <map>

    #include <string>

    #include <iostream>

    Using namespace std;

    Int main()

    {

           Map<int, string> mapStudent;

           mapStudent.insert(pair<int, string>(1, “student_one”));

           mapStudent.insert(pair<int, string>(2, “student_two”));

           mapStudent.insert(pair<int, string>(3, “student_three”));

           map<int, string>::iterator  iter;

           for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)

    {

           Cout<<iter->first<<”   ”<<iter->second<<end;

    }

    }

    第二种:用insert函数插入value_type数据,下面举例说明

    #include <map>

    #include <string>

    #include <iostream>

    Using namespace std;

    Int main()

    {

           Map<int, string> mapStudent;

           mapStudent.insert(map<int, string>::value_type (1, “student_one”));

           mapStudent.insert(map<int, string>::value_type (2, “student_two”));

           mapStudent.insert(map<int, string>::value_type (3, “student_three”));

           map<int, string>::iterator  iter;

           for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)

    {

           Cout<<iter->first<<”   ”<<iter->second<<end;

    }

    }

    第三种:用数组方式插入数据,下面举例说明

    #include <map>

    #include <string>

    #include <iostream>

    Using namespace std;

    Int main()

    {

           Map<int, string> mapStudent;

           mapStudent[1] =  “student_one”;

           mapStudent[2] =  “student_two”;

           mapStudent[3] =  “student_three”;

           map<int, string>::iterator  iter;

           for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)

    {

           Cout<<iter->first<<”   ”<<iter->second<<end;

    }

    }

    以上三种用法,虽然都可以实现数据的插入,但是它们是有区别的,当然了第一种和第二种在效果上是完成一样的,用insert函数插入数据,在数据的插入上涉及到集合的唯一性这个概念,即当map中有这个关键字时,insert操作是插入数据不了的,但是用数组方式就不同了,它可以覆盖以前该关键字对应的值,用程序说明

    mapStudent.insert(map<int, string>::value_type (1, “student_one”));

    mapStudent.insert(map<int, string>::value_type (1, “student_two”));

    上面这两条语句执行后,map中1这个关键字对应的值是“student_one”,第二条语句并没有生效,那么这就涉及到我们怎么知道insert语句是否插入成功的问题了,可以用pair来获得是否插入成功,程序如下

    Pair<map<int, string>::iterator, bool> Insert_Pair;

    Insert_Pair = mapStudent.insert(map<int, string>::value_type (1, “student_one”));

    我们通过pair的第二个变量来知道是否插入成功,它的第一个变量返回的是一个map的迭代器,如果插入成功的话Insert_Pair.second应该是true的,否则为false。

    下面给出完成代码,演示插入成功与否问题

    #include <map>

    #include <string>

    #include <iostream>

    Using namespace std;

    Int main()

    {

           Map<int, string> mapStudent;

    Pair<map<int, string>::iterator, bool> Insert_Pair;

           Insert_Pair = mapStudent.insert(pair<int, string>(1, “student_one”));

           If(Insert_Pair.second == true)

           {

                  Cout<<”Insert Successfully”<<endl;

           }

           Else

           {

                  Cout<<”Insert Failure”<<endl;

           }

           Insert_Pair = mapStudent.insert(pair<int, string>(1, “student_two”));

           If(Insert_Pair.second == true)

           {

                  Cout<<”Insert Successfully”<<endl;

           }

           Else

           {

                  Cout<<”Insert Failure”<<endl;

           }

           map<int, string>::iterator  iter;

           for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)

    {

           Cout<<iter->first<<”   ”<<iter->second<<end;

    }

    }

    大家可以用如下程序,看下用数组插入在数据覆盖上的效果

    #include <map>

    #include <string>

    #include <iostream>

    Using namespace std;

    Int main()

    {

           Map<int, string> mapStudent;

           mapStudent[1] =  “student_one”;

           mapStudent[1] =  “student_two”;

           mapStudent[2] =  “student_three”;

           map<int, string>::iterator  iter;

           for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)

    {

           Cout<<iter->first<<”   ”<<iter->second<<end;

    }

    }

    3.       map的大小

    在往map里面插入了数据,我们怎么知道当前已经插入了多少数据呢,可以用size函数,用法如下:

    Int nSize = mapStudent.size();

    4.       数据的遍历

    这里也提供三种方法,对map进行遍历

    第一种:应用前向迭代器,上面举例程序中到处都是了,略过不表

    第二种:应用反相迭代器,下面举例说明,要体会效果,请自个动手运行程序

    #include <map>

    #include <string>

    #include <iostream>

    Using namespace std;

    Int main()

    {

           Map<int, string> mapStudent;

           mapStudent.insert(pair<int, string>(1, “student_one”));

           mapStudent.insert(pair<int, string>(2, “student_two”));

           mapStudent.insert(pair<int, string>(3, “student_three”));

           map<int, string>::reverse_iterator  iter;

           for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)

    {

           Cout<<iter->first<<”   ”<<iter->second<<end;

    }

    }

    第三种:用数组方式,程序说明如下

    #include <map>

    #include <string>

    #include <iostream>

    Using namespace std;

    Int main()

    {

           Map<int, string> mapStudent;

           mapStudent.insert(pair<int, string>(1, “student_one”));

           mapStudent.insert(pair<int, string>(2, “student_two”));

           mapStudent.insert(pair<int, string>(3, “student_three”));

           int nSize = mapStudent.size()

    //此处有误,应该是 for(int nIndex = 1; nIndex <= nSize; nIndex++)


    //by rainfish

           for(int nIndex = 0; nIndex < nSize; nIndex++)

    {

           Cout<<mapStudent[nIndex]<<end;

    }

    }

    5.       数据的查找(包括判定这个关键字是否在map中出现)

    在这里我们将体会,map在数据插入时保证有序的好处。

    要判定一个数据(关键字)是否在map中出现的方法比较多,这里标题虽然是数据的查找,在这里将穿插着大量的map基本用法。

    这里给出三种数据查找方法

    第一种:用count函数来判定关键字是否出现,其缺点是无法定位数据出现位置,由于map的特性,一对一的映射关系,就决定了count函数的返回值只有两个,要么是0,要么是1,出现的情况,当然是返回1了

    第二种:用find函数来定位数据出现位置,它返回的一个迭代器,当数据出现时,它返回数据所在位置的迭代器,如果map中没有要查找的数据,它返回的迭代器等于end函数返回的迭代器,程序说明

    #include <map>

    #include <string>

    #include <iostream>

    Using namespace std;

    Int main()

    {

           Map<int, string> mapStudent;

           mapStudent.insert(pair<int, string>(1, “student_one”));

           mapStudent.insert(pair<int, string>(2, “student_two”));

           mapStudent.insert(pair<int, string>(3, “student_three”));

           map<int, string>::iterator iter;

           iter = mapStudent.find(1);

    if(iter != mapStudent.end())

    {

           Cout<<”Find, the value is ”<<iter->second<<endl;

    }

    Else

    {

           Cout<<”Do not Find”<<endl;

    }

    }

    第三种:这个方法用来判定数据是否出现,是显得笨了点,但是,我打算在这里讲解

    Lower_bound函数用法,这个函数用来返回要查找关键字的下界(是一个迭代器)

    Upper_bound函数用法,这个函数用来返回要查找关键字的上界(是一个迭代器)

    例如:map中已经插入了1,2,3,4的话,如果lower_bound(2)的话,返回的2,而upper-bound(2)的话,返回的就是3

    Equal_range函数返回一个pair,pair里面第一个变量是Lower_bound返回的迭代器,pair里面第二个迭代器是Upper_bound返回的迭代器,如果这两个迭代器相等的话,则说明map中不出现这个关键字,程序说明

    #include <map>

    #include <string>

    #include <iostream>

    Using namespace std;

    Int main()

    {

           Map<int, string> mapStudent;

           mapStudent[1] =  “student_one”;

           mapStudent[3] =  “student_three”;

           mapStudent[5] =  “student_five”;

           map<int, string>::iterator  iter;

    iter = mapStudent.lower_bound(2);

    {

           //返回的是下界3的迭代器

           Cout<<iter->second<<endl;

    }

    iter = mapStudent.lower_bound(3);

    {

           //返回的是下界3的迭代器

           Cout<<iter->second<<endl;

    }

     

    iter = mapStudent.upper_bound(2);

    {

           //返回的是上界3的迭代器

           Cout<<iter->second<<endl;

    }

    iter = mapStudent.upper_bound(3);

    {

           //返回的是上界5的迭代器

           Cout<<iter->second<<endl;

    }

     

    Pair<map<int, string>::iterator, map<int, string>::iterator> mapPair;

    mapPair = mapStudent.equal_range(2);

    if(mapPair.first == mapPair.second)
           {

           cout<<”Do not Find”<<endl;

    }

    Else

    {

    Cout<<”Find”<<endl;
    }

    mapPair = mapStudent.equal_range(3);

    if(mapPair.first == mapPair.second)
           {

           cout<<”Do not Find”<<endl;

    }

    Else

    {

    Cout<<”Find”<<endl;
    }

    }

    6.       数据的清空与判空

    清空map中的数据可以用clear()函数,判定map中是否有数据可以用empty()函数,它返回true则说明是空map

    7.       数据的删除

    这里要用到erase函数,它有三个重载了的函数,下面在例子中详细说明它们的用法

    #include <map>

    #include <string>

    #include <iostream>

    Using namespace std;

    Int main()

    {

           Map<int, string> mapStudent;

           mapStudent.insert(pair<int, string>(1, “student_one”));

           mapStudent.insert(pair<int, string>(2, “student_two”));

           mapStudent.insert(pair<int, string>(3, “student_three”));

     

    //如果你要演示输出效果,请选择以下的一种,你看到的效果会比较好

           //如果要删除1,用迭代器删除

           map<int, string>::iterator iter;

           iter = mapStudent.find(1);

           mapStudent.erase(iter);

     

           //如果要删除1,用关键字删除

           Int n = mapStudent.erase(1);//如果删除了会返回1,否则返回0

     

           //用迭代器,成片的删除

           //一下代码把整个map清空

           mapStudent.earse(mapStudent.begin(), mapStudent.end());

           //成片删除要注意的是,也是STL的特性,删除区间是一个前闭后开的集合

     

           //自个加上遍历代码,打印输出吧

    }

    8.       其他一些函数用法

    这里有swap,key_comp,value_comp,get_allocator等函数,感觉到这些函数在编程用的不是很多,略过不表,有兴趣的话可以自个研究

    9.       排序

    这里要讲的是一点比较高深的用法了,排序问题,STL中默认是采用小于号来排序的,以上代码在排序上是不存在任何问题的,因为上面的关键字是int型,它本身支持小于号运算,在一些特殊情况,比如关键字是一个结构体,涉及到排序就会出现问题,因为它没有小于号操作,insert等函数在编译的时候过不去,下面给出两个方法解决这个问题

    第一种:小于号重载,程序举例

    #include <map>

    #include <string>

    Using namespace std;

    Typedef struct tagStudentInfo

    {

           Int      nID;

           String   strName;

    }StudentInfo, *PStudentInfo;  //学生信息

     

    Int main()

    {

        int nSize;

           //用学生信息映射分数

           map<StudentInfo, int>mapStudent;

        map<StudentInfo, int>::iterator iter;

           StudentInfo studentInfo;

           studentInfo.nID = 1;

           studentInfo.strName = “student_one”;

           mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));

           studentInfo.nID = 2;

           studentInfo.strName = “student_two”;

    mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));

     

    for (iter=mapStudent.begin(); iter!=mapStudent.end(); iter++)

        cout<<iter->first.nID<<endl<<iter->first.strName<<endl<<iter->second<<endl;

     

    }

    以上程序是无法编译通过的,只要重载小于号,就OK了,如下:

    Typedef struct tagStudentInfo

    {

           Int      nID;

           String   strName;

           Bool operator < (tagStudentInfo const& _A) const

           {

                  //这个函数指定排序策略,按nID排序,如果nID相等的话,按strName排序

                  If(nID < _A.nID)  return true;

                  If(nID == _A.nID) return strName.compare(_A.strName) < 0;

                  Return false;

           }

    }StudentInfo, *PStudentInfo;  //学生信息

    第二种:仿函数的应用,这个时候结构体中没有直接的小于号重载,程序说明

    #include <map>

    #include <string>

    Using namespace std;

    Typedef struct tagStudentInfo

    {

           Int      nID;

           String   strName;

    }StudentInfo, *PStudentInfo;  //学生信息

     

    Classs sort

    {

           Public:

           Bool operator() (StudentInfo const &_A, StudentInfo const &_B) const

           {

                  If(_A.nID < _B.nID) return true;

                  If(_A.nID == _B.nID) return _A.strName.compare(_B.strName) < 0;

                  Return false;

           }

    };

     

    Int main()

    {

           //用学生信息映射分数

           Map<StudentInfo, int, sort>mapStudent;

           StudentInfo studentInfo;

           studentInfo.nID = 1;

           studentInfo.strName = “student_one”;

           mapStudent.insert(pair<StudentInfo, int>(studentInfo, 90));

           studentInfo.nID = 2;

           studentInfo.strName = “student_two”;

    mapStudent.insert(pair<StudentInfo, int>(studentInfo, 80));

    }

    10.   另外

    由于STL是一个统一的整体,map的很多用法都和STL中其它的东西结合在一起,比如在排序上,这里默认用的是小于号,即less<>,如果要从大到小排序呢,这里涉及到的东西很多,在此无法一一加以说明。

    还要说明的是,map中由于它内部有序,由红黑树保证,因此很多函数执行的时间复杂度都是log2N的,如果用map函数可以实现的功能,而STL  Algorithm也可以完成该功能,建议用map自带函数,效率高一些。

    下面说下,map在空间上的特性,否则,估计你用起来会有时候表现的比较郁闷,由于map的每个数据对应红黑树上的一个节点,这个节点在不保存你的数据时,是占用16个字节的,一个父节点指针,左右孩子指针,还有一个枚举值(标示红黑的,相当于平衡二叉树中的平衡因子),我想大家应该知道,这些地方很费内存了吧,不说了……






    展开全文
  • 这意味着我们需要时刻留意哈希表的尺寸以及当前表中已有的元素数量。因为一旦哈希表中有太多元素,也将很难找到可用的位置来存放我们新插入的元素,因此这里我们需要引入一个重要的术语,负载系数(Load Factor)负载...

    开放寻址是其中一种缓解散列冲突的编程技术,当使用开放寻址作为冲突解决技术时,键值对存储在表(数组)中,而不是像单独链表那样的数据结构中。这意味着我们需要时刻留意哈希表的尺寸以及当前表中已有的元素数量。因为一旦哈希表中有太多元素,也将很难找到可用的位置来存放我们新插入的元素,因此这里我们需要引入一个重要的术语,负载系数(Load Factor)

    负载系数

    4e4286bc17493b8ae6f14ae425984721.png


    其实就是表中已有元素个数和表尺寸的比例,我们要密切关注这个系数的是因为哈希表的O(1)恒定时间行为假设负载因子k保持一定的固定值,这意味着一旦k>阈值,我们就需要增加表的大小(理想情况下是指数增长,例如,两倍)

    517b898d56cdeb4e6334a45e1eec71dd.png


    在上图中,你会看到有两种缓解冲突的方法,即单独链表和线性探测(Linear Probing),在开放寻址(线性探测)技术看来,一旦达到某个阀值,它的时间复杂度就会呈现指数级恶化的趋势

    当我们想要将键值对插入哈希表时,我们对键进行哈希处理并获得该键值对所属位置的原始位置。如果我们的键被散列到的位置被占用(此时出现了冲突),对于开放寻址来说,同一个位置中不允许有两个键的,这不是数组的工作方式,我们要做的是使用一个探测序列函数(Probing Seque Function) 这里简称p(x),因为我们已从散列函数获取了冲突点的所在位置,现在我们使用p(x)进行探测直到在沿途发现一个空闲的位置为止

    探测函数

    您可以提出无限数量的探测序列,这里仅提及一些常见的探测函数:

    • 线性探测(Linear Probing):p(x)= kx + b其中a,b是常数
    • 二次探测(Quaratic Probing):p(x)= ax ^ 2 + bx + c,其中a,b,c是常数
    • 双重散列(Double Hashing):p(k,x)= x * h(k),其中h(k)是辅助s散列函数
    • 伪随机数发生器(Pseudo Random Number Generator): p(k,x)= x*RNG(h(k),x)其中RNG是以H(k)作为种子的随机数生成器函数

    本篇仅介绍线性探测函数进行线性探测,因此给定输入参数x,当我们进行探测时,我们通常会将变量x初始化为0或1作为一个起点,如果我们找不到空闲的位置,会依次将x增加1,对以上所有这些探测函数都是一样的

    开放寻址的通用算法

    接下来,这是一个通用的开放寻址插入算法,假设我们有一个表的尺寸为n,开放寻址算法首先会初始化变量x=1,因为x是一个变量,我们要用它来探测,每当我们未能到达闲置的位置时,都需要递增x,然后我们通过散列函数获得keyHash,而实际上我们首先要查看表的索引,当表索引被占用意味着它不为空,那么新索引就是我们散列的最初位置(keyHash所指向的起始索引)加上探测函数的总和再于表尺寸N取模运算得到整数,由于我们总是回到表里,在循环中要递增x。下一次当我们在不同的位置探测时,在while循环中,最终我们会找到一个空闲的位置

    x=1keyHash=h(k)index=keyHashwhile table[index]!=NULL:      index=(keyHash+p(k,x)) mod N      x=x+1insert(k,v,index) 

    死循环地狱(Chaos with Cycle)

    由于我们知道负载系数被控制在一定的范围内,所以这里有个问题,就是开放寻址中的探测函数存在缺陷--死循环地狱,以表尺寸N为模的大多数随机选择的探测序列将产生比表大小N更短的循环。当您尝试插入一个键-值对并且循环中的所有存储桶都被占用时,这将成为灾难性问题,因为您将陷入无限循环,这在一些老外谈及哈希表的相关文章中有一个非常有趣的昵称叫死循环地狱(Chaos with Cycle)

    为了生动说明什么叫死循环地狱,我们这里看一个例子,这里有一个尺寸为12的哈希表,并且使用开放寻址插入了一些键值对,,该哈希表已经部分填充。 占用的单元格填充有键值对(Ki,Vi)和带有空令牌Φ的空单元格,如下图所示

    7002536b795afe4966059f7707786b97.png

    假设我们使用探测序列函数p(x)=4x,并且在表中插入一个新的键值对,并且该键值对的散列值为8,即h(x)=8这意味着我们会在索引8的位置插入该键值对,但是该位置已被占用,因为这里已经有简直对(k5,v5),所以我们该怎么办呢?接下来,我们需要进行探测,所以我们计算: index=h(k)+p(1)=8+4 mod 12=0

    此时,如下图,此时探测函数会跳转到索引为0的位置,糟糕的是索引1的位置也被占用了,因为(k1,v1)已经存在.

    a78a462e9e581b904abb5dc9cd3cc92b.png
    • 当x=2时,即index=h(k)+p(2)=(8+8) mod 12=4,探测函数会跳跃到索引4的位置,同样这里也是被占用的,如此类推
    • 当x=3时,即index=h(k)+p(3)=(8+12) mod 12=8,p(x)跳跃到索引8的位置,该位置被占用
    • 当x=4时,即index=h(k)+p(4)=(8+16) mod 12=0,p(x)跳跃到索引0的位置,该位置被占用
    • 当x=5时,即index=h(k)+p(5)=(8+20) mod 12=4,p(x)跳跃到索引4的位置,该位置被占用
      .....

    这样尽管我们具有探测函数,但这种特定的情况下它一直在一个死循环里面一直做一些毫无意义的事情。

    由这个例子我们可知探测函数存在缺陷,他们产生的周期短于表的尺寸,因此,我们要如何处理产生小于表大小的周期的探测功能?一般来说,一致的看法是我们不处理这个问题,相反,我们通过将探测函数的范围限制在那些产生长度为N的循环的函数上来避免这个问题,我们选择的那些产生的周期正好为N的探测函数,并且这些探测函数确实存在。

    线性探测、二次探测和双重散列等技术都受到死循环地狱问题的影响,这就是为什么与这些方法一起使用的探测函数非常特殊的原因。这是一个很大的话题,将是接下来几篇文章会重点讲述这些,我们目前需要做的是重新定义非常具体的探测函数,这些函数会产生一个循环长度为表尺寸N,并且避免无法插入元素或陷入无限循环

    注意,开放寻址对使用的哈希函数和探测函数非常敏感。如果使用单独的链接作为冲突解决方法,则不必担心此问题。

    小结

    我们本篇用一个反例生动地介绍了开放寻址插入算法的底层是由探测函数和散列函数相互作用的结果,同时我们也介绍了一些探测函数的固有缺陷,就是死循环地狱,下一篇我们会详细讨论线性探测函数的原理,敬请期待。


    链接:https://www.jianshu.com/p/b8c47701dd07

    展开全文
  • C++哈希表

    2020-08-24 10:32:03
    哈希表原理3.c++哈希表接口的使用 1.什么是哈希表 散列表(Hash table 也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过关键码值映射到表中一个位置来访问记录,以加快查找的...

    1.什么是哈希表

    散列表(Hash table 也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    2.哈希表原理

    给定表M,存在函数f(key),对任意给定的关键字key,代入函数后若能得到包含关键字的记录在表中的地址,则称表M为哈希表(Hash Table),函数f(key)为哈希函数。
    基本概念:
    (1)若关键字为k,则其值存放在f(k)的存储位置上。由此,不需要比较便可直接取得所查记录。称这个对应关系f为散列函数,按这个意思建立的表为散列表。
    (2)对不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)=f(k2),这种现象称为碰撞。具有相同函数值的关键字对该散列函数来说乘坐同义词。综上所述,根据散列函数f(k)和处理碰撞的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。
    (3)若对于关键字集合中的任一关键字,经散列函数映射到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数,这就使关键字经过散列函数得到一个“随机的地址”,从而减少碰撞。
    几种常见的哈希表设计方法以及解决哈希冲突的方法:
    哈希表的原理和使用
    完美哈希(重点,面试中经常会被问到)
    当关键字的集合是一个不变的静态集合(Static)时,哈希技术还可以用来获取出色的最坏情况性能。如果某一种哈希技术在进行查找时,其最坏情况时间复杂度是O(1) ,则称其为完美哈希(Perfect Hashing)。
    完美哈希表的设计:https://blog.csdn.net/tiankong_/article/details/76769230

    3.c++中哈希表接口的使用

    头文件#include<hash_map>,并非标准库中的,但绝大部分都实现
    http://blog.csdn.net/tiankong_/article/details/76718467

    展开全文
  • C++哈希表的实现

    2021-01-23 21:22:15
    C++哈希表的实现前言源码如下: 前言 本篇文章为笔者的读书笔记,未经允许请勿转载。如果对你有帮助记得点个赞(●’◡’●) 本文主要讲的哈希表的创建和使用, 源码如下: main #include <iostream> #...

    C++哈希表的实现


    前言

    本篇文章为笔者的读书笔记,未经允许请勿转载。如果对你有帮助记得点个赞(●’◡’●)
    本文主要讲的哈希表的创建和使用。哈希表的存储方式是不可逆,存储的value是经过哈希算法得到,所以只是获得存储中的value是毫无意义的,它只是密码经过哈希算法后得到的数值。


    源码如下:

    main

    #include <iostream>
    #include<string>
    #include"HashTable.hpp"
    using namespace std;
    void test()
    {
        //创建一个有15个节点的哈希表;
        HashTable<string> ht(15);
        
        bool is;
        cout << boolalpha;
        is = ht.insert(11, "A");
        cout << is << endl;
        is = ht.insert(22, "B");
        cout << is << endl;
        is = ht.insert(33, "C");
        cout << is << endl;
        is = ht.insert(44, "D");
        cout << is << endl;
        is = ht.insert(45, "D");
        cout << is << endl;
        is = ht.insert(55, "E");
        cout << is << endl;
        is = ht.insert(66, "F");
        cout << is << endl;
        is = ht.insert(77, "G");
        cout << is << endl;
        is = ht.insert(88, "H");
        cout << is << endl;
    
        cout << "-------------------------" << endl;
        ht.out();
        cout << "-------------------------" << endl;
    
        try
        {
            cout << ht.search(44) << endl;
        }
        catch (const char* str)
        {
            cout << str << endl;
        }
        ht.remove(45);
    
        cout << "-------------------------" << endl;
        ht.out();
        cout << "-------------------------" << endl;
    
        HashTable<string> ht1(ht);//调用拷贝构造
        try
        {
            cout << ht1.search(45) << endl;
        }
        catch (const char* str)
        {
            cout << str << endl;
        }
        cout << "-------------------------" << endl;
        ht1.out();
    
    }
    int main()
    {
        test();
        system("pause");
        return 0;
    }
    测试结果:
    true
    true
    true
    true
    true
    true
    true
    true
    true
    -------------------------
    [0]->nil
    [1]->(11:A)->(55:E)->nil
    [2]->nil
    [3]->nil
    [4]->nil
    [5]->nil
    [6]->nil
    [7]->(88:H)->nil
    [8]->(44:D)->nil
    [9]->(45:D)->nil
    [10]->nil
    [11]->(77:G)->nil
    [12]->(66:F)->nil
    [13]->(22:B)->(33:C)->nil
    [14]->nil
    -------------------------
    D//查询的数据
    -------------------------
    [0]->nil
    [1]->(11:A)->(55:E)->nil
    [2]->nil
    [3]->nil
    [4]->nil
    [5]->nil
    [6]->nil
    [7]->(88:H)->nil
    [8]->(44:D)->nil
    [9]->nil
    [10]->nil
    [11]->(77:G)->nil
    [12]->(66:F)->nil
    [13]->(22:B)->(33:C)->nil
    [14]->nil
    -------------------------
    没有这个数据//删除的数据
    -------------------------
    [0]->nil
    [1]->(11:A)->(55:E)->nil
    [2]->nil
    [3]->nil
    [4]->nil
    [5]->nil
    [6]->nil
    [7]->(88:H)->nil
    [8]->(44:D)->nil
    [9]->nil
    [10]->nil
    [11]->(77:G)->nil
    [12]->(66:F)->nil
    [13]->(22:B)->(33:C)->nil
    [14]->nil
    

    HashTable.hpp

    #pragma once
    #include<list>
    #include<utility>//pair
    template <class T>
    class HashTable
    {
    	public:
    		HashTable(int len):length(len),count(0) 
    		{
    			data = new hash_table[length]();//堆内存
    			//hash_table data[length]();栈内存
    
    		}
    		//拷贝构造
    		HashTable(const HashTable& ht):length(ht.length)
    		{
    			this->data = new hash_table[length]();
    			for (int i = 0; i < length; i++)
    			{
    				this->data[i] = ht.data[i];
    			}
    		}
    		~HashTable()
    		{
    			if (data)
    			{
    				delete[] data;
    				data = nullptr;
    			}
    		}
    		//插入数据
    		bool insert(int key, T val)
    		{
    			//通过hash运算再求余的方法插入位置,也可以用其他办法,自由发挥。
    			int base = hash(key) % length;
    			for (auto e:data[base])
    			{
    				if (e.first == key)
    				{
    					return false;
    				}
    			}
    			//数组里面的每一个元素都是一个list,二list里面的每一个元素是pair。
    			data[base].push_back({ key,val });
    			return true;
    		}
    		//查找数据
    		T search(int key)
    		{
    			int base = hash(key) % length;
    			for (auto e : data[base])
    			{
    				if (e.first == key)
    				{
    					return e.second;
    				}
    			}
    			throw "没有这个数据";
    		}
    		//删除数据
    		bool remove(int key)
    		{
    			int base = hash(key) % length;
    			for (auto it = data[base].begin(); it != data[base].end(); it++)
    			{
    				if (it->first == key)
    				{
    					data[base].erase(it);
    					return true;
    				}
    			}
    			return false;
    		}
    		//输出
    		void out()
    		{
    			for (int i = 0; i < length; i++)
    			{
    				std::cout << "[" << i << "]" << "->";
    				for (const auto& e : data[i])
    				{
    					std::cout <<"("<< e.first << ":" << e.second <<")"<< "->";
    				}
    				std::cout << "nil\n";
    			}
    		}
    private:
    	using hash_table = std::list<std::pair<int, T>>;
    	int length = 0;
    	int count = 0;
    	hash_table * data=nullptr;
    	//计算hash值的函数,对于频繁访问的hash函数可以用inline来使用更少的栈内存
    	inline int hash(int key)
    	{	
    		return key^10;
    	}
    };
    

    哈希表的实现原理不懂的可以参考一下
    可视化哈希表

    展开全文
  • 目录1、概念2、散列表的构造方法2.1、直接定址法 ...采用散列技术将记录存储在一块存储空间中,这块连续空间称为散列表或哈希表(Hash-Table)。 2、散列表的构造方法 2.1、直接定址法 直接定址法使用
  • C++标准库中使用的unordered_map底层实现是哈希表,关于哈希表的一些基础知识,我看了公众号代码随想录里面的推文:《关于哈希表,你该了解这些!》,有了基本的认识。 哈希表是什么:哈希表是根据关键码的值而直接...
  • C++哈希表使用

    万次阅读 2019-07-13 22:31:46
    C++中的STL提供了hash_map来实现哈希表功能,在介绍hash_map的使用方法之前,我们先从哈希函数和哈希冲突来了解哈希表。 一、 哈希函数 所谓哈希函数就是从关键字(Key)到值(Value)的映射: Value=H(Key)Value=H...
  • C++ 哈希表的原理

    2021-01-15 15:01:56
    什么是Hash? Hash也称为散列、哈希。 其基本的原理就是把任意长度的输入、通过Hash算法变成固定长度的...上面就是使用MD5对数据加密的一个案例: 原始值:这是一个测试文案 映射后的Hash值:2124968af757ed51e71e6abea
  • C++哈希表unordered_map,推荐使用

    千次阅读 2017-03-17 21:37:19
    这题我竟然在想其他的歪点子,没想到第二次直接从数组0位置开始遍历(好蠢)(而不是哈希容器),不要动不动就想遍历哈希容器。 class Solution { public: int FirstNotRepeatingChar(string str) { if(str.empty...
  • C++ 实现哈希表的实例

    2020-08-29 13:58:28
    主要介绍了C++ 实现哈希表的实例的相关资料,这里使用C++实现哈希表的实例帮助大家彻底理解哈希表的原理,需要的朋友可以参考下
  • 这意味着我们需要时刻留意哈希表的尺寸以及当前表中已有的元素数量。因为一旦哈希表中有太多元素,也将很难找到可用的位置来存放我们新插入的元素,因此这里我们需要引入一个重要的术语,负载系数(Load Factor)负载...
  • 哈希表c++中map与unordered_map的区别内部实现机理优缺点以及适用处map 优点map缺点unordered_map 优点unordered_map 缺点unordered_map是hash_map的替代名称hash_map原理unordered_map详解1. 原型2. 说明3. 容器...
  • 提示:本文是关于C++中哈希表(unordered_map)的使用,看完之后相信你会对C++哈希表使用有一定的理解 文章目录一、插入和便利二、查找三、修改四、擦除五、交换六、清空七、insert() 的返回值总结 一、插入和...
  • C++哈希表

    2018-10-04 15:08:58
    C/C++哈希表、字典表 将字符串的key,转成整数,使用整数找到对应的value;** Hash算法将字符串转成整数,同样的Hash值得 key:value会放到一个集合里面,由于Hash能使得不同的字符串尽量有不同的整数值(仍然有重复); ...
  • C++中的 unordered_map使用时通过键值对进行插入,并通过find(key)进行寻找键值是否存在。 //iterator find (key) : 找到则返回对应键值得迭代器 //没有找到则返回unordered_map::end. // unordered_map::find ...
  • 这是数据结构中关于哈希表这个知识的实现,是使用C++实现的,那么希望能够对学校数据结构的哈希表这个知识点的朋友能有帮助
  • //建立基本数据类型的哈希表 unordered_map<int,int> m; //<string,string>,<char,char> //向哈希表中添加元素 1.insert 函数 m.insert(pair<int,int>(1, 10)); m.insert(pair<int,int&...
  • C++数据结构哈希表

    2014-04-01 19:58:56
    数据结构课上的哈希表事例。适宜初学者使用和参考

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 649
精华内容 259
关键字:

c++哈希表使用

c++ 订阅