精华内容
下载资源
问答
  • 数据结构之数据应用总结篇(一)数据在字符串操作程序中应用由于数组中的内存是连续的,于是可以根据下标在O(1)时间读/写任何元素,因此它的时间效率是很高的,我们可以利用数组时间效率高的优点,用数组来实现简单...

    (一)数组实现哈希表在字符串操作程序中应用

    由于数组中的内存是连续的,于是可以根据下标在O(1)时间读/写任何元素,因此它的时间效率是很高的,我们可以利用数组时间效率高的优点,用数组来实现简单的哈希表,即把数组的小标设为哈希表的键值(Key),而把数组中的每一个数字设为哈希表的值(Value),这样每一个下标及数组中该下标对应的数字就组成了一个键-值的配对。

    应用1:第一个只出现一次的字符

    题目描述:在一个字符串中找出第一个只出现一次的字符,如输入”abaccdeff”,输出’b’.

    解题思路:
    用数组创建一个简单的哈希表来存储每一个字符出现的次数,再次遍历字符串,并用O(1)的时间判断该字符是否只出现了一次

    #include<iostream>
    #include<string.h>
    using namespace std;
    
    char FirstNotRepeatingChar(char *pString)
    {
        if(pString == NULL)
            return NULL;
        const int hash_size=256;
        int hashTable[hash_size];
        for(int i=0;i<hash_size;i++)
            hashTable[i]=0;
        int len=strlen(pString);
        for(int i=0;i<len;i++)
        {
            char ch=pString[i];
            ++hashTable[ch];
        }
    
        //while(*pString!='\0')//此时pString已指向尾部
        for(int i=0;i<len;i++)
        {
            char ch=pString[i];
            if(hashTable[ch]==1)
                return ch;
        }
        return '\0';
    }
    
    int main()
    {
        char s[1000];
        cin.getline(s,1000);
        char ch=FirstNotRepeatingChar(s);
        cout<<ch<<endl;
    }

    应用2:定义一个函数,输入两个字符串,从第一个字符串中删除在第二个字符串中出现过的所有字符。例如,从第一个字符串“We are stduents”中删除在第二个字符串”aeio”中出现过的字符得到的结果时”W r stdnts”.

    解题思路:
    创建一个用数组实现的简单哈希表来存储第二个字符串,从头到尾扫描第一个字符串的每一个字符时,用O(1)时间判断该字符是不是在第二个字符中

    #include<iostream>
    #include<string>
    using namespace std;
    
    string DeleteChar(const string &s1,const string &s2)
    {
        string Result;
        bool hashTable[256]={0};
        char ch;
        for(size_t i=0;i<s2.size();i++)
        {
            ch=s2[i];
            if(!hashTable[ch])
                hashTable[ch]=1;
        }
        for(size_t i=0;i<s1.size();i++)
        {
            ch=s1[i];
            if(!hashTable[ch])
                Result.push_back(ch);
        }
        return Result;
    }
    string DeleteChar2(const string &s1,const string &s2)
    {
        string Result;
        char ch;
        for(size_t i=0;i<s1.size();i++)
        {
            ch=s1[i];
            if(s2.find_first_of(ch)==string::npos)
                Result.push_back(ch);
        }
        return Result;
    }
    int main()
    {
        string s1,s2;
        getline(cin,s1);
        getline(cin,s2);
        cout<<DeleteChar(s1,s2)<<endl;
        cout<<DeleteChar(s1,s2)<<endl;
    }
    

    应用3:定义一个函数,删除字符串中所有重复出现的字符。例如输入”google”,删除重复的字符之后得到”gole”

    解题思路:
    创建一个用布尔型数组实现的简单哈希表,数组中的元素的意义是其下标看做ASCII码后对应的字母在字符串中是否已经出现

    #include<iostream>
    #include<string>
    using namespace std;
    
    void DeleteRepeatingChar(const string &s)
    {
        bool hashTable[256]={false};
        char ch;
        for(string::size_type i=0;i<s.size();i++)
        {
            ch=s[i];
            if(!hashTable[ch])
            {
                cout<<ch;
                hashTable[ch]=true;
            }
        }
    }
    int main()
    {
        string str;
        getline(cin,str);
        DeleteRepeatingChar(str);
        cout<<endl;
        return 0;
    }

    应用4:变位词判断

    在英语中,如果两个单词中出现的字母相同,并且每个字母出现的次数也相同,那么这两个单词互为变为词(Anagram),例如silent和listen,evil和live等为变位词

    解题思路:
    创建一个数组实现的简单哈希表,用来统计字符串出现的次数,当扫描到第一个字符串中的每一字符时,为哈希表对应的项的值加1,接下来扫描第二个字符串,扫描到每个字符串时,为哈希表中对应的项的值减1,如果扫描第二个字符串后,哈希表中所有的值都为0,那么这两个字符串就互为变为词

    #include<iostream>
    #include<string>
    using namespace std;
    bool Anagram(const string &s1,const string &s2)
    {
        int HashTable[256]={0};
        char ch;
        for(string::size_type i=0;i<s1.size();i++)
        {
            ch=s1[i];
            HashTable[ch]++;
        }
        for(string::size_type i=0;i<s2.size();i++)
        {
            ch=s2[i];
            HashTable[ch]--;
        }
        for(int j=0;j<256;j++)
            if(HashTable[j] != 0)
                return false;
        return true;
    }
    int main()
    {
        string s1,s2;
        cin>>s1>>s2;
        if(Anagram(s1,s2))
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    展开全文
  • 一个设计哈希查找的简单应用

    本次笔记内容:
    11.5 文件中单词词频统计

    题目

    在这里插入图片描述

    如上图,对单词词频进行统计。

    分析

    在这里插入图片描述

    如上图,涉及到对已有单词进行查找,因此要进行单词的管理,使用散列表。

    程序框架

    int main()
    {
        int TableSize = 10000; // 散列表的估计大小
        int wordcount = 0, length;
        HashTable H;
        ElementType word;
        FILE *fp;
        char document[30] = "HarryPotter.txt"; // 要被统计词频的文件名
        H = InitializeTable(TableSize);        // 建立散列表
        if ((fp = fopen(document, "r")) == NULL)
            FatalError("无法打开文件!\n");
        while (!feof(fp))
        {
            length = GetAWord(fp, word);
            if (length > 3)	// 只考虑适当长度的单词
            {
                wordcount++;
                InsertAndCount(word, H);
            }
        }
        fclose(fp);
        printf("该文档共出现%d个有效单词", wordcount);
        Show(H, 10.0 / 100); // 显示词频前10%的所有单词
        DestroyTable(H);
        return 0;
    }
    

    在这里插入图片描述

    如上图,Show函数做4件事。

    展开全文
  • 数据结构哈希表

    千次阅读 2013-11-17 14:24:37
    哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0(1)的时间级。实际上,这...
    哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0(1)的时间级。实际上,这只需要几条机器指令。
    

      对哈希表的使用者一一人来说,这是一瞬间的事。哈希表运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常使用哈希表(例如拼写检查器)哈希表的速度明显比树快,树的操作通常需要O(N)的时间级。哈希表不仅速度快,编程实现也相对容易。

      哈希表也有一些缺点它是基于数组的,数组创建后难于扩展某些哈希表被基本填满时,性能下降得非常严重,所以程序虽必须要清楚表中将要存储多少数据(或者准备好定期地把数据转移到更大的哈希表中,这是个费时的过程)。

      而且,也没有一种简便的方法可以以任何一种顺序〔例如从小到大〕遍历表中数据项。如果需要这种能力,就只能选择其他数据结构。

    然而如果不需要有序遍历数据,井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

    哈希表算法-哈希表的概念及作用

      一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上,查找的效率依赖于查找过程中所进行的比较次数。

      理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。

    哈希表最常见的例子是以学生学号为关键字的成绩表,1号学生的记录位置在第一条,10号学生的记录位置在第10条...

    如果我们以学生姓名为关键字,如何建立查找表,使得根据姓名可以直接找到相应记录呢?

    哈希表算法哈希表算法

    用上述得到的数值作为对应记录在表中的位置,得到下表:

    哈希表算法哈希表算法

    上面这张表即哈希表。

    如果将来要查李秋梅的成绩,可以用上述方法求出该记录所在位置:

    李秋梅:lqm 12+17+13=42 取表中第42条记录即可。

    问题:如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录?

    这个问题是哈希表不可避免的,即冲突现象:对不同的关键字可能得到同一哈希地址。

    哈希表算法-哈希表的构造方法(哈希函数)

    1、直接定址法

    例如:有一个从1到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。

               但这种方法效率不高,时间复杂度是O(1),空间复杂度是O(n),n是关键字的个数

    哈希表算法哈希表算法

    2、数字分析法

    有学生的生日数据如下:

    年.月.日

    75.10.03
    75.11.23
    76.03.02
    76.07.12
    75.04.21
    76.02.15
    ...

    经分析,第一位,第二位,第三位重复的可能性大,取这三位造成冲突的机会增加,所以尽量不取前三位,取后三位比较好。

    3、平方取中法

    取关键字平方后的中间几位为哈希地址

    4、折叠法

    将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法。

    例如:每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则:

    哈希表算法哈希表算法

    5、除留余数法

    取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

    H(key)=key MOD p (p<=m)

    6、随机数法

    选择一个随机函数,取关键字的随机函数值为它的哈希地址,即

    H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

    5、除留余数法

    取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

    H(key)=key MOD p (p<=m)

    6、随机数法

    选择一个随机函数,取关键字的随机函数值为它的哈希地址,即

    H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

    5、除留余数法

    取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

    H(key)=key MOD p (p<=m)

    6、随机数法

    选择一个随机函数,取关键字的随机函数值为它的哈希地址,即

    H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

    哈希表算法-处理冲突的方法


    哈希表算法

    如果两个同学分别叫 刘丽 刘兰,当加入刘兰时,地址24发生了冲突,我们可以以某种规律使用其它的存储位置,如果选择的一个其它位置仍有冲突,则再选下一个,直到找到没有冲突的位置。选择其它位置的方法有:

    1、开放定址法

    Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)

    其中m为表长,di为增量序列

    如果di值可能为1,2,3,...m-1,称线性探测再散列。

    如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)

    称二次探测再散列

    如果di取值可能为伪随机数列。称伪随机探测再散列。

    例:在长度为11的哈希表中已填有关键字分别为17,60,29的记录,现有第四个记录,其关键字为38,由哈希函数得到地址为5,若用线性探测再散列,如下:

    哈希表算法哈希表算法

    2、再哈希法

    当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。

    3、链地址法

    将所有关键字为同义词的记录存储在同一线性链表中。

    哈希表算法哈希表算法

    4、建立一个公共溢出区

    假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

     

    哈希表算法的编写

    hash表,有时候也被称为散列表。个人认为,hash表是介于链表和二叉树之间的一种中间结构。链表使用十分方便,但是数据查找十分麻烦;二叉树中的数据严格有序,但是这是以多一个指针作为代价的结果。hash表既满足了数据的查找方便,同时不占用太多的内容空间,使用也十分方便。

        打个比方来说,所有的数据就好像许许多多的书本。如果这些书本是一本一本堆起来的,就好像链表或者线性表一样,整个数据会显得非常的无序和凌乱,在你找到自己需要的书之前,你要经历许多的查询过程;而如果你对所有的书本进行编号,并且把这些书本按次序进行排列的话,那么如果你要寻找的书本编号是n,那么经过二分查找,你很快就会找到自己需要的书本;但是如果你每一个种类的书本都不是很多,那么你就可以对这些书本进行归类,哪些是文学类,哪些是艺术类,哪些是工科的,哪些是理科的,你只要对这些书本进行简单的归类,那么寻找一本书也会变得非常简单,比如说如果你要找的书是计算机方面的书,那么你就会到工科一类当中去寻找,这样查找起来也会显得麻烦。

        不知道这样举例你清楚了没有,上面提到的归类方法其实就是hash表的本质。下面我们可以写一个简单的hash操作代码。

        a)定义hash表和基本数据节点

    1. typedef struct _NODE 
    2.     int data; 
    3.     struct _NODE* next; 
    4. }NODE; 
    5.  
    6. typedef struct _HASH_TABLE 
    7.     NODE* value[10]; 
    8. }HASH_TABLE; 
    typedef struct _NODE
    {
    	int data;
    	struct _NODE* next;
    }NODE;
    
    typedef struct _HASH_TABLE
    {
    	NODE* value[10];
    }HASH_TABLE;
    


        b)创建hash表

    1. HASH_TABLE* create_hash_table() 
    2.     HASH_TABLE* pHashTbl = (HASH_TABLE*)malloc(sizeof(HASH_TABLE)); 
    3.     memset(pHashTbl, 0, sizeof(HASH_TABLE)); 
    4.     return pHashTbl; 
    HASH_TABLE* create_hash_table()
    {
    	HASH_TABLE* pHashTbl = (HASH_TABLE*)malloc(sizeof(HASH_TABLE));
    	memset(pHashTbl, 0, sizeof(HASH_TABLE));
    	return pHashTbl;
    }


        c)在hash表当中寻找数据

    1. NODE* find_data_in_hash(HASH_TABLE* pHashTbl, int data) 
    2.     NODE* pNode; 
    3.     if(NULL ==  pHashTbl) 
    4.         return NULL; 
    5.  
    6.     if(NULL == (pNode = pHashTbl->value[data % 10])) 
    7.         return NULL; 
    8.  
    9.     while(pNode){ 
    10.         if(data == pNode->data) 
    11.             return pNode; 
    12.         pNode = pNode->next; 
    13.     } 
    14.     return NULL; 
    NODE* find_data_in_hash(HASH_TABLE* pHashTbl, int data)
    {
    	NODE* pNode;
    	if(NULL ==  pHashTbl)
    		return NULL;
    
    	if(NULL == (pNode = pHashTbl->value[data % 10]))
    		return NULL;
    
    	while(pNode){
    		if(data == pNode->data)
    			return pNode;
    		pNode = pNode->next;
    	}
    	return NULL;
    }


        d)在hash表当中插入数据

    1. STATUS insert_data_into_hash(HASH_TABLE* pHashTbl, int data) 
    2.     NODE* pNode; 
    3.     if(NULL == pHashTbl) 
    4.         return FALSE; 
    5.  
    6.     if(NULL == pHashTbl->value[data % 10]){ 
    7.         pNode = (NODE*)malloc(sizeof(NODE)); 
    8.         memset(pNode, 0, sizeof(NODE)); 
    9.         pNode->data = data; 
    10.         pHashTbl->value[data % 10] = pNode; 
    11.         return TRUE; 
    12.     } 
    13.  
    14.     if(NULL != find_data_in_hash(pHashTbl, data)) 
    15.         return FALSE; 
    16.  
    17.     pNode = pHashTbl->value[data % 10]; 
    18.     while(NULL != pNode->next) 
    19.         pNode = pNode->next; 
    20.  
    21.     pNode->next = (NODE*)malloc(sizeof(NODE)); 
    22.     memset(pNode->next, 0, sizeof(NODE)); 
    23.     pNode->next->data = data; 
    24.     return TRUE; 
    STATUS insert_data_into_hash(HASH_TABLE* pHashTbl, int data)
    {
    	NODE* pNode;
    	if(NULL == pHashTbl)
    		return FALSE;
    
    	if(NULL == pHashTbl->value[data % 10]){
    		pNode = (NODE*)malloc(sizeof(NODE));
    		memset(pNode, 0, sizeof(NODE));
    		pNode->data = data;
    		pHashTbl->value[data % 10] = pNode;
    		return TRUE;
    	}
    
    	if(NULL != find_data_in_hash(pHashTbl, data))
    		return FALSE;
    
    	pNode = pHashTbl->value[data % 10];
    	while(NULL != pNode->next)
    		pNode = pNode->next;
    
    	pNode->next = (NODE*)malloc(sizeof(NODE));
    	memset(pNode->next, 0, sizeof(NODE));
    	pNode->next->data = data;
    	return TRUE;
    }


        e)从hash表中删除数据

    1. STATUS delete_data_from_hash(HASH_TABLE* pHashTbl, int data) 
    2.     NODE* pHead; 
    3.     NODE* pNode; 
    4.     if(NULL == pHashTbl || NULL == pHashTbl->value[data % 10]) 
    5.         return FALSE; 
    6.  
    7.     if(NULL == (pNode = find_data_in_hash(pHashTbl, data))) 
    8.         return FALSE; 
    9.  
    10.     if(pNode == pHashTbl->value[data % 10]){ 
    11.         pHashTbl->value[data % 10] = pNode->next; 
    12.         goto final; 
    13.     } 
    14.  
    15.     pHead = pHashTbl->value[data % 10]; 
    16.     while(pNode != pHead ->next) 
    17.         pHead = pHead->next; 
    18.     pHead->next = pNode->next; 
    19.  
    20. final: 
    21.     free(pNode); 
    22.     return TRUE; 
    STATUS delete_data_from_hash(HASH_TABLE* pHashTbl, int data)
    {
    	NODE* pHead;
    	NODE* pNode;
    	if(NULL == pHashTbl || NULL == pHashTbl->value[data % 10])
    		return FALSE;
    
    	if(NULL == (pNode = find_data_in_hash(pHashTbl, data)))
    		return FALSE;
    
    	if(pNode == pHashTbl->value[data % 10]){
    		pHashTbl->value[data % 10] = pNode->next;
    		goto final;
    	}
    
    	pHead = pHashTbl->value[data % 10];
    	while(pNode != pHead ->next)
    		pHead = pHead->next;
    	pHead->next = pNode->next;
    
    final:
    	free(pNode);
    	return TRUE;
    }


    总结:

        1、hash表不复杂,我们在开发中也经常使用,建议朋友们好好掌握;

        2、hash表可以和二叉树形成复合结构,至于为什么,建议朋友们好好思考一下?

     

     

    哈希表算法-哈希表的实际应用

    以上就是一些关于hash以及其相关的一些基本预备知识。那么在emule里面他具体起到什么作用呢?
    大家都知道emule是基于P2P (Peer-to-peer的缩写,指的是点对点的意思的软件), 它采用了"多源文件传输协议”(MFTP,the Multisource FileTransfer Protocol)。在协议中,定义了一系列传输、压缩和打包还有积分的标准,emule 对于每个文件都有md5-hash的算法设置,这使得该文件独一无二,并且在整个网络上都可以追踪得到。
    什么是文件的hash值呢?
    MD5-Hash-文件的数字文摘通过Hash函数计算得到。不管文件长度如何,它的Hash函数计算结果是一个固定长度的数字。与加密算法不同,这一个Hash算法是一个不可逆的单向函数。采用安全性高的Hash算法,如MD5、SHA时,两个不同的文件几乎不可能得到相同的Hash结果。因此,一旦文件被修改,就可检测出来。
    当我们的文件放到emule里面进行共享发布的时候,emule会根据hash算法自动生成这个文件的hash值,他就是这个文件唯一的身份标志,它包含了这个文件的基本信息,然后把它提交到所连接的服务器。当有他人想对这个文件提出下载请求的时候, 这个hash值可以让他人知道他正在下载的文件是不是就是他所想要的。尤其是在文件的其他属性被更改之后(如名称等)这个值就更显得重要。而且服务器还提供了,这个文件当前所在的用户的地址,端口等信息,这样emule就知道到哪里去下载了。
    一般来讲我们要搜索一个文件,emule在得到了这个信息后,会向被添加的服务器发出请求,要求得到有相同hash值的文件。而服务器则返回持有这个文件的用户信息。这样我们的客户端就可以直接的和拥有那个文件的用户沟通,看看是不是可以从他那里下载所需的文件。
    对于emule中文件的hash值是固定的,也是唯一的,它就相当于这个文件的信息摘要,无论这个文件在谁的机器上,他的hash值都是不变的,无论过了多长时间,这个值始终如一,当我们在进行文件的下载上传过程中,emule都是通过这个值来确定文件。
    那么什么是userhash呢?
    道理同上,当我们在第一次使用emule的时候,emule会自动生成一个值,这个值也是唯一的,它是我们在emule世界里面的标志,只要你不卸载,不删除config,你的userhash值也就永远不变,积分制度就是通过这个值在起作用,emule里面的积分保存,身份识别,都是使用这个值,而和你的id和你的用户名无关,你随便怎么改这些东西,你的userhash值都是不变的,这也充分保证了公平性。其实他也是一个信息摘要,只不过保存的不是文件信息,而是我们每个人的信息。
    那么什么是hash文件呢?
    我们经常在emule日志里面看到,emule正在hash文件,这里就是利用了hash算法的文件校验性这个功能了,文章前面已经说了一些这些功能,其实这部分是一个非常复杂的过程,目前在ftp,bt等软件里面都是用的这个基本原理,emule里面是采用文件分块传输,这样传输的每一块都要进行对比校验,如果错误则要进行重新下载,这期间这些相关信息写入met文件,直到整个任务完成,这个时候part文件进行重新命名,然后使用move命令,把它传送到incoming文件里面,然后met文件自动删除,所以我们有的时候会遇到hash文件失败,就是指的是met里面的信息出了错误不能够和part文件匹配,另外有的时候开机也要疯狂hash,有两种情况一种是你在第一次使用,这个时候要hash提取所有文件信息,还有一种情况就是上一次你非法关机,那么这个时候就是要进行排错校验了。
    关于hash的算法研究,一直是信息科学里面的一个前沿,尤其在网络技术普及的今天,他的重要性越来越突出,其实我们每天在网上进行的信息交流安全验证,我们在使用的操作系统密钥原理,里面都有它的身影,特别对于那些研究信息安全有兴趣的朋友,这更是一个打开信息世界的钥匙,他在hack世界里面也是一个研究的焦点。
    一般的线性表、树中,记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上,查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。因而查找时,只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上,由此不需要进行比较便可直接取得所查记录。在此,称这个对应关系f为哈希函数,按这个思想建立的表为哈希表(又称为杂凑法或散列表)。
    哈希表不可避免冲突(collision)现象:对不同的关键字可能得到同一哈希地址 即key1≠key2,而hash(key1)=hash(key2)。具有相同函数值的关键字对该哈希函数来说称为同义词(synonym)。因此,在建造哈希表时不仅要设定一个好的哈希函数,而且要设定一种处理冲突的方法。可如下描述哈希表:根据设定的哈希函数H(key)和所选中的处理冲突的方法,将一组关键字映象到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应记录在表中的存储位置,这种表被称为哈希表。
    对于动态查找表而言,1) 表长不确定;2)在设计查找表时,只知道关键字所属范围,而不知道确切的关键字。因此,一般情况需建立一个函数关系,以f(key)作为关键字为key的录在表中的位置,通常称这个函数f(key)为哈希函数。(注意:这个函数并不一定是数学函数)
    哈希函数是一个映象,即:将关键字的集合映射到某个地址集合上,它的设置很灵活,只要这个地址集合的大小不超出允许范围即可。
    现实中哈希函数是需要构造的,并且构造的好才能使用的好。
    用途:加密,解决冲突问题。
    用途很广,比特精灵中就使用了哈希函数,你可以自己看看。
    具体可以学习一下数据结构和算法的书。

     

    展开全文
  • 数据结构哈希表查找姓名

    千次阅读 2019-01-05 19:37:40
    数据结构哈希表查找姓名的课程设计 有没有大神能帮忙写一下这道题,课设的题目。用C语言 问题描述:针对某个集体中人名设计哈希表,并完成相应的建表和查表程序。 要求: (1)假设人名为中国人姓名的汉语拼音形式。...

    数据结构哈希表查找姓名的课程设计。用C语言

    问题描述:针对某个集体中人名设计哈希表,并完成相应的建表和查表程序。
    要求:
    (1)假设人名为中国人姓名的汉语拼音形式。名称的长度不少于3个字符、不多于10个字符;
    (2)随机生成人名列表,个数不少于3000个,保存到文本文件中,构建哈希表时读入;
    (3)至少实现三个不同的哈希函数(采用不同的方法)和对应的冲突处理函数;
    (4)计算比较不同的方法的平均查找长度。

    展开全文
  • 数据结构---哈希表

    千次阅读 2020-05-23 14:08:23
    散列表( Hash table,也叫哈希表)是根据关键码值(key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散...
  • JS数据结构:哈希表

    千次阅读 2017-09-18 23:54:26
    哈希表也被称为散列表,Hash表是一种特殊的数据结构,它同数组、栈、链表等相比较有很明显的区别,它能够快速定位到想要查找的记录,而不是与表中存在的记录的关键字进行比较来进行查找。
  • 哈希表是实际开发中非常常用的数据结构,也很重要。了解其底层实现细节也是非常重要的。 我这篇主要是想记录一下自己的学习结果,是关于不同应用情形下实现哈希表扩容的不同方案。 哈希表 什么是哈希表 哈希表是...
  • 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • 底层实现数据结构哈希表

    千次阅读 2019-04-18 18:35:24
    哈希表时要解决两个问题,索引如何设计以及解决哈希冲突(即由键转换的索引与之前的相同)
  • 数据结构基础 哈希表 概念篇

    千次阅读 2015-08-22 09:21:39
    为什么会有哈希表这种数据结构呢?让我们用一个通俗的例子来理解: 大家一定都查过字典吧,我们知道,《新华字典》是按照读音排序的,可以理解为一个以读音为key,按升序排列的数据库。对于读音已
  • 哈希表(hash table),这种数据结构提供了键(Key)和值 (Value)的映射关系;只要给出一个Key,就可以高效查找到它所匹配的Value,时间复杂度接近于O(1) 2、哈希函数 散列表在本质上也是一个数组,可是数组只能...
  • 重温数据结构:哈希 哈希函数 哈希表

    万次阅读 多人点赞 2016-10-27 00:49:30
    在学习 HashMap 前,我们先来温习下 Hash(哈希) 的概念。 什么是 HashHash(哈希),又称“散列”。散列(hash)英文原意是“混杂”、“拼凑”、“重新表述”的意思。在某种程度上,散列是与排序相反的一种操作,...
  • 数据结构哈希表(包含哈希桶)

    千次阅读 2018-05-15 08:20:20
    哈希表详解机器代码的实现。
  • 哈希表应用实例

    万次阅读 2011-12-30 09:33:53
    1:问题描述  针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。 2:基本要求  假设人名为中国人姓名...3:数据结构设计 #ifndef _HashTest_H_
  • 数据结构(Python实现)------ 哈希表数据结构(Python实现)------ 哈希表)设计哈希表基本概念哈希表的原理设计哈希表的关键1. 哈希函数 数据结构(Python实现)------ 哈希表) 哈希表是一种使用哈希函数组织数据,...
  • 哈希表的原理是将全部数据通过某个函数来确定独特的一个存储位置,在查找某个数据时通过该函数来直接得到该数据的存储位置。所以在理想情况下该种查找方法的期望时间为O(1)。 冲突是哈希表使用过程不可避免的存在...
  • 数据结构 哈希表的原理和代码实现

    千次阅读 2017-06-11 20:18:36
    哈希法又称散列法、杂凑法以及关键字地址计算法等,相应的表称为哈希表。这种方法的基本思想是:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。创建哈希表时,把关键字为...
  • 哈希表极其应用

    2015-08-13 15:42:41
    哈希表(Hash Table)也叫散列表,是一种数据结构,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数(也叫...
  • 程序中存储的数据都可以理解为文本,文本可以是数值、可打印字符、Unicode编码等。当我们在存储结构中查找某个...哈希表分为内哈希表和外哈希表两种,内哈希表的基本数据结构是数组,关键字为k的元素存储在数组中下标
  • 数据结构复习一:哈希表的总结

    千次阅读 2017-02-01 16:06:26
    哈希表概述哈希表,是根据关键码值(key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录。由于可以根据哈希函数直接得到对应位置,哈希表的查找时间复杂度为O(1)。这是一...
  • 数据结构-哈希表(哈希集合)

    千次阅读 多人点赞 2019-05-12 17:06:05
    哈希表 部分内容来源于博主@SnailMann 前提 在实际编程中,我们常常面临着两个问题:存储和查询,这两个过程的效率往往制约着整个程序的效率,而我们常见的存储数据的数据结构比如线性表,树,图等,数据在结构中的...
  • 哈希表又名散列,能够在O(1)的预期内完成对字典的获取插入和删除操作。 哈希表hash table,记为ht,每个ht有b个桶,记为ht[1].....ht[b-1]。每个桶由s个槽组成,每个槽可以放置一条记录。 关键字为K 的一个...
  • MySQL为什么要用B+Tree作为索引的数据结构,而不用数组、哈希表、二叉树等数据结构作为索引呢
  • 数据结构-哈希表原理详解

    千次阅读 2017-08-05 14:05:35
    (摘自百度百科):散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列...
  • 【算法与数据结构 10】哈希表——高效查找的利器

    千次阅读 多人点赞 2020-09-24 17:03:21
    大家都在看的高效《数据结构与算法》!
  • 数据结构哈希表查找姓名的课程设计 有没有大神能帮忙写一下这道题,课设的题目。用C++语言 问题描述:针对某公司中花名设计哈希表,并完成相应的建表和查表程序,基本要求: (1)假设花名为汉字拼音形式。名称长度...
  • 基于先前的学习计划,最近打算深入学习Java的集合类,首先要研究的就是HashMap,在学习HashMap前,我花了几天时间温习了一下类中用到的数据结构哈希表,二叉树),并决定把所学的知识记录写成文章,本文讲述的...
  • 哈希表的出现就可以带给我们一种思路,这种思路可以用来解决特定的实际问题,就比如说我们可以将数组和链表组合成一种新的数据结构,那么我们也可以将某些数据结构进行组合,合理应用他们的优点来解决实际问题。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 109,402
精华内容 43,760
关键字:

哈希表应用数据结构

数据结构 订阅