精华内容
下载资源
问答
  • 哈希表散列冲突
    千次阅读
    2021-12-28 16:24:37

    什么是哈希表

    哈希表是一种根据关键码去寻找值的数据映射结构,该结构通过关键码映射的位置去寻找存放值的地方。

    举例说明:新华字典中,获取“暗”字详细信息,需要根据拼音an去查找拼音索引(当然也可以是偏旁索引),我们首先去查an在字典的位置,查了一下得到“安”。这过程就是键码映射,在公式里面,就是通过key去查找f(key)。其中,按就是关键字(key),f()就是字典索引,也就是哈希函数,查到的页码就是哈希值。

    一个好的哈希函数需要有以下特点:

    • 尽量使关键字对应的记录均匀分配在哈希表里面
    • 关键字极小的变化可以引起哈希值极大的变化,如time33算法

    什么是哈希冲突

    在采用哈希函数对输入域进行映射到哈希表的时候,因为哈希表的位桶的数目远小于输入域的关键字的个数,所以对于输入域的关键字来说,很可能会产生一个关键字映射到同一个位桶中的情况,这种情况就就叫做哈希冲突。

    如何解决哈希冲突

    方法一:开放定址法

    这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:

    Hi=(H(key)+di)% m   i=1,2,…,n

    其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下三种:

    (1)线性探测再散列

    di=1,2,3,…,m-1

    这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

    (2)二次探测再散列

    di=1²,-1²,2²,-2²,…,k²,-k²    ( k<=m/2 )

    这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。

    (3)伪随机探测再散列

    di=伪随机数序列。

    具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),并给定一个随机数做起点。

    例如,已知哈希表长度m=11,哈希函数为:H(key)= key  %  11,则H(47)=3,H(26)=4,H(60)=5,假设下一个关键字为69,则H(69)=3,与47冲突。

    如果用线性探测再散列处理冲突,下一个哈希地址为H1=(3 + 1)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 + 2)% 11 = 5,还是冲突,继续找下一个哈希地址为H3=(3 + 3)% 11 = 6,此时不再冲突,将69填入5号单元。

    如果用二次探测再散列处理冲突,下一个哈希地址为H1=(3 + 12)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 - 12)% 11 = 2,此时不再冲突,将69填入2号单元。

    如果用伪随机探测再散列处理冲突,且伪随机数序列为:2,5,9,……..,则下一个哈希地址为H1=(3 + 2)% 11 = 5,仍然冲突,再找下一个哈希地址为H2=(3 + 5)% 11 = 8,此时不再冲突,将69填入8号单元。

    方法二:再哈希法

    这种方法是同时构造多个不同的哈希函数:

    Hi=RH1(key)  i=1,2,…,k

    当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

    方法三:链地址法

    这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

    方法四:建立公共溢出区

    这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。

    更多相关内容
  • 按这个思路,采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或者哈希表。那么关键字对应的记录存储位置我们称为散列地址。 散列技术最适合的求解问题是查找与给定值相等的记录。对于...
  • 一.哈希概念
    一.哈希概念
    • 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( logN),搜索的效率取决于搜索过程中元素的比较次数。
    1. 理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。
    2. 当向该结构中:
      插入元素
      根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放。
      搜索元素
      对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。
    • 哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表)
    • 常见的哈希函数:
    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. 闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的**“下一个” 空位置**中去。那如何寻找下一个空位置呢?
      (1)线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
    • 插入
      ①通过哈希函数获取待插入元素在哈希表中的位置
      ②如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素。
    • 删除
      采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。因此线性探测采用标记的伪删除法来删除一个元素。
    • 线性探测优点:实现非常简单。
    • 线性探测缺点:一旦发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”,即:不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要许多次比较,导致搜索效率降低。
      (2)二次探测:线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题。
    • 若当前key与原来key产生相同的哈希地址,则当前key存在该地址后偏移量为(1,2,3…)的二次方地址处
      key1:hash(key)+0
      key2:hash(key)+1^2
      key3:hash(key)+2^2
      二次探测
    开散列:

    1.开散列概念:
    开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
    2.开散列的实现(哈希函数选择除数取余法)
    链地址法解决冲突

    三.链地址法解决冲突

    1.HashTable的定义:
    ①哈希节点管理:

    #define P 7
    
    typedef struct HashNode
    {
    	DataType data;//存储的数据
    	struct HashNode *link;//尾指针
    }HashNode;
    

    ②HashTable管理

    typedef HashNode* HashTable[P];
    

    ③hashTable操作函数:

    int Hash(DataType key)//哈希函数(取余法)
    {
    	return key % P;
    }
    
    void HashInit(HashTable *pht);//初始化哈希
    bool HashInsert(HashTable pht, DataType x);//插入
    bool HashRemove(HashTable pht, DataType key);//删除
    void HashShow(HashTable pht);//打印哈希表
    

    ④功能实现:

    void HashInit(HashTable pht)
    {
    	memset(pht, 0, sizeof(HashNode*)*P);//初始化哈希表,数据为0
    }
    bool HashInsert(HashTable pht, DataType x)
    {
    	int index = Hash(x);
    	HashNode *node = (HashNode*)malloc(sizeof(HashNode));
    	if(node == NULL)
    		return false;
    	node->data = x;
    
    	node->link = pht[index];
    	pht[index] = node;
    
    	return true;
    }
    
    bool HashRemove(HashTable pht, DataType key)
    {
    	int index = Hash(key);
    	HashNode *cur = pht[index];
    	HashNode *pre = NULL;
    
    	while(cur!=NULL && cur->data!=key)
    	{
    		pre = cur;
    		cur = cur->link;
    	}
    	if(cur == NULL)
    		return false;
    
    	if(pre == NULL)
    		pht[index] = cur->link;
    	else
    		pre->link = cur->link;
    	free(cur);
    	return true;
    
    }
    void HashShow(HashTable pht)
    {
    	for(int i=0; i<P; ++i)
    	{
    		HashNode *p = pht[i];
    		printf("%d : ",i);
    		while(p != NULL)
    		{
    			printf("%d-->", p->data);
    			p = p->link;
    		}
    		printf("Nul.\n");
    	}
    }
    
    展开全文
  • 哈希表和哈希冲突

    前言: 数组和链表是我们经常使用的数据结构。

      数组寻址容易,在知道其下标时获取元素的速度是非常快的 O(1),但在不知道下标的情况下,只能对数组进行线性查找,效率很低,在删除与插入时效率很低,要对该对象后面的数据进行重写覆盖O(n)。

      链表插入和删除效率高O(1),但查询效率低O(n)。

    有没有一种寻址简单,插入删除也快速的数据结构?嘿,还真有,那就是哈希表。

     

     首先,我们可以确定一哈希函数f  存储位置=f(关键字),通过这个f,使得每个关键字key对应一个存储位置f(key),将记录存储在一块连续的存储空间之中,这块空间就叫哈希表。打个比方,我们可以建立一个哈希表,通过自己的身份证经过哈希函数转化成地址,在哈希表中找到自己。可能有些聪明蛋可能会问,是否存在着自己定的哈希函数,使得不同的key经过哈希函数的转化在哈希表中具有同样的地址?还真有,这是哈希表中的不可避免的一个缺点———哈希冲突,即key1!=key2,但有f(key1)=f(key2).稍后我会简述一下解决方法。

    一.哈希表的查询步骤

     1.在存储时通过同一个哈希函数计算散列地址,再进行存储。

    2.在查找记录时,也通过同一个哈希函数计算地址,进行查找。

    一言以蔽之,就是,怎么存的,就去哪找。

     二.哈希函数的构造方法

    要建立一个好的哈希表,核心的是建立一个好的哈希函数,可以从以下几点来考虑:

    1.计算简单.

    由于我们每次存储数据和查询数据都需要通过哈希函数来计算地址,如果一个算法需要复杂的时间,那效率肯定会大大降低。如果哈希函数的计算时间比其他查找技术与关键词比较的时间还长,用哈希表也就没有意义了。

    2.散列地址分布均匀。让散列地址均匀的分布可以保证存储空间的充分应用,减少哈希冲突的发生。

    1.直接定址法

    地址                          成绩                              人数

    100                           100                               121

    99                                99                                 1

    。。。                       。。。

    类似上图统计成绩的人数,可以直接用成绩作为地址 ,f(key)=key;

     其他的类似的取关键词的线性函数值作为散列地址,都是直接定址法的例子

    f(key)=a*key+b

    优点:简单,均匀,不会产生冲突。

    限制:需要知道关键字的分布情况。

    适用:表较小且连续。

    2.数字分析法

    比如这是我们的学号:

    04211001

    04211002

    03211123

    前4位表示入学年分,后三位表示学号

     如果登记时把学号作为关键字,那么前4位有很大概率是一样的,那么把后三位学号作为散列地址是不错的选择。如果这样还发生冲突,可以对其进行翻转(321),右环位移(321),左环位移,位数叠加(6)。

    总的就是从关键词里抽取一部分来计算散列地址。l

    适用:关键字位数较多,事先知道关键字的分布且关键字的若干位分布较为均匀。

    3.平方取中法

    对关键字先平方,再取中间几位。

    比如 1234 平方是1522756 取中277

    4321 平方18671041 取中可以是710也可以是671

    适用:不知道关键词分布,位数不是很多

    4.折叠法

    将关键词从左往右分割成位数相等的几部分,再叠加求和,根据散列表表长,取后几位作为散列地址。

    比如9876543210,散列表长3,变成987|654|321|0,叠加求和1962,取后三位962

    适用:不需要知道关键词的分布,适合关键词较多。

    5.除留余数法

    f(key)=key mod p (p<=m)

     在长度为6的散列表中,比如29mod6=5,下标为5

    但如果11mod6=5,就哈希冲突了。

    所以p的选取至关重要。

    若散列表的表长为m,通常p为小于或等于表长的最小质数或不包含小于20质因子的合数。

    6.随机数法

     选一个随机数,关键字的随机函数值为它的散列地址。f(key)=random(key).

    适用:关键词长度不等。

    综上,这么多的哈希函数,选择因素有那些?

    1.计算散列地址的时间

    2.散列表大小

    3。关键字分布情况

    4关键字长度

    5记录查找的频率

    三.处理哈希冲突的方法

    1.开放定址法

     一旦发生冲突,就取寻找下个空的散列地址,只要散列表足够大,空的散列地址总能找到。

    f(key)=(f(key)+di)mod m di=1,2,3,4...m-1

    这种解决冲突的开放定址法称为线性探索法,但是这种方法很容易使得,两个本来就不是同一个地址的关键词却需要争夺一个相同的地址,这种现象叫做堆积,我们就需要一直解决冲突,效率会大大降低,或者在该关键词地址的后面已经没有空位但在之前有位置,效率也很低。

    所以,改进的方法来了,二次探测法:

     f(key)=(f(key)+di)mod m (di=1*1,-1*1,2*2,-2*2.....q<=m/2),

    通过增加平方运算,不让关键词都聚集在同一区域。

    2.再散列函数法

    我们提前准备多几个散列函数,如果冲突了,就换一个函数,虽然能够是的关键词不聚集,但是也增加了运算时间。

    3.链地址法

    顾名思义,如果有冲突,不用换地方,直接将所有关键词为同义字的记录存储在一个单链表中,散列表中存头指针即可。比如mod4,这样的话,其实就是四个链表了0,1,2,3,其他多的数字都是给上述链表增加节点而已。

    链地址法提供了绝对不会找不到地址的保障,但是增加了遍历单链表的性能消耗。

    4.公共溢出法

    其实就是把冲突的数据单开一个溢出链表存储,在存储的适合,先通过哈希函数计算地址后,在原哈希表中查找,找到就OK,没查到就去溢出表进行顺序查找。如果有冲突的数据很少的情况下,公共溢出区的查找性能还是很高的。

    四。哈希表查找的实现代码()

    #include <iostream>
    #define SUCCESS 1
    #define UNSUCCESS 0
    #define HASHSIZE 12 //散列表长度
    #define NULLKEY -32768
    
    typedef class
    {
    public:
        int *elem;
        int count;
    } HashTable;
    int m = 0; //散列表长度
    
    void InitHashTable(HashTable *H) //初始化
    {
        int i;
        m = HASHSIZE;
        H->elem = (int *)malloc(sizeof(int) * m);
        H->count = 0;
        for (int i = 0; i < m; i++)
        {
            H->elem[i] = NULLKEY;
        }
    }
    
    int Hash(int key) //哈希函数
    {
        return key % m; //除留取余法
    }
    
    void InsertHash(HashTable *H, int key) //插入关键词
    {
        int count = 0, x = 0;
        int addr = Hash(key);
        while (H->elem[addr] != NULLKEY) //哈希冲突
        {
            count++;
            // addr=(addr+1)%m; //开放定址的线性检测
    
            {
                if (count % 2 == 0)
                {
                    if ((addr - x * x) % m > 0)
                        addr = (addr - x * x) % m;
                }
                else
                {
                    x++;
                    addr = (addr + x * x) % m;
                }
            } //二次探测法
        }
        H->elem[addr] = key;
    }
    
    int 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 UNSUCCESS;
            }
        }
        return SUCCESS;
    }
    
    int main()
    {
        int i, result;
        int addr;
        HashTable hashTable;
        int arr[HASHSIZE] = {1, 2, 12, 24, 13, 15};
        //初始化哈希表
        InitHashTable(&hashTable);
    
        //利用插入函数构造哈希表
        for (i = 0; i < HASHSIZE; i++)
        {
            InsertHash(&hashTable, arr[i]);
        }
        //调用查找算法
        result = SearchHash(hashTable, 13, &addr);
        if (result == 0)
            printf("查找失败");
        else
            printf("13在哈希表中的位置是:%d\n", addr);
        for (int i = 0; i < m; i++)
            std::cout << hashTable.elem[i] << " ";
        free(hashTable.elem);
        return 0;
    }
    

    性能分析:

     在没有冲突的情况下,散列表的查找时间复杂度为O(1),可惜冲突不可避免。散列查找的平均长度取决于以下几点。

     1.散列函数是否均匀。散列函数的好坏直接影响着冲突的频繁程度。

     

     2.怎么处理冲突的方法。线性探索会产生堆积,没有二次探索好,而链地址不会产生任何堆积,因此有更佳的性能。

     3.装填因子 x=填入表中的个数/散列表长度,因子越大,产生冲突的可能性越大。所以我们通常将散列表的空间设置得比集合大,效率会提高很多。说白了,就是拿空间换时间。

    展开全文
  • 散列表与散列冲突

    2021-01-08 02:22:16
    HashTable,音译为哈希表,是根据关键字(key)而直接进行访问的数据结构。关键字k,值存放在f(k)的存储位置上,则f为散列函数。关键字(key)通过散列函数直映射到表中一个位置,以加快查找速度。 散列冲突,因为...
  • 取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B 优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景:适合查找比较小且连续的情况 如下这题: 该题直接采用直接定址法,已知该题只包含...

                      🍎作者:努力学习的少年

     🍎个人简介:双非大二,一个正在自学c++和linux操作系统,写博客是总结知识,方便复习。

     🍎目标:进大厂

     🍎 如果你觉得文章可以的话,麻烦你给我点个赞和关注,感谢你的关注!

                  种一颗树最好是10年前,其次是现在。

    目录

    哈希概念

    哈希函数

    直接定址法

    除留余数法

    哈希冲突

    闭散列----------开发定址法

    闭散列的实现

    开散列--------哈希桶

    开散列的增容

    开散列的实现


    哈希概念

    用某个函数直接将元素映射到一个顺序结构中,查找的时候通过映射关系直接找到该值。这个映射函数叫做哈希函数

    哈希函数

    设计哈希函数常用有两种方法:直接定址法除留余数法

    直接定址法

    取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B

    优点:简单、均匀

    缺点:需要事先知道关键字的分布情况 使用场景:适合查找范围集中且已知范围

    如下这题就直接使用直接定址法:

    该题直接采用直接定址法,已知该题只包含小写字母,所以直接创建一个大小为26的数组直接映射小写字母即可,然后遍历字符串,统计字符串中的小写字母出现的次数,然后再遍历一遍字符串,通过字符哈希映射关系,直接找到第一个只出现一次的字符。

    class Solution {
    public:
        char firstUniqChar(string s) {
            int arr[26]={0};
            for(auto c:s)//遍历一遍字符串,统计s中字符的个数
            {
                arr[c-'a']++;
            }
    
            for(auto c:s)//再遍历一遍字符串,找出第一个只出现一次的字符
            {
                if(arr[c-'a']==1)
                return c;
            }
            return ' ';
        }
    };

    时间复杂度:O(N)

    空间复杂度:因为我们只定义出一个arr[26]的数组,所以空间复杂度为O(1), 

     该题是直接将0~25映射出a~z这26个字母,这种方式叫做直接定址法。

    该方式的优点是:效率高,通过某个数字直接映射出某个字符。

    缺点:只适用于整数,字符且范围较小的映射,浮点数或者范围很广的映射不适用。

    除留余数法

    假设需要映射一些范围很广的元素,可以将这个范围很广的数组缩小到一个哈希数组里进行映射,也就是说映射该数的位置=该数%哈希表数组的大小,这就是除留余数法。

    例如我们的哈希数组的大小是10,所以我们可以将映射的每个元素进行%10,那么哈希数组中的范围映射位置是0~9,如下,将下列的数组映射到哈希表中。

    哈希冲突

    简单来说,哈希冲突就是不同的值映射到相同的位置

    上面的除留余数法就会发生哈希冲突,例如:

    100和10放在大小为10的哈希数组中,那么它们都%10之后都是0,这就是哈希冲突。

    解决哈希冲突常用有两种方法,闭散列开散列

    闭散列----------开发定址法

    如果哈希表未满,然后未被装满,说明哈希表必然存在空位置,那么可以把key值放在冲突的下一个空位置。例如:

     查找空位置的方式有线性探测和二次探测:

    线性探测从冲突位置上往后一个一个查找空位置

    例如:上面的10映射到哈希表中,它经过1,12,3最终在4的位置找到空位置,往后一个一个查找就是线性探测,线性探测一旦发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”,即:不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要许多次比较,导致搜索效率降低。,例如:当我们要查找10这个数据的时候,我们需要踏过1,12,3这三个数据,查找效率较低。

    二次探测从冲突位置上往后以n^2进行查找空位置。n={1,2,3,4...}

    查找值的时候,也是按二次探测开始查找,走到空时,说明查找不到。

    如下:

     二次探测相对分散一些,不容易发生踩踏事件。

    思考:

    哈希什么时候下进行增容?如何增容?

    散列表中载荷因子的定义: a=哈希表填入的元素个数/哈希表的容量

    a越大,填入表中的元素个数越多,冲突可能性越大,查找效率较低,反之,a越小,冲突的可能性越小,查找效率较高,为了保证查找效率,载荷因子到一定的数之后,哈希表就要增容,正常情况下,载荷因子控制在0~0.8,超过0.8,则查找效率会很低。

    闭散列的实现

     1.闭散列需要定义定义一个枚举数组来判断哈希表上位置的状态。

        enum State//标识哈希表中位置的状态
        {
            EMPTY,//空
            EXITS,//存在
            DLETE//删除
        };

    2.定义一个哈希表存储的数据结构体,一个是存储的数据,一个是存储的状态,状态默认为空。

    	template<class K,class V>
    	class HashData//哈希位置的数据
    	{
    	public:
    		pair<K, V> _kv;//哈希表上映射的数据
    		State _state = EMPTY;//位置上的状态
    	};

    3.哈希表的定义

    namespace sjp
    {
    	enum State//标识哈希表中位置的状态
    	{
    		EMPTY,//空
    		EXITS,//存在
    		DLETE//删除
    	};
    
    	template<class T>
    	struct HashFunc//哈希仿函数,用来转化为整数,才能进行除留余数
    	{
    		size_t operator()(const T& k)
    		{
    			return k;
    		}
    	};
    
    	
    	template<>//string仿函数的模板特化
    	struct HashFunc<string>
    	{
    		//将字符变成对应的整形值
    		//BKDRHAXI 每次加上一个数,在乘上131
    		//近似唯一
    		size_t  operator()(const string& st)
    		{
    			size_t ret = 0;
    			for (auto e : st)
    			{
    				ret += e;
    				ret *= 131;
    			}
    			return ret;
    		}
    	};
    
    
    	template<class K,class V>
    	class HashData//哈希位置的数据
    	{
    	public:
    		pair<K, V> _kv;//哈希表上映射的数据
    		State _state = EMPTY;//位置上的状态
    	};
    
    	template<class K, class V, class HashFunc= HashFunc<K>>//仿函数
    	class HashTable
    	{
    	public:
    		bool Insert(const pair<K, V>& kv)
    		{
    			if (find(kv.first) != NULL)//如果kv值在_table,则插入失败
    				return false;
    			if (_table.capacity() == 0)
    			{
    				_table.resize(10);
    			}
    
    			else if ((double)_n /(double) _table.size()>=0.7)//计算负载因子
    			{
    				//大于负载因子,哈希表进行增容
    				HashTable<K, V, HashFunc> newHT;//创建新的哈希表并未原来的两倍
    				newHT._table.resize(_table.size() * 2);
    				for (auto& e : _table)//将旧表中数据一个一个的映射到新表中
    				{
    					if (e._state == EXITS)
    					{
    						newHT.Insert(e._kv);//在运行insert,相当于复用了insert
    					}
    				}
    				_table.swap(newHT._table);//最后将newHT.table和本身的table交换即可
    			}
    			//位置得模上size()
    			HashFunc hf;
    			size_t index = hf(kv.first)%_table.size();
    			size_t i = 1;
    			int start = index;
    			//探测后面的位置 —— 线性探测 or 二次探测
    			while (_table[index]._state == EXITS)//发生冲突,探测下一个位置
    			{
    				i += 1;
    				index =start+i*1;//进行二次探测
    				index %= _table.size();
    			}
    			_table[index]._kv = kv;
    			_table[index]._state = EXITS;
    			++_n;
    			return true;
    		}
    
    		HashData<K, V>* find(const K& k)//查找函数
    		{
    			HashFunc fc;//仿函数
    			if (_table.size()== 0)//防止除0
    				return nullptr;
    			int index = fc(k) % _table.size();
    			int i = 1;
    			while (_table[index]._state !=EMPTY )//如果找到的位置不为空,则继续往下找
    			{
    				//找到了需要判断该值是否存在,有可能被删除掉
    				if (_table[index]._state == EXITS&&_table[index]._kv.first == k)
    				{
    					return &_table[index];
    
    				}
    				else 
    				{
    					index += i;
    					index %= _table.size();
    				}
    			}
    			return NULL;
    		}
    
    		bool erase(const K& k)//删除数据
    		{
    			HashData<K, V>* kv = find(k);//查找key值
    			if (kv == NULL)//找不到,则删除失败
    			{
    				return false;
    			}
    			else if (kv != NULL)//找到了
    			{
    				kv->_state = DLETE; //直接将该位置的状态设置为DLETE,假删除
    				return true;
    			}
    		}
    	private:
    		vector<HashData<K,V>> _table;
    		size_t _n=0;//存储有效数据的个数
    	};
    }

    为了让各个类型都能映射到哈希表中,需要创建一个仿函数的类模板,该仿函数可以将char和int等直接转换为整数。

    	template<class K> 
    	struct Hash//将数据转换为整数的仿函数
    	{
    		size_t operator()(const K& k)
    		{
    			return k;
    		}
    	};

    为了让string类型也能映射到哈希表里面,所以我们需要将string转化为整数,这样才能%某个数找到相应的位置,所以我们需要对上面的仿函数进行模板的特化,。如下:

    	template<>//模板的特化,将string的转换为整数
    	struct Hash<string>
    	{
    		size_t operator()(const string& s)
    		{
    			int ret = 0;
    			for (auto c : s)
    			{
    				ret += c;
    			}
    			return ret;
    		}
    	};

    当然,这样将string中的字符相加起来后,不同的string会发生冲突,例如:

    “abbc"和”acbb"或者“abcd"和”aadd"它们的转化成整数是冲突的。

    所以可以相加每个字符后*131,这样使我们string转化成整数的冲突概率变得极低。

    	template<>//模板的特化,将string的转换为整数
    	struct Hash<string>
    	{
    		size_t operator()(const string& s)
    		{
    			int ret = 0;
    			for (auto c : s)
    			{	
    				ret += c;
    				ret *= 131;
    			}
    			return ret;
    		}
    	};

     然后将仿函数传入到模板列表中,这样我们哈希表默认可以会对string,char等进行整形转化

    template<class K, class V,class Hash=Hash<K>>

    如果有其它类型需要转化成仿函数,我们也可以自定义一个仿函数将它传进我们类模板中。 

    开散列--------哈希桶

    概念:

    开散列概念开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。

    如下:将下面的数组 

    我们将映射相同位置的值用一个单链表连接起来,各链表的头节点存储在哈希表中,将每条链表称为一个桶。其中链表的插入删除是进行头插,因为头插的效率是O(1).

    开散列的增容

    桶的个数是一定的,随着数据的不断的插入,冲突的概率越来越高,每个桶的元素不断增加,那么映射效率越低,当每个桶的元素是只有一个元素时,映射效率时最高的,当元素个数等于桶的个数时,可以给哈希表继续增容。

    开散列的实现

    	template<class K, class V,class Hash=Hash<K>>
    	class HashTable
    	{
    		typedef HashData<K, V> node;
    	public:
    		bool insert(const pair<K, V>& kv)//插入
    		{
    			if (find(kv.first) != nullptr)//哈希表中的k值不允许重复
    				return false;
    			if (_table.capacity() == 0)//如果容量为0,则哈希表初始化10个空间
    			{
    				_table.resize(10,0);
    			}
    			else if (_n / _table.size() >= 1)//哈希表中的元素大于
    			{
    				HashTable<K,V> newtable;//创建一个新的哈希表
    				newtable._table.resize(_table.size() * 2);//newtable的大小为_table的两倍
    				for (auto& c : _table)//将_table中的元素映射到newtable中
    				{
    					node* cur = c;//c是每个链表的头节点
    					while (cur)
    					{
    						newtable.insert(cur->_kv);
    						cur=cur->_next;
    					}
    				}
    				_table.swap(newtable._table);//交换两个表格,完成增容
    			}
    			node* newnode = new node(kv);//创建新的节点
    			Hash hs;
    			int index = hs(kv.first) % _table.size();//找到映射的位置
    			node* cur = _table[index];//新的节点进行头插
    			newnode->_next = cur;
    			_table[index] = newnode;
    			_n++;//有效数据加1
    			return true;
    		}
    
    		node* find(const K& k)//查找
    		{
    			if (_table.size() == 0)//如果哈希表的空间为0,则直接返回
    				return nullptr;
    			Hash hs;
    			int index = hs(k) % _table.size();//找到该值在哈希表对应的映射位置
    			//在该位置上的链表进行查找
    			node* cur = _table[index];
    			while (cur)
    			{
    				if (cur->_kv.first == k)//找到了
    					return cur;
    				else
    				{
    					cur = cur->_next;
    				}
    			}
    			return nullptr;//找不到
    		}
    
    		bool erase(const K& k)//删除
    		{
    			if (_table.size() == 0)
    				return false;
    			Hash hs;
    			int index = hs(k) % _table.size();//找到该值在哈希表对应的映射位置
    			node* pre = nullptr;//cur前面的一个节点
    			node* cur = _table[index];
    			while (cur)
    			{
    				if (cur->_kv.first == k)//找到了
    				{
    					if (pre == nullptr)//头节点删除
    					{
    						_table[index] = cur->_next;
    					}
    					else//中间节点删除
    					{
    						pre->_next = cur->_next;
    					}
    					delete cur;
    					cur = nullptr;
    					_n--;
    					return true;
    				}
    				else
    				{
    					pre = cur;
    					cur = cur->_next;
    				}
    			}
    			return false;//找不到,删除失败
    		}
    
    	private:
    		vector<node*> _table;//哈希表
    		size_t _n;//计算哈希表中有多少个有效元素
    	};
    }
    

    思考:在极端情况下,如果所有的数都映射在一个桶,且没有到达有效数据个数小于哈希表的大小,此时的查找的效率是O(N),请问有什么解决方法可以提高查找效率。

    由于哈希表中的有效元素未达到哈希表的容量,所以就没办法增容,为了防止链表的太长,我们可以将限制链表的长度,如果链表大于该长度,我们把该链表转化为红黑树,例如我们可以 设置链表的最大长度为8,如果大于该长度,在将该链表转换为红黑树

            

    若文章出现错误,随时欢迎你帮我指正,若文章对你有所帮助,麻烦你给我点个关注!!!

                                              

            

    展开全文
  • 哈希表,散列表,哈希冲突的产生及解决方式 开散列:线性探测,二次探测 哈希的负载因子 闭散列 哈希桶的实现
  • 1)设计几个不同的哈希函数,比较他们的地址冲突率(可以用更大的名字集合做实验)。...(3)在哈希函数确定的前提下尝试各种不同处理冲突的方法,考察平均查找长度的变化和造好的哈希表中关键字的聚集性。
  • 散列表(哈希表):按散列存储方式构造的存储结构为散列表。 散列函数(哈希函数):H(ki),关键字与表之间的对应关系。 散列地址(哈希地址):散列函数的值。 散列:将结点按关键字的散列地址存储到散列表中的...
  •  (2)从键盘读入待查找的权重数值,以除留余数法为哈希函数,二次探测再散列法解决冲突建立哈希表,基于哈希算法从数组中查找相应的记录,计算相应的查找时间,并在屏幕上输出显示。(提示:当前计算机时间 函数 C\...
  • 一,哈希表的定义 二,哈希表的常用函数 三,哈希表的适用题目 四,哈希冲突 五,哈希冲突的解决方法 一,哈希表的定义 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据...
  • 哈希表解决冲突的两种方式

    千次阅读 2019-02-17 01:12:23
    另外,当关键字的实际取值大于哈希表的长度时,而且表中已装满了记录,如果插入一个新记录,不仅发生冲突,而且还会发生溢出。因此,处理冲突和溢出是 哈希技术中的两个重要问题。1、开放定址法 用开放定址法解决...
  • 散列表(HashTable,也叫哈希表):由数组扩展而来,是根据键(Key)直接访问在内存存储位置的数据结构。 实现原理是:通过散列函数(也叫哈希函数)将元素的键(key)映射为数组下标(转化后的值叫做散列值或哈希...
  • 哈希表是一种存储记录的连续内存通过哈希函数的应用,通过哈希函数的应用,可以快速存取与查找数据。所谓哈希法(Hashing),就是将本身的键(Key)通过特定的数学函数运算或使用其他的方转化成对应的数据存储地址。...
  • 哈希表(散列表)的构造方法和哈希冲突一、散列函数的构造方法1、直接定址法2、数字分析法3、平方取中法4、折叠法5、除留余数法6、随机数法二、解决哈希冲突的方法1、开放定址法2、再散列函数法3、链地址法4、公共...
  • 哈希表(重要)

    千次阅读 2022-01-24 10:28:54
    目录概念哈希冲突概念哈希冲突的避免(两种方式)第一种方式:设计精妙的哈希函数哈希函数的设计哈希函数设计原则常见的哈希函数第二种方式:负载因子调节(重点掌握)哈希冲突的解决(两种方式)闭散列方法1:线性...
  • 首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。 2.开散列的实现 存...
  • 哈希表的消除哈希冲突——双散列

    千次阅读 2019-09-02 15:20:20
    当插入49时,与已经插入的89产生哈希冲突,则采用双散列函数来处理这样的哈希冲突,这里双散列函数采用的是。这里采用的是hash2(x)=7-(x mod 7)。带入49计算得到hash2(49)=7-0=7。则从第9个位置开始数7次,到了第6个...
  • 目录一、冲突问题二、处理冲突的方法三、算法思想四、算法线性探测再散列1、首先计算 = hash(K);2、如果单元 为空,则所查元素不存在;3、 如果单元 中元素的关键字为K,则找到所查元素;4、否则重复线性探测再散列...
  • 哈希表(散列表)原理详解

    万次阅读 多人点赞 2018-07-03 19:40:58
    什么是哈希表哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数...
  • 0 1散列表 1简单来说就是给一个key,...1.1散列冲突 我们时常会碰到两个关键字key1 ≠ key2,但是却有f (key1) = f (key2),这种现象我们称为冲突(collision), 打个比方说:加上f的函数是这样的f(key)=key%10...
  • 哈希散列

    2019-03-18 09:45:28
    什么是哈希表哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数...
  • 哈希概念 常规搜索:   数据杂乱无章——-&amp;amp;gt;顺序查找—–&amp;amp;gt;时间复杂度0(n)。   数据有序—–&amp;amp;gt;二分查找——&amp;amp;gt;时间复杂度0(log(n))。   建立二叉...
  • P61 5.1 哈希表概述 1、哈希表概念 P62 5.2 散列函数的设计 P63 5.3 散列冲突的解决方案 1、开放地址法 1.1、线性探测法 1.2、二次探测法 1.3、再哈希法 2、链地址法
  • 哈希表冲突处理

    2020-04-21 00:09:50
    ①插入操作:在发生哈希冲突的时候,我们输入域的关键字去映射到位桶(实际上是实现位桶的这个数据结构,链表或者红黑树)中去的时候,我们先检查带插入元素x是否出现在中,很明显,这个查找所用的次数不会超过...
  • 近来上班划水划得起飞,又...散列冲突哈希冲突):两个关键字散列到同一个值。 哈希代码: 第一种(适用整数): typedef unsigned int Index; Index Hash(const char *key, int tableSize) { unsigned in..
  • 前面提到,如果说散列函数是完美的,那就不会有散列冲突,但完美散列函数常常是不现实的。 如果两个数据项被散列映射到同一个槽,那么就产生了“冲突”。而使用一个系统化的方法在散列表中保存第二个数据项,这个...
  • 哈希表及处理冲突的方法
  • 一、构造哈希表的几种方法 1.1 直接定址法 f(key) = a × key + b 1.2 除留余数法 f( key ) = key mod p ( p ≤ m ) mod是取模(求余数)的意思。事实上,这方法不仅可以对关键字直接取模,也可在折叠、平方取中后再...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 36,328
精华内容 14,531
关键字:

哈希表散列冲突