精华内容
下载资源
问答
  • python-哈希表使用

    2020-08-24 22:17:49
    将数字作为键装入哈希表,输出值大于1的键: def findnum_dic(nums_list): result = {} for x in nums_list: if result.get(x): result[x] = result.get(x) + 1 else: result[x] = 1 return [i for...
    1. 输入一个列表,里面装有n个数,以列表形式输出其中重复的数字。

    将数字作为键装入哈希表,输出值大于1的键:

    def findnum_dic(nums_list):
    	result = {}
    	for x in nums_list:
    		if result.get(x):
    			result[x] = result.get(x) + 1
    		else:
    			result[x] = 1
    			
    	return [i for i in result if result[i]>1]
    

    注意:

    list(result.keys())   
    # 用表格装下所有键
    
    1. 输入str1,str2两个字符串,判断是否str2的所有字符都在str1中

    直接对字符进行判断:

        result = True
        for x in str2:
            if x not in str1:
                result = False
        print(result)
    

    使用哈希表的方式:

    def dj2(str1,str2):
        dic1 = {}
        for x in str1:
            if dic1.get(x):
                dic1[x] = dic1.get(x) + 1
            else:
                dic1[x] = 1
        result = True
        for x in str2:
            if dic1.get(x) and dic1[x]>0:
                dic1[x] = dic1.get(x) - 1
            else:
                result = False
                break
        print(result)
    
    展开全文
  • C++哈希表使用的好文章-Hash_Map

    热门讨论 2010-05-17 12:38:24
    hash_map基于hash table(哈希表)。 哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间...
  • 哈希表JS简化 在计算中,哈希表(哈希表)是一种实现关联数组抽象数据类型的数据结构,该结构可以将键映射到值。 哈希表使用哈希函数来计算存储桶或插槽数组的索引,从中可以找到所需的值。
  • 本文为大家分享了C语言基于哈希表实现通讯录的具体代码,供大家参考,具体内容如下 1.需求分析 本演示程序用C语言编写,完成哈希表的生成,电话号码的插入、以及查找等功能。  (1)按提示输入相应的联系人的相关...
  • 本篇文章只要是对js中哈希表的几种用法进行了总结介绍,需要的朋友可以过来参考下,希望对大家有所帮助
  • 哈希表底层实现

    2021-01-20 13:46:03
    哈希表使用数组作为主干,实现查找,插入,删除元素的时间复杂度为O(1)。 哈希表(key,value) 就是把Key通过一个固定的算法函数既哈希函数转换成一个整型数字,然后将该数字对数组长度进行取余,取余结果就当作数组...
  • 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个字节的,一个父节点指针,左右孩子指针,还有一个枚举值(标示红黑的,相当于平衡二叉树中的平衡因子),我想大家应该知道,这些地方很费内存了吧,不说了……






    展开全文
  • C++之哈希表使用

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

    C++中的STL提供了hash_map来实现哈希表功能,在介绍hash_map的使用方法之前,我们先从哈希函数和哈希冲突来了解哈希表。

    一、 哈希函数

    所谓哈希函数就是从关键字(Key)到值(Value)的映射:
    V a l u e = H ( K e y ) Value=H(Key) Value=H(Key)
    值反映了关键字的存储地址。
    1、数字分析法
    选取关键字中的几位数字作为值,一般选取数字分布比较均匀的几位。
    H ( k 1 k 2 k 3 k 4 k 5 k 6 k 7 ) = k 2 k 3 k 5 H(k_1 k_2 k_3 k_4 k_5 k_6 k_7)= k_2 k_3 k_5 H(k1k2k3k4k5k6k7)=k2k3k5
    2、直接定址法
    选取线性函数作为哈希函数
    H ( K e y ) = a ∗ K e y + b H(Key)=a*Key+b H(Key)=aKey+b
    3、折叠法
    将关键字分成数字相同的几段(最后一段数字可以不够),然后相加得到值。
    H ( k 1 k 2 k 3 k 4 k 5 k 6 k 7 ) = ( k 1 + k 4 + k 7 ) ( k 2 + k 5 ) ( k 3 + k 6 ) H(k_1 k_2 k_3 k_4 k_5 k_6 k_7)=( k_1+k_4+k_7)( k_2+k_5)( k_3+k_6) H(k1k2k3k4k5k6k7)=(k1+k4+k7)(k2+k5)(k3+k6)
    k 1 k 2 k 3 k_1 k_2 k_3 k1k2k3
    k 4 k 5 k 6 k_4 k_5 k_6 k4k5k6
    + k 7 + k_7 +k7
    4、平方取中法
    将关键字求平方之后选取中间的几位作为值
    5、除留余数法
    关键字除以 P P P得到的余数作为值,其中P为小于哈希表长度的最大质数。
    H ( K e y ) = K e y M O D P H(Key)=Key \quad MOD \quad P H(Key)=KeyMODP
    6、随机数法
    选取一个随机函数作为哈希函数
    H ( K e y ) = r a n d o m ( K e y ) H(Key)=random(Key) H(Key)=random(Key)

    二、 哈希冲突

    对于不同的关键字,经过哈希函数的映射可能得到相同的值,也就是发生了冲突,下面介绍几种解决哈希冲突的方法
    1、公共溢出区法
    新建一块内存用来存储发生冲突的数据
    2、再探测法
    当发生冲突时,通过一个函数为关键字寻找新的值:
    V a l u e = ( H ( K e y ) + d i ) M O D L Value=(H(Key)+d_i) \quad MOD \quad L Value=(H(Key)+di)MODL
    其中 L L L为哈希表的长度,根据 d i d_i di的取值不同可以细分为以下三种方法:

    • 线性探测法
      d i = 1 , 2 , ⋯ , L − 1 d_i=1,2,⋯,L-1 di=12L1

    • 平方探测法
      d i = 1 2 , − 1 2 , 2 2 , − 2 2 , ⋯ d_i=1^2,-1^2,2^2,-2^2,⋯ di=12122222

    • 随机探测法
      这时 d i d_i di取的是一组随机数

    3、再哈希法
    当发生冲突时,再进行一次哈希函数,当然这个哈希函数可以和前面的相同,也可以不同
    V a l u e = R H ( H ( K e y ) ) Value=RH(H(Key)) Value=RH(H(Key))
    4、链地址法
    链地址法是一种将数组与链表结合的方法,这也是最常用的一种方法,将相同值的不同关键字存放于一个链表中,不同的链表即不同的值构成了一个数组。

    三、 unordered_map的使用

    1、头文件:

    #include< unordered_map>
    

    2、定义一个哈希表(我们以Key和Value都是int变量为例):

    unordered_map<int,int> Hash;
    

    3、哈希表的建立有下面几种方法:

    Hash[1]=3;
    Hash.insert<make_pair(1,3)>;
    Hash.insert({ {1,3},{2,4} });
    

    4、迭代器

    unordered_map<int,int>::iterator it;
    

    5、利用迭代器访问变量:

    it->first;
    it->second;
    

    6、哈希表的查找:

    it=Hash.find(1);
    

    若找不到,返回的是Hash.end();
    7、修改哈希表:

    Hash[1] = 4;
    

    8、清除哈希表:

    Hash.erase(1);
    Hash.clear();
    

    以上我们介绍了哈希表的几个基本用法,详细的介绍可以访问下方的网址:
    https://docs.microsoft.com/en-us/previous-versions/visualstudio/visual-studio-2008/bb982522(v=vs.90)

    展开全文
  • C语言基于哈希表的电话簿
  • 哈希表实现通讯录

    2018-01-23 12:11:22
    (1)每个人的信息至少包括姓名,...(2)假设人名为汉语拼音全拼形式,待插入哈希表的长度为你所在班级的人数。哈希函数用除留余数法构造,采用链地址法或二次探测再散列法解决冲突。 (3)完成菜单设计。操作有必要的提示。
  • 哈希表词典

    2017-08-01 14:53:14
    功能:利用哈希表实现英文翻译功能 注:限输入英文查找相应汉语意思,秒出答案 有个别词查不到的话,那是因为词库不全
  • 哈希表查找

    2017-04-27 20:54:24
    对于哈希表的查找一些简介
  • 搜索引擎 目前只支持英文字母,即不支持... 哈希表是从头开始实现的--- std::hash未使用--- 具有功能。 快速统计:该程序大约需要 4 秒钟来初始化哈希表,扫描大小约为 100 兆字节的文件并创建一个哈希表进行搜索。
  • 基于哈希表的词典,其中包含单词拼写检查功能,使用最长公共子序列完成。大学课程设计作业,有很多不足之处,主要在于分享思路,介意请勿下载。
  • /为班级30个人的姓名设计一个哈希表,假设姓名用汉语拼音表示。要求用除留余数法 构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限为2。 编写数据结构和算法来实现。要求:将哈希函数和处理冲突方法...
  • 文件clear - 清除哈希表display - 显示一个哈希表对象元素 - 获取所有哈希表元素get - 从哈希表中获取数据hashtable - HashTable 类的构造函数isempty - 检查哈希值是否为空iskey - 检查散列当前是否正在使用密钥键 ...
  • 哈希表的原理和使用(C++代码)

    万次阅读 多人点赞 2018-08-12 22:48:32
    概念 散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f,是的每个关键字key对应一个存储位置f(key)...采用散列技术将记录存储在一块连续的存储空间中,这块连续空间称为散列表或哈希表(Hash-Tab...

    一、概念

    散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f,是的每个关键字key对应一个存储位置f(key)。查找时,根据这个对应的关系找到给定值key的映射f(key),若查找集合中存在这个记录,则必定在f(key)的位置上。我们把这种对应关系f成为散列函数,又称为哈希(Hash)函数。采用散列技术将记录存储在一块连续的存储空间中,这块连续空间称为散列表或哈希表(Hash-Table)。

    二、散列表的构造方法

    2.1 直接定址法

    直接定址法使用下面的公式
    f ( k e y ) = a × k e y + b , b 为 常 数 f(key) = a×key+b,b为常数 f(key)=a×key+b,b
    比如统计出生年份,那么就可以使用 f ( k e y ) = k e y − 1990 f(key) = key-1990 f(key)=key1990来计算散列地址。
    在这里插入图片描述

    2.2 除留取余法

    这种方法是最常用的散列函数构造方法,对于表长为m的散列公式为
    f ( k e y ) = k e y m o d    p ( p ≤ m ) f(key)=key \mod p (p \leq m) f(key)=keymodp(pm)
    在这里插入图片描述

    2.3 数字分析法

    分析数字关键字在各位上的变化情况,取比较随机的位作为散列地址这里使用一个手机号码作为例子,手机号码是一个字符串,一般的说,后面4位是真正的用户号。
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20190310214023289.png)

    2.4 折叠法

    把关键词分割成位数相同的几个部分,然后叠加。
    在这里插入图片描述

    2.5 平方取中法

    在这里插入图片描述

    三、冲突解决方法

    常用处理冲突的思路:

    • 换个位置: 开放地址法
    • 同一位置的冲突对象组织在一起: 链地址法

    3.1 开放地址法

    一旦产生了冲突(该地址已有其它元素),就按某种规则去寻找另一空地址.若发生了第 i 次冲突,试探的下一个地址将增加 d i d_i di, 基本公式是:
    h i ( k e y ) = ( h ( k e y ) + d i ) m o d    T a b l e S i z e ( 1 ≤ i < T a b l e S i z e ) h_i(key) = (h(key)+d_i) \mod TableSize ( 1≤ i < TableSize ) hi(key)=(h(key)+di)modTableSize(1i<TableSize)
    这里面 d i d_i di 决定了不同的解决冲突方案: **线性探测、平方探测、双散列。**下面依次介绍各中方法。

    3.1.1 线性探测法

    线性探测法以增量序列 1 , 2 , … … , ( T a b l e S i z e − 1 ) 1, 2, ……,(TableSize -1) 12TableSize1)循环试探下一个存储地址。
    【例1】 设关键词序列为 47 , 7 , 29 , 11 , 9 , 84 , 54 , 20 , 30 {47, 7, 29, 11, 9, 84, 54, 20, 30} 4772911984542030,散列表表长 T a b l e S i z e = 11 TableSize =11 TableSize=11 (装填因子 α = 9 / 13 ≈ 0.69 α= 9/13 ≈ 0.69 α=9/130.69),散列函数为: h ( k e y ) = k e y m o d    11 h(key) = key \mod 11 h(key)=keymod11。 用线性探测法处理冲突,列出依次插入后的散列表,并估算查找性能。

    【解】 初步的散列地址如下表所示。

    关键词 ( k e y ) (key) (key)4772911984542030
    散列地址 h ( k e y ) h(key) h(key)3770971098

    可以看出,有多个关键词的散列地址发生了冲突,具体见下表。

    关键词 ( k e y ) (key) (key)4772911984542030
    散列地址 h ( k e y ) h(key) h(key)3770971098
    冲突次数001003136

    具体的哈希表构建过程可以用下面的图表来表示
    在这里插入图片描述

    这里引出一下散列表的的查找性能分析,散列表的查找性能,一般有两种方法

    • 成功平均查找长度(ASLs)
    • 不成功平均查找长度 (ASLu)

    对于上面一题的散列地址冲突次数为

    散列地址 h ( k e y ) h(key) h(key)0123456789101112
    关键词 ( k e y ) (key) (key)1130477299845420
    冲突次数060010313

    ASLs: 查找表中关键词的平均查找比较次数(其冲突次数加1)
    A S L s = ( 1 + 7 + 1 + 1 + 2 + 1 + 4 + 2 + 4 ) / 9 = 23 / 9 ≈ 2.56 ASLs = (1+7+1+1+2+1+4+2+4) / 9 = 23/9 ≈ 2.56 ASLs=1+7+1+1+2+1+4+2+4/9=23/92.56

    ASLu:不在散列表中的关键词的平均查找次数(不成功)
    一般方法:将不在散列表中的关键词分若干类。
    如:根据H(key)值分类
    A S L u = ( 3 + 2 + 1 + 2 + 1 + 1 + 1 + 9 + 8 + 7 + 6 ) / 11 = 41 / 11 ≈ 3.73 ASL u= (3+2+1+2+1+1+1+9+8+7+6) / 11 = 41/11 ≈ 3.73 ASLu=3+2+1+2+1+1+1+9+8+7+6/11=41/113.73

    • 参考代码
    #include<iostream>
    #include <stdlib.h>
    using namespace std;
    
    
    #define SUCCESS 1
    #define UNSUCCESS 0
    #define HASHSIZE 12
    #define NULLKEY -32768
    typedef bool Status ;
    typedef struct 
    {
    	int *elem;
    	int count;
    }HashTable;
    
    int m = 0;   //the length of HashTable
    
    
    //Initialize  of HashTable
    Status InitHashTable(HashTable* H)
    {
    	int i;
    	m = HASHSIZE;
    	H->count = m;
    	H->elem = (int*)malloc(m*sizeof(int));
    	for(i = 0;i < m; i++)
    	{
    		H->elem[i] = NULLKEY;
    	}
    	return true;
    }
    
    //hash function
    int Hash(int key)
    {
    	return key % m; 
    }
    
    //Insert the elem to the Hahtable
    void InsertHash(HashTable* H,int key)
    {
    	int addr = Hash(key);  //get the address of hash
    	while(H->elem[addr] != NULLKEY)     //Conflict
    		addr = (addr+1) % m;
    	H->elem[addr] = key;
    }
    
    
    //search the key
    Status searchHash(HashTable H,int key,int *addr)
    {
    	*addr = Hash(key);
    	while(H.elem[*addr] != key)
    	{
    		*addr = (*addr+1) % m;
    		if(H.elem[*addr] == NULLKEY || *addr == Hash(key))
    			//return the origin
    			return UNSUCCESS;
    	}
    	return SUCCESS;
    }
    
    int main()
    {
    	return 0;
    }
    

    3.1.2 平方探测法

    平方探测法以增量序列 1 2 , − 1 2 , 2 2 , − 2 2 , . . . , q 2 1^2 ,-1^2 ,2^2 ,-2^2 ,...,q^2 12,12,22,22,...,q2,且 q ≤ ⌊ T a b l e S i z e / 2 ⌋ q ≤ \lfloor TableSize/2 \rfloor qTableSize/2 循环试探下一个存储地址。还是使用[例1],得到的冲突如下表

    关键词 key4772911984542030
    散列地址h(key)3770971098
    冲突次数001002033

    A S L s = ( 1 + 1 + 2 + 1 + 1 + 3 + 1 + 4 + 4 ) / 9 = 18 / 9 = 2 ASLs =(1+1+2+1+1+3+1+4+4)/ 9 = 18/9 = 2 ASLs=(1+1+2+1+1+3+1+4+4)/9=18/9=2
    在这里插入图片描述

    • 参考代码
    /*******************************************************************************
    功    能:哈希表——平方探测法(+/- 1^2,2^2,3^2...)
    创建时间: 2018-07-24
    作    者:Elvan
    修改时间:
    作    者:
    ********************************************************************************/
    
    #include <iostream>
    #include <string>
    #include <vector>
    #include <cmath>
    #include <malloc.h>
    using namespace std;
    
    #define MAXTABLESIZE 10000 //允许开辟的最大散列表长度
    typedef int ElementType;
    typedef enum
    {
        Legitimate,
        Empty,
        Deleted
    } EntryType; //散列单元的状态类型
    
    struct HashEntry
    {
        ElementType data; //存放的元素
        EntryType state;  //单元状态
    };
    
    typedef struct HashEntry Cell;
    
    struct TblNode
    {
        int tablesize; //表的最大长度
        Cell *cells;   //存放散列单元数据的数组
    };
    typedef struct TblNode *HashTable;
    
    /*返回大于n且不超过MAXTABLESIZE的最小素数*/
    int NextPrime(int n)
    {
        int p = (n % 2) ? n + 2 : n + 1; //从大于n的下一个奇数开始
        int i;
        while (p <= MAXTABLESIZE)
        {
            for (i = (int)sqrt(p); i > 2; i--)
            {
                if ((p % i) == 0)
                    break;
            }
            if (i == 2)
                break; //说明是素数,结束
            else
                p += 2;
        }
        return p;
    }
    
    /*创建新的哈希表*/
    HashTable CreateTable(int table_size)
    {
        HashTable h = (HashTable)malloc(sizeof(TblNode));
        h->tablesize = NextPrime(table_size);
        h->cells = (Cell *)malloc(h->tablesize * sizeof(Cell));
        //初始化哈希表状态为空单元
        for (int i = 0; i < h->tablesize; i++)
        {
            h->cells[i].state = Empty;
        }
        return h;
    }
    
    /*查找数据的初始位置*/
    int Hash(ElementType key, int n)
    {
        return key % 11; //假设为11
    }
    
    /*查找元素位置*/
    int Find(HashTable h, ElementType key)
    {
        int current_pos, new_pos;
        int collision_num = 0; //记录冲突次数
    
        new_pos = current_pos = Hash(key, h->tablesize); //初始散列位置
    
        //当该位置元素为非空并且不是要找的元素的时候,发生冲突
        while (h->cells[new_pos].state != Empty && h->cells[new_pos].data != key)
        {
            collision_num++;
            if (collision_num % 2) //处理奇数冲突
            {
                new_pos = current_pos + (collision_num + 1) * (collision_num + 1) / 4;
                if (new_pos >= h->tablesize)
                    new_pos = new_pos % h->tablesize;
            }
            else //处理偶数冲突
            {
                new_pos = current_pos - (collision_num) * (collision_num) / 4;
                while (new_pos < 0)
                    new_pos += h->tablesize; //调整到合适大小
            }
        }
        return new_pos;
    }
    
    
    /*插入新的元素*/
    bool Insert(HashTable h,ElementType key)
    {
        int pos = Find(h,key);  //先查找key是否存在
        if(h->cells[pos].state != Legitimate)
        {
            h->cells[pos].state = Legitimate;
            h->cells[pos].data = key;
            return true;
        }
        else
        {
            cout << "键值已存在!"<<endl;
            return false;
        }
    }
    
    
    int main(int argc, char const *argv[])
    {
        int a[] = {47,7,29,11,9,84,54,20,30};
        int n = 9;
        HashTable h = CreateTable(n);
        for(int i = 0;i < n;i++)
        {
            Insert(h,a[i]);  //插入元素
        }
        for(int i = 0;i < h->tablesize;i++)
        {
            cout << h->cells[i].data << " ";  //打印哈希表元素
        }
        cout << endl;
        return 0;
    }
    
    

    3.2 链地址法

    链地址法就是将相应位置上冲突的所有关键词存储在同一个单链表中
    【例2】 设关键字序列为 47 , 7 , 29 , 11 , 16 , 92 , 22 , 8 , 3 , 50 , 37 , 89 , 94 , 21 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21 47,7,29,11,16,92,22,8,3,50,37,89,94,21,散列函数取为 h ( k e y ) = k e y m o d    11 h(key) = key \mod 11 h(key)=keymod11,用分离链接法处理冲突。
    在这里插入图片描述
    【解】表中有9个结点只需1次查找,5个结点需要2次查找,所以查找成功的平均查找次数为
    A S L s = ( 9 + 5 ∗ 2 ) / 14 ≈ 1.36 ASLs=(9+5*2)/ 14 ≈ 1.36 ASLs=(9+52)/141.36

    • 参考代码
    /*******************************************************************************
    功    能:哈希表——链表法(+/- 1^2,2^2,3^2...)
    创建时间: 2018-07-24
    作    者:Elvan
    修改时间:
    作    者:
    ********************************************************************************/
    
    #include <iostream>
    #include <string>
    #include <vector>
    #include <cmath>
    #include <malloc.h>
    using namespace std;
    
    #define MAXTABLESIZE 10000 //允许开辟的最大散列表长度
    #define KEYLENGTH 100      //关键字的最大长度
    
    typedef int ElementType;
    struct LNode
    {
        ElementType data;
        LNode *next;
    };
    typedef LNode *PtrToNode;
    typedef PtrToNode LinkList;
    struct TblNode
    {
        int tablesize;  //表的最大长度
        LinkList heads; //存放散列单元数据的数组
    };
    typedef struct TblNode *HashTable;
    
    /*返回大于n且不超过MAXTABLESIZE的最小素数*/
    int NextPrime(int n)
    {
        int p = (n % 2) ? n + 2 : n + 1; //从大于n的下一个奇数开始
        int i;
        while (p <= MAXTABLESIZE)
        {
            for (i = (int)sqrt(p); i > 2; i--)
            {
                if ((p % i) == 0)
                    break;
            }
            if (i == 2)
                break; //说明是素数,结束
            else
                p += 2;
        }
        return p;
    }
    
    /*创建新的哈希表*/
    HashTable CreateTable(int table_size)
    {
        HashTable h = (HashTable)malloc(sizeof(TblNode));
        h->tablesize = NextPrime(table_size);
        h->heads = (LinkList)malloc(h->tablesize * sizeof(LNode));
        //初始化表头结点
        for (int i = 0; i < h->tablesize; i++)
        {
            h->heads[i].next = NULL;
        }
        return h;
    }
    
    /*查找数据的初始位置*/
    int Hash(ElementType key, int n)
    {
        //这里只针对大小写
        return key % 11;
    }
    
    /*查找元素位置*/
    LinkList Find(HashTable h, ElementType key)
    {
        int pos;
    
        pos = Hash(key, h->tablesize); //初始散列位置
    
        LinkList p = h->heads[pos].next; //从链表的第一个节点开始
        while (p && key != p->data)
        {
            p = p->next;
        }
    
        return p;
    }
    
    /*插入新的元素*/
    bool Insert(HashTable h, ElementType key)
    {
        LinkList p = Find(h, key); //先查找key是否存在
        if (!p)
        {
            //关键词未找到,可以插入
            LinkList new_cell = (LinkList)malloc(sizeof(LNode));
            new_cell->data = key;
            int pos = Hash(key, h->tablesize);
            new_cell->next = h->heads[pos].next;
            h->heads[pos].next = new_cell;
            return true;
        }
        else
        {
            cout << "键值已存在!" << endl;
            return false;
        }
    }
    
    /*销毁链表*/
    void DestroyTable(HashTable h)
    {
        int i;
        LinkList p, tmp;
        //释放每个节点
        for (i = 0; i < h->tablesize; i++)
        {
            p = h->heads[i].next;
            while (p)
            {
                tmp = p->next;
                free(p);
                p = tmp;
            }
        }
        free(h->heads);
        free(h);
    }
    
    int main(int argc, char const *argv[])
    {
        int a[] = {47, 7, 29,29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21};
        int n = 15;
        HashTable h = CreateTable(n);
        for (int i = 0; i < n; i++)
        {
            Insert(h, a[i]); //插入元素
        }
        for (int i = 0; i < h->tablesize; i++)
        {
            LinkList p = h->heads[i].next;
            while (p)
            {
                cout << p->data << " "; //打印哈希表元素
                p = p->next;
            }
            cout << endl;
        }
        return 0;
    }
    
    
    展开全文
  • Hashtable中key/value键值对均为object类型,所以Hashtable可以支持任何类型的key/value键值对 <BR><BR>在哈希表中添加一个key/value键值对:HashtableObject.Add(key,value); 在哈希表中去除某个key/value键值对:...
  • 这是数据结构中关于哈希表这个知识的实现,是使用C++实现的,那么希望能够对学校数据结构的哈希表这个知识点的朋友能有帮助
  • 一、javascript哈希表简介 javascript里面是没有哈希表的,一直在java,C#中有时候用到了这一种数据结构,javascript里面若没有,感觉非常不顺手。细细看来,其实javascript的object的属性其实与哈希表非常类似。 如: ...
  • 哈希表的c语言实现1

    2019-03-01 16:29:42
    哈希表的哈希取余法和链表地址法来实现哈希表的基本操作。。。
  • 哈哈 英雄联盟的哈希表 不推荐使用代替
  • 福 建 工 程 学 院 课 程 设 计 课程 题目 专业 班级 座号 姓名 算法与数据结构 哈希表 网络工程 xxxxxx 班 xxxxxxxxxxxx xxxxxxx 2011 年 12 月 31 日 实验题目哈希表 一 要解决的问题 针对同班同学信息设计一个...
  • 关于哈希表使用和特点

    千次阅读 2017-08-23 15:08:10
    原文出处: 研究者July  说明:本文分为三部分内容,第一部分为一道百度面试题Top...搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。 假设目前有一千万个记录
  • C++ 中哈希表(unordered_map)的使用

    千次阅读 2021-03-13 20:28:30
    提示:本文是关于C++中哈希表(unordered_map)的使用,看完之后相信你会对C++哈希表使用有一定的理解 文章目录一、插入和便利二、查找三、修改四、擦除五、交换六、清空七、insert() 的返回值总结 一、插入和...
  • 哈希表设计.rar

    2019-05-22 14:10:05
    针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,完成相应的建表和查表程序。 【基本要求】 假设人名为中国人姓名的汉语拼音形式。带填入哈希表的人名共有30个。哈希函数用除留余数法构造,用线性...
  • 通过使用哈希表对XML文件进行查询
  • C++哈希表用法

    千次阅读 2019-08-31 11:08:18
    hash用法,记得几个关键的, 引入 #include 定义 unordered_map, string> unomap; 引入的时候可以定义初始化,例如 unordered_map,string> unomap ={{1,"dd"},{2,"ssss"}}; 打印查找: ...
  • 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。 [测试数据] 取读者周围较熟悉的30个人名

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 351,351
精华内容 140,540
关键字:

哈希表使用