精华内容
下载资源
问答
  • hash表拉链法解决冲突

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

    https://blog.csdn.net/lcalqf/article/details/60775221

    拉链法

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

    image

    实现步骤

    • 得到一个 key
    • 计算 keyhashValue
    • 根据 hashValue 值定位到 data[hashValue] 。( data[hashValue] 是一条链表)
    • data[hashValue] 为空则直接插入
    • 不然则添加到链表末尾
    展开全文
  • 哈希表用拉链法解决冲突的时候怎么根据K进行查找值?假如k1,k2有冲突,现在查找k2的值?怎么查找。
  • 哈希表 拉链法解决冲突原理:(大数对应一个小数,加快查找速率)建立一条拉链,每个拉链为一个槽,每个槽涵盖一个链表,将所有处理过的数放入对应槽的链表中 #include<iostream> #include<cstring> ...

    哈希表 拉链法解决冲突原理:(大数对应一个小数,加快查找速率)建立一条拉链,每个拉链为一个槽,每个槽涵盖一个链表,将所有处理过的数放入对应槽的链表中

    #include<iostream>
    #include<cstring>
    
    using namespace std;
    
    const int N = 1e5 + 3;//N最好是质数且远离2的整倍数(可证明) 
    
    int h[N], ne[N], e[N], idx;
    
    void add(int x){
    	int k = (x % N + N) % N;//找到x所在的k槽
    	e[idx] = x;//将x插入k槽所在的链表 
    	ne[idx] = h[k];
    	h[k] = idx ++ ;
    } 
    
    bool find(int x){
    	int k = ( x % N + N) % N;//找到x所在的k槽 
    	for(int i = h[k]; i != -1; i = ne[i] ){//遍历k槽所在的链表 
    		if(e[i] == x){//找到x 
    			return true;//返会true,表示已找到 
    		}
    	} 
    	return false;//如果k槽的链表遍历结束还没有找到,返回false,表示没找到 
    }
    
    int main()
    {
    	int n;
    	cin>>n;
    	memset(h, -1, sizeof(h));//初始化每个表头!!!!这一步很重要!!!!不能忘!! 
    	while(n -- ){
    		char op[2];//将命令字符以字符串形式读入,防止样例给无意义的空格 
    		int x;
    		scanf("%s%d", op, &x);
    		if(op[0] == 'I'){
    			add(x);
    		}
    		else if(op[0] == 'Q'){
    			if(find(x)){
    				cout<<"Yes"<<endl;
    			}
    			else if(!find(x)){
    				cout<<"No"<<endl;
    			} 
    		}
    	}
    	return 0;
    }
    
    展开全文
  • 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

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

    展开全文
  • <?php class HashNode { public $key; public $value; public $nextNode; public function __construct($key, $value, $nextNode = NULL) { $this->key = $key; ...
    <?php
    class HashNode {
        public $key;
        public $value;
        public $nextNode;
        
        public function __construct($key, $value, $nextNode = NULL)
        {
            $this->key = $key;
            $this->value = $value;
            $this->nextNode = $nextNode;
        }
    }
    
    class HashTable{
        private $buckets;
        private $size = 10;
        
        public function __construct()
        {
            $this->buckets = [];
        }
        
        private function hashfunc($key)
        {
            $strlen = strlen($key);
            $hashval = 0;
            for ($i = 0; $i < $strlen; $i++) {
                $hashval += ord($key[$i]);
            }
            return $hashval % $this->size;
        }
        
        public function insert($key, $value)
        {
            $index = $this->hashfunc($key);
            //新创建一个节点
            if (isset($this->buckets[$index])) {
                $newNode = new HashNode($key, $value, $this->buckets[$index]);
            } else {
                $newNode = new HashNode($key, $value, NULL);
            }
            $this->buckets[$index] = $newNode; //保存新节点
        }
        
        public function find($key)
        {
            $index = $this->hashfunc($key);
            $current = $this->buckets[$index];
            while (isset($current)) {
                if($current->key == $key){
                    return $current->value;
                }
                var_dump($current);die;
                $current = $current->nextNode;
            }
            return NULL;
        }
    }

    解释:

    1.使用Hash函数计算关键字的Hash值,通过Hash值定位到Hash表的指定位置

    2.如果此位置已经被其他节点占用,把新节点的$nextNode指向此节点,否则把新节点的$nextNode设置为NULL

    3.把新节点保存到Hash表的当前位置

    4.遍历当前链表,比较链表中每个节点的关键字与查找关键字是否相等

    转载于:https://www.cnblogs.com/kerwing/p/9154865.html

    展开全文
  • #define N 12 //首先定义相关的结构体 typedef struct HNode { int key; struct HNode *next; }Hnode; /* 创建哈希表 heahLink哈希表,里面存储的为指针变量 ...void createHB(Hnode *heahLink[], int key[], int ...
  • hash表的拉链法解决冲突

    千次阅读 2014-05-30 15:15:25
    //拉链法对hash table的溢出处理 #include #include #include #define MAX_CHAR 10 #define TABLE_SIZE 13 typedef struct element { char key[MAX_CHAR]; //other fields }element ; typedef struct List { ...
  • 解决冲突,构造哈希表 将所有哈希函数 结果相同的结点 连接在同一个单链表中。 若选定的哈希表 长度 为m,则可将哈希表定义为一个长度为m的 指针数组 t[0-m-1],指针数组中的每个指针指向哈希函数 结果相同的...
  • * 使用拉链法解决冲突 */ class hashtable{ private $buckets; //存储数据数组 private $size = 10; public function __construct(){ $this -> buckets = new SplFixedArray($this->size); } /** * 通过...
  • 拉链法解决冲突的哈希表

    千次阅读 2013-01-21 19:43:35
    //使用拉链法解决哈希冲突 }; ////表头 struct head{ snow * next; }; head h[rem + 1]; ////清空hash表 void init(){ int i; for( i = 0; i ; i ++ ){ h[i].next = NULL; } } ////哈希函数 int hash( int ...
  • 以vector为容器(可自动扩展),供用户多次输入(而不是在源代码中设置数组)来建立散列,以拉链法解决冲突(头插入建链),可进行多次搜索
  • 拉链法解决Hash节点冲突问题 <?php /* * hash::拉链法解决hash节点存储冲突问题 * ::2014-07-02 * ::Small_Kind */ class small_hash { privat...
  • 将所有哈希函数结果相同的节点连接在同一个单链表中。 #include <string> #include<stdio.h> #include<vector> struct ListNode { int val; ListNode* next;...int int_func(i...
  • 本文探讨拉链解决哈希冲突的方式和几种常见的散列函数。  首先,什么是散列表?  对于一个数组,我们在O(1)时间复杂度完成可以完成其索引的查找,现在我们想要存储一个key value的键值对,我们可以根据key生成...
  • //使用头插插入结点 hash_table[hash_key] = node; } bool search(ListNode* hash_table[], int value, int table_len) { int hash_key = hash_func(value, table_len); ListNode* head = hash_table[hash_key...
  • 2019独角兽企业重金招聘Python工程师标准>>> 解决HashMap冲突 转载于:https://my.oschina.net/u/3781047/blog/1628725
  • 一个关键字会映射到同一个位桶中的情况,这种情况就就叫做哈希冲突解决哈希冲突的有三种方案,一种叫做拉链法(也叫作链接法、链地址法,一个意思),另外三种分别为开发地址法和再散列法。 一、拉链法 ...
  • #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;...}
  • &lt;?php header('Content-type:text/html;charset=utf-8'); class HashTable{ private $buckets; private $size = 10; public function __construct() { $this-&...buckets = new SplFix...
  • 开放地址法和拉链法分别是怎么解决哈希冲突的,希望可以通俗一点,感谢大咖们的帮助
  • /* ... * All rights reserved. * 文件名称:项目3.cbp ...相比线性探查,拉链法适用于大数据,它是把所有的同义词用单链表链接起来,利用哈希函数求出每个关键字的地址,同一地址的利用链表存放在一起。
  • 拉链法和线性探测法解决哈希冲突 转自:http://www.tuicool.com/articles/QNjAbaf   前言 前面学习到的几种算法比如 红黑树 , 二叉搜索树 ,查找插入 时间复杂度 最快也只能到 O(logn) .现在介绍一...
  • 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; ...
  • 散列表线性探测法外拉链法 #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 ...

空空如也

空空如也

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

拉链法解决冲突