精华内容
下载资源
问答
  • 拉链法处理冲突
    万次阅读 多人点赞
    2018-06-12 10:16:57

    上篇博客我们说到了,什么是哈希冲突,其实就是再采用哈希函数对输入域进行映射到哈希表的时候,因为哈希表的位桶的数目远小于输入域的关键字的个数,所以,对于输入域的关键字来说,很可能会产生这样一种情况,也就是,一个关键字会映射到同一个位桶中的情况,这种情况就就叫做哈希冲突,解决哈希冲突的有三种方案,一种叫做拉链法(也叫作链接法、链地址法,一个意思),另外三种分别为开发地址法和再散列法。

    一、拉链法

    上篇博文我们举的例子,HashMap,HashSet其实都是采用的拉链法来解决哈希冲突的,就是在每个位桶实现的时候,我们采用链表(jdk1.8之后采用链表+红黑树)的数据结构来去存取发生哈希冲突的输入域的关键字(也就是被哈希函数映射到同一个位桶上的关键字)。首先来看使用拉链法解决哈希冲突的几个操作:

    ①插入操作:在发生哈希冲突的时候,我们输入域的关键字去映射到位桶(实际上是实现位桶的这个数据结构,链表或者红黑树)中去的时候,我们先检查带插入元素x是否出现在表中,很明显,这个查找所用的次数不会超过装载因子(n/m:n为输入域的关键字个数,m为位桶的数目),它是个常数,所以插入操作的最坏时间复杂度为O(1)的。

    ②查询操作:和①一样,在发生哈希冲突的时候,我们去检索的时间复杂度不会超过装载因子,也就是检索数据的时间复杂度也是O(1)的

    ③删除操作:如果在拉链法中我们想要使用链表这种数据结构来实现位桶,那么这个链表一定是双向链表,因为在删除一个元素x的时候,需要更改x的前驱元素的next指针的属性,把x从链表中删除。这个操作的时间复杂度也是O(1)的。

     

    拉链法的优点

    与开放定址法相比,拉链法有如下几个优点:

    ①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

    ②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

    ③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

    ④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

     

    拉链法的缺点

    指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

    使用例子:

    HashMap

    二、开发地址法

    开放地址法有个非常关键的特征,就是所有输入的元素全部存放在哈希表里,也就是说,位桶的实现是不需要任何的链表来实现的,换句话说,也就是这个哈希表的装载因子不会超过1。它的实现是在插入一个元素的时候,先通过哈希函数进行判断,若是发生哈希冲突,就以当前地址为基准,根据再寻址的方法(探查序列),去寻找下一个地址,若发生冲突再去寻找,直至找到一个为空的地址为止。所以这种方法又称为再散列法。

    有几种常用的探查序列的方法:

    ①线性探查

    dii=1,2,3,…,m-1;这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

    (使用例子:ThreadLocal里面的ThreadLocalMap)

    ②二次探查

    di=12,-12,22,-22,…,k2,-k2    ( k<=m/2 );这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。

    ③ 伪随机探测

    di=伪随机数序列;具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),生成一个位随机序列,并给定一个随机数做起点,每次去加上这个伪随机数++就可以了。

    三、再哈希法

    再哈希法其实很简单,就是再使用哈希函数去散列一个输入的时候,输出是同一个位置就再次哈希,直至不发生冲突位置

    缺点:每次冲突都要重新哈希,计算时间增加。

    更多相关内容
  • 散列表线性探测法外拉链法 #include &amp;amp;lt;iostream&amp;amp;gt; #include &amp;amp;lt;algorithm&amp;amp;gt; using namespace std; struct Node { int key; Node *next; }; Node ...

    散列表线性探测法外拉链法
    这里写图片描述

    #include <iostream>
    #include <algorithm>
    using namespace std;
    struct Node
    {
        int key;
        Node *next;
    };
    Node HashTable[13];
    int a[13];
    int InsertHT(int x,int w)
    {
        int adr;
        Node *p;
        adr=x%w;
        p=&HashTable[adr];
        while(p->next)
        {
            if(p->next->key==x)
            return -1;
            p=p->next;
        }
        Node *s;
        s=new Node;
        s->key=x;
        s->next=p->next;
        p->next=s;
        return 1;
    }
    void CreateHT(int n,int m,int p)
    {
        for(int i=0;i<n;i++)
        {
            HashTable[i].key=i;
            HashTable[i].next=NULL;
        }
        for(int i=0;i<m;i++)
            InsertHT(a[i],p);
    }
    void Display(int n,int m)
    {
       int add[13],j,count;
       Node *q;
       for(int i=0;i<13;i++)
       {
           j=0;count=0;
           q=(&HashTable[i])->next;
           while(q!=NULL)
           {
               add[j]=q->key;
               j++;
               count++;
               q=q->next;
           }
           sort(add,add+count);
           q=(&HashTable[i])->next;
           j=0;
           while(q!=NULL)
           {
               q->key=add[j];
               j++;
               q=q->next;
           }
       }
       cout<<"  "<<0<<endl;
       for(int i=1;i<13;i++)
       {
           q=&HashTable[i];
           cout<<"  ";
           while(q->next!=NULL)
           {
               cout<<q->key<<" ";
               q=q->next;
           }
           cout<<q->key<<endl;
       }
    }
    int main()
    {
        for(int i=0;i<13;i++)
        cin>>a[i];
        CreateHT(13,13,13);
        Display(13,13);
        return 0;
    }
    
    
    
    
    展开全文
  • 自己手撸了一下拉链法解决散列冲突的算法,代码如下: #include <iostream> #include <vector> #define N 1000 using namespace std; typedef struct ChainNodes { int data; ChainNodes* Next; }...

    自己手撸了一下拉链法解决散列冲突的算法,代码如下:

    
    #include <iostream>
    #include <vector>
    #define N 1000
    using namespace std;
    typedef struct ChainNodes {
        int data;
        ChainNodes* Next;
    }ChainNodes;
    void CreatHashTable(vector<ChainNodes*>& try01) {
        //ChainNodes** try01 = new ChainNodes * [10];//try应该是关键字
        for (int i = 0; i < try01.size(); i++) {
            try01[i] = NULL;
        }
        cout << "请输入您要储存的数字" << endl;
        int item, i = 0;
        char t;
        while (cin >> item) {
            //“=”在C语言中优先级中最低;
            i = item % 7;
            if (try01[i] == NULL) {
                try01[i] = new ChainNodes;
                try01[i]->data = item;
                try01[i]->Next = NULL;
            }
            else {
                ChainNodes* pre = try01[i];
                ChainNodes* cur = try01[i]->Next;
                while (cur != NULL) {
                    pre = cur;//“=”在C语言中优先级中最低;
                    cur = cur->Next;
                }
                pre->Next = new ChainNodes;/*这段代码的目的是进行链表的尾插法;但是当try指向空节点时,没有一个临时指针保存try01的前继节点,导致try01
                                          指向一片和链表中断的空间,之后再把temp赋给try01,则原先try01【i】所指的空间失去连接,导致内存泄漏*/
                pre->Next->data = item;
                pre->Next->Next = NULL;
                
            };
            if ((t = cin.get()) == '\n')      break;
        }
    
    };
    
    void QueryNum(vector<ChainNodes*>& try01) {
        cout << "请输入您要查询的数" << endl;
        int tem;
        cin >> tem;
        if (try01[tem % 7] == NULL) {
            cout << "您要查询的数不存在" << endl;
        }
        else {
            ChainNodes* temp = try01[tem % 7];
            int count = 0;
            while (temp != NULL) {
                count++;//
                if (temp->data == tem) {
                    cout << "您找的数位于散列表第" << tem % 7 << "个表的第" << count << "个链表中" << endl;
                    break;
                }
                temp = temp->Next;
            }
            if (temp == NULL) {
                cout << "您要查询的数不存在" << endl;
    
            }
        }
    }
    
    void DeleteHashTable(vector<ChainNodes*>& try01) {
        for (int i = 0; i < try01.size(); i++) {
            if (try01[i] == NULL) {
                cout << "第"<<i<<"位链表为空,无需释放。" << endl;
            }
            else {
                ChainNodes* temp = try01[i];
                int count = 0;
                while (temp != NULL) {
                    ChainNodes* t = temp;
                    cout << t->data << endl;
                    temp = temp->Next;
                    delete t;
                }
                if (temp == NULL) {
                    try01[i] = NULL;
                    cout << "第"<<i<<"位链表已经释放完毕" << endl;
    
                }
            }
    
        }
    
    }
    
    int main()
    {
        vector<ChainNodes*> try01(10);
        CreatHashTable(try01);
       QueryNum(try01);
       DeleteHashTable(try01);
        return 0;
    }
    

     欢迎大家交流讨论;

    展开全文
  • 哈希表(拉链法解决冲突

    千次阅读 2020-06-10 22:57:22
    Java 标准库的 HashMap 基本上就是用 拉链法 实现的。 拉链法 的实现比较简单,将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。 实现...

    哈希冲突

    若两个不相等的 key 产生了相等的 哈希值 ,这时则需要采用 哈希冲突 。

    拉链法

    Java 标准库的 HashMap 基本上就是用 拉链法 实现的。 拉链法 的实现比较简单,将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。

     

    实现步骤

    *得到一个 key
    *计算 key 的 hashValue
    *根据 hashValue 值定位到 data[hashValue] 。( data[hashValue] 是一条链表)
    *若 data[hashValue] 为空则直接插入
    *不然则添加到链表末尾

    这里需要注意的是, 哈希函数 必须保证 哈希值 的 均匀分布 ,若全部集中在一条链表中,则 时间复杂度 和顺序链表相同。

    还有一点则是数组的大小,若你能估计数据的大小,则直接指定即可,否则就需要 动态扩充 数组。

    //拉链法实现
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node{
        char *name;//字段名
        char *desc;//描述
        struct node *next;
    }node;
    
    #define HASHSIZE 100 //hash表长度
    static node* hashtable[HASHSIZE];//定义一个hash数组,该数组的每个元素是一个hash结点指针,并且由于是全局静态变量,默认初始化为NULL
    
    unsigned int hash(char *s)
    {//哈希函数
        unsigned int h=0;
        for(;*s;s++)
            h=*s+h*31;//将整个字符串按照特定关系转化为一个整数,然后对hash长度取余
        return h%HASHSIZE;
    }
    
    node* lookup(char *str)
    {
        unsigned int hashvalue = hash(str);
        node* np = hashtable[hashvalue];
        for( ; np!=NULL; np = np->next)
        {//这里是链地址法解决的冲突,返回的是第一个链表结点
            if(!strcmp(np->name, str))//strcmp相等的时候才返回0
                return np;
        }
        return NULL;
    }
    
    char* search(char* name)
    {//对hash表查找特定元素(元素是字符串)
        node* np=lookup(name);
        if(np==NULL)
            return NULL;
        else
            return np->desc;
    }
    
    node* malloc_node(char* name, char* desc)
    {//在堆上为结点分配内存,并填充结点
        node *np=(node*)malloc(sizeof(node));
        if(np == NULL)
            return NULL;
        np->name = name;
        np->desc = desc;
        np->next = NULL;
        return np;
    }
    
    int insert(char* name, char* desc)
    {
        unsigned int hashvalue;
        hashvalue = hash(name);
        //头插法,不管该hash位置有没有其他结点,直接插入结点
        node* np = malloc_node(name, desc);
        if (np == NULL) return 0;//分配结点没有成功,则直接返回
        np->next = hashtable[hashvalue];
        hashtable[hashvalue] = np;
        return 1;
    }
    
    /* A pretty useless but good debugging function,
    which simply displays the hashtable in (key.value) pairs
    */
    void displayHashTable()
    {//显示hash表元素(不包括空)
        node *np;
        unsigned int hashvalue;
        for(int i=0; i < HASHSIZE; ++i)
        {
            if(hashtable[i] != NULL)
            {
                np = hashtable[i];
                printf("\nhashvalue: %d (", i);
                for(; np != NULL; np=np->next)
                    printf(" (%s.%s) ", np->name, np->desc);
                printf(")\n");
            }
        }
    }
    
    void cleanUp()
    {//清空hash表
        node *np,*tmp;
        for(int i=0;i < HASHSIZE; ++i)
        {
            if(hashtable[i] != NULL)
            {
                np = hashtable[i];
                while(np != NULL)
                {
                    tmp = np->next;
                    free(np->name);
                    free(np->desc);
                    free(np);
                    np = tmp;
                }
            }
        }
    }
    
    int main()
    {
        char* names[]={"First Name","Last Name","address","phone","k101","k110"};
        char* descs[]={"Kobe","Bryant","USA","26300788","Value1","Value2"};
    
        for(int i=0; i < 6; ++i)
            insert(names[i], descs[i]);
        printf("we should see %s\n",search("k110"));
        insert("phone","9433120451");//这里计算的hash是冲突的,为了测试冲突情况下的插入
         printf("we have %s and %s\n",search("k101"),search("phone"));
        displayHashTable();
        cleanUp();
        return 0;
    }

    本文分享自微信公众号 - 国产程序员(Monday_lida),作者:Monday

    原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

    原始发表时间:2019-02-22

    本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

    展开全文
  • 拉链法 解决冲突,构造哈希表 将所有哈希函数 结果相同的结点 连接在同一个单链表中。 若选定的哈希表 长度 为m,则可将哈希表定义为一个长度为m的 指针数组 t[0-m-1],指针数组中的每个指针指向哈希函数 结果相同...
  • hash表拉链法解决冲突

    万次阅读 多人点赞 2017-03-07 18:34:03
    散列表(Hash table) 也称为 哈希表 。是字典的一种抽象。比如说你要查一个字,通过这个字的拼音首字母,找到...如果两个不同的 key`算出了同一个索引,此时就要用到一定的方法来解决哈希冲突。 哈希函数 哈希函数
  • 开放散列(open hashing)/ 拉链法(针对桶链结构) 封闭散列(closed hashing)/ 开放定址法 通过构造性能良好的哈希函数,可以减少冲突,但一般不可能完全避免冲突,因此解决冲突是哈希法的另一个关键问题。创建...
  • hash表之拉链法处理冲突

    千次阅读 2014-08-16 17:01:07
    /*hash表之拉链法处理冲突:*/ 方法一: #define ARRLEN 17 #define NAMELEN 20 #define ADDRLEN 20 typedef struct _rec {  char name[NAMELEN];  char addr[ADDRLEN];  struct _rec *next; } rec; ...
  • 哈希表处理冲突的方式主要有两种一种是拉链法,另一种是开放寻址法
  • class StorePageMap {  /**  * The table, resized as necessary. Length MUST Always be a power of two.  */  private Entry[] table;  /** ... * The number of key-value mappi
  • 一、什么是hash冲突? 假设hash表的大小为9(即有9个槽),现在要把一串数据存到表里:5,28,19,15,20,33,12,17,10 简单计算一下:hash(5)=5, 所以数据5...1.开放定址(再散列): 基本思想:当关键字key的哈希地址p
  • /* ... * All rights reserved. * 文件名称:项目3.cbp ...相比线性探查,拉链法适用于大数据,它是把所有的同义词用单链表链接起来,利用哈希函数求出每个关键字的地址,同一地址的利用链表存放在一起。
  • //哈希表(拉链法) #include<iostream> #include<cstring> using namespace std; const int N=100003; int h[N],e[N],ne[N],idx; void insert(int x) { //拉链法 int k=(x%N+N)%N; e[idx]=x; ne[idx]...
  • 数据结构——拉链法(链地址法)

    千次阅读 2019-12-10 20:54:16
    当存储结构是链表时,多采用拉链法,用拉链法处理冲突的办法是:把具有相同散列地址的关键字(同义词)值放在同一个单链表中,称为同义词链表。有m个散列地址就有m个链表,同时用指针数组T[0..m-1]存放各个链表的头...
  • 另外还有一篇: (1)拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短; (2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况; (3)开放定址...
  • ​ 也叫再散列,其基本思想是:当关键字 key 的哈希地址 p=H(key)出现冲突时,以 p 为基础,产生另一个哈希地址 p1 ,如果 p1 仍然冲突,再以 p 为基础,产生另一个哈希地址 p2 ,…,直到找出一个不冲突的哈希...
  • 开放地址 这个方法的基本思想是:当发生地址冲突时,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止。这个过程可用下式描述: H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… , k ...
  • 由于哈希表的查找高效性,在平时的算法中用的也是比较多。...(2)计算出来的地址分布均匀,即对任一关键字k,f(k) 对应不同地址的概率相等,目的是尽可能减少冲突。 1、除留余数; 取关键字被某个不大于
  • 哈希冲突解决

    2019-04-16 13:47:03
    什么是哈希冲突? 假设hash表的大小为9(即有9个槽),现在要把一串数据存到表里:5,28,19,15,20,33,12,17,10 简单计算一下:hash(5)=5, 所以数据5应该放在hash表的第5个槽里;hash(28)=1,所以数据28应该放在hash表...
  • 常见的解决Hash冲突的四种方法 开放定址 再哈希法 链地址 建立公共溢出区
  • 实现哈希表创建及查找算法,哈希函数使用除余法,用拉链法处理冲突。 函数接口定义: void CreateHash(HashTable HT[],int n); //输入不大于m的n个不为0(0表示空值)的数,用拉链法解决冲突构造散列表 float ASL...
  • 实现哈希表创建及查找算法,哈希函数使用除余法,用拉链法处理冲突。 函数接口定义: void CreateHash(HashTable HT[],int n); //输入不大于m的n个不为0(0表示空值)的数,用拉链法解决冲突构造散列表 float ASL...
  • 对于给定的一组整数和散列函数,分别采用线性探测法和拉链法处理冲突构造散列表,并在这两种方法构建的散列表中查找整数K,比较两种方法的时间和空间性能。
  • 哈希表及处理冲突的方法

    万次阅读 2017-04-14 15:48:26
     哈希法又称散列、杂凑以及关键字地址计算等,相应的表成为哈希表。  基本思想:首先在元素的关键字K和元素的位置P之间建立一个对应关系f,使得P=f(K),其中f成为哈希函数。  创建哈希表时,把关键字K的元素...
  • #include <iostream> #include<bits/stdc++.h> using namespace std; typedef struct node{ int data; struct node *next; }no; int main() { no n[100]; int key,h; for(int i=0;...h=k
  • 哈希表冲突及处理冲突的方法

    万次阅读 多人点赞 2018-07-06 20:31:30
    哈希法又称散列、杂凑以及关键字地址计算等,相应的表成为哈希表。 基本思想:首先在元素的关键字K和元素的位置P之间建立一个对应关系f,使得P=f(K),其中f成为哈希函数。 创建哈希表时,把关键字K的元素直接...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,383
精华内容 4,153
关键字:

拉链法处理冲突