精华内容
下载资源
问答
  • 模拟散列表(哈希表拉链法和开放寻址法C++)
    2021-07-12 18:02:01

    题目

    维护一个集合,支持如下几种操作:

    1. I x,插入一个数 x;
    2. Q x,询问数 x 是否在集合中出现过;

    现在要进行 N 次操作,对于每个询问操作输出对应的结果。

    输入格式

    第一行包含整数 N,表示操作数量。

    接下来 N 行,每行包含一个操作指令,操作指令为 I xQ x 中的一种。

    输出格式

    对于每个询问指令 Q x,输出一个询问结果,如果 x 在集合中出现过,则输出 Yes,否则输出 No

    每个结果占一行。

    数据范围

    1≤N≤105
    −109≤x≤109

    输入样例:

    5
    I 1
    I 2
    I 3
    Q 2
    Q 5
    

    输出样例:

    Yes
    No

    拉链法 

    #include<iostream>
    #include<cstring>
    
    using namespace std;
    
    const int N = 1e5 + 3;
    
    int h[N], e[N], ne[N], idx;
    
    void insert(int x)
    {
    	int k = (x % N + N) % N;
    	e[idx] = x;
    	ne[idx] = h[k];
    	h[k] = idx ++; 
    }
    
    bool query(int x)
    {
    	int k = (x % N + N) % N;
    	for(int i = h[k]; i != -1; i = ne[i])
    		if(e[i] == x) return true;
    	return false;
    }
    
     int main()
     {
     	//初始全为 -1 
     	memset(h, -1, sizeof(h));
     	
     	int n;
     	cin >> n;
     	while(n --)
     	{
     		char op;
     		int x;
     		cin >> op >> x;
     		if(op == 'I')insert(x);
     		else 
     		{
     			if(query(x)) cout << "Yes" << endl;
     			else cout << "No" << endl;
    		}
    	}
    
     	return 0;
     }

    开放寻址法

    #include<iostream>
    #include<cstring>
    
    using namespace std;
    
    const int N = 2e5, null = 0x3f3f3f3f;
    
    int h[N];
    
    int find(int x)//返回要插入的位置 
    {
    	int k = (x % N + N) % N;
    	while(h[k] != null && h[k] != x)
    	{
    		k ++;
    		if(k == N) k = 0;
    	}
    	return k;
    }
    
     int main()
     {
     	//初始全为 -1 
     	memset(h, 0x3f, sizeof(h));
     	
     	int n;
     	cin >> n;
     	while(n --)
     	{
     		char op;
     		int x;
     		cin >> op >> x;
     		int k = find(x);
     		if(op == 'I') h[k] = x;
     		else 
     		{
     			if(h[k] != null) cout << "Yes" << endl;
     			else cout << "No" << endl;
    		}
    	}
    
     	return 0;
     }

     

    更多相关内容
  • 哈希表存储结构: 1.开放寻址法 2.拉链法 哈希表的主要作用: 把一个较大(0-10^9 )的数据映射到较小(0-N(N一般为10^5 到 10^6))的数据 哈希函数:可以把一个从-10^19 到10^19 的中的一个数映射到0-10^5之间的一个数 ...

    哈希表存储结构:
    1.开放寻址法
    2.拉链法

    哈希表的主要作用:
    把一个较大(0-10^9 )的数据映射到较小(0-N(N一般为10^5 到 10^6))的数据

    哈希函数:可以把一个从-10^19 到10^19 的中的一个数映射到0-10^5之间的一个数

    1.哈希函数怎么写?
    一般情况下,直接取模,x%10^5,我们一般模的数,一般取为质数,并且离2的整次幂尽可能的远,这样取,冲突的概率最小

    2.冲突:把2个不一样的数映射成同一个数怎么办?
    我们可以用开放寻址法或者拉链法来解决这个问题

    首先我们先定义哈希函数:h(a) = b,指我们将a映射成b
    这里我们只介绍拉链法。
    拉链法:
    参考文献:
    图示算法
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    举个例子:

    维护一个集合,支持如下几种操作:
    “I x”,插入一个数x;
    “Q x”,询问数x是否在集合中出现过;
    现在要进行N次操作,对于每个询问操作输出对应的结果。

    输入格式
    第一行包含整数N,表示操作数量。
    接下来N行,每行包含一个操作指令,操作指令为”I x”,”Q x”中的一种。

    输出格式
    对于每个询问指令“Q x”,输出一个询问结果,如果x在集合中出现过,则输出“Yes”,否则输出“No”。

    每个结果占一行。

    数据范围
    1≤N≤105
    −109≤x≤109

    输入样例:
    5
    I 1
    I 2
    I 3
    Q 2
    Q 5

    输出样例:
    Yes
    No

    代码如下:

    #include <iostream>
    #include <cstring>
    using namespace std;
    const int N = 1e5+3;
    int h[N],e[N],ne[N],idx;
    void Insert(int x)
    {
        int t = (x%N+N)%N;
        e[idx] = x;
        ne[idx] = h[t];
        h[t] = idx++;
        
    }
    
    bool find(int x)
    {
        int t = (x%N+N)%N;
        for (int i = h[t];i!=-1;i = ne[i])
        {
            if (e[i]==x)
            {
                return true;
            }
        }
        return false;
    }
    
    int main()
    {
        int cnt;
        cin>>cnt;
        memset(h,-1,sizeof(h));
        while(cnt--)
        {
            string a;
            int b;
            cin>>a>>b;
            if (a[0]=='I') Insert(b);
            else
            {
                if (find(b))
                {
                    cout<<"Yes"<<endl;
                }
                else
                {
                    cout<<"No"<<endl;
                }
            }
        }
        return 0;
    }
    
    展开全文
  • 哈希表拉链法

    2019-10-09 03:59:53
    前段时间理解了一下所谓的哈希表,一直以来在小博印象中哈希表是深奥的,是高大上的,但是接触原理以及看了一份demo之后我就觉得哈希表也就那样吧,接下来我把小博自己的理解尽量用最直白的语句来解释下~~~ ...

    前段时间理解了一下所谓的哈希表,一直以来在小博印象中哈希表是深奥的,是高大上的,但是接触原理以及看了一份demo之后我就觉得哈希表也就那样吧,接下来我把小博自己的理解尽量用最直白的语句来解释下~~~

    ---------------------------------------------------------我是分界线,没错,很丑------------------------------------------------------------------

    首先什么是哈希表???

    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    以上是一段在百度百科中的解释,如果还是不能理解,那么我就抽象的比喻一下。

    先看(是根据关键码值(Key value)而直接进行访问的数据结构),这里的关键码值以及数据结构可以用具体的物体代替一下,这里小博将关键码值用学号代替,数据结构用学生代替,学生与学号都是唯一的,可以根据学号直接找到学生。(说了一堆废话~~~~接下去才是重点)。

    场景演示一下,当我们需要将数据存入哈希表中的时候,就好像是一堆学生在办理入学,那么这时候有个地中海的大肚子男老师过来了,他对每个上前办理的学生说:你是XXX号,你所在的班级是YYY班,记住咯。然后这名学生就屁颠屁颠的去YYY班了。那么怎么查找呢??想必在学校中被校长点名过的同学应该都想到了,比如XXX号犯错了,他所在的班级是YYY一班,那么校长会说,在YYY一班的XXX号,你出来一下咱们好好喝喝茶~~这样校长就不用为了找XXX号同学而找遍每一个学生了,相对来说就是提升了查找效率。这是哈希表其中的一个特性————查找方便

    还有一个比较重要的特性,小博暂时没想到怎么怎么形象的比喻(原谅小博的见识浅薄~~囧)。另一个特性是空间高利用率,各位大老爷可能有几个一下子不能理解这个,请容小博详细说明,都知道需要存数据是需要容器的,数组,结构体等都是容器的一种,那么只要是容器都需要各自的空间(其实不仅仅是容器需要,其他也是一样的,但是相比之下其他占用的比较少罢了,继续正文),比如数组,当申请的时候需要一块连续的空间,而数据结构也是如此,申请的时候需要一块整个数据结构大小的空间,而且每次申请空间的时候,系统内部所为你划分的空间并不是一块挨着一块申请的,因此肯定会有少部分空间无法申请导致浪费,采用数据结构可以灵活的利用这些空间,采用链表将每个结构体联系起来,那么就形成了一个最简单的哈希表。直接上代码理解一下吧~~~~(写这些的时候小博已经神游,断片了,原谅小博的才疏学浅。)

    #include <stdio.h>
    #include <string>
    #include <time.h>
    
    typedef struct ITEM 
    {
    	int val;
    	int index;
    	struct ITEM *next;
    }Item;
    
    typedef struct LIST
    {
    	Item *head;
    	Item *end;
    }List;
    
    #define HASH_VAL 10
    
    void insertItem(List* list, Item* item)
    {
    	int key = (unsigned int)item->val%HASH_VAL;
    	if (!list[key].head)
    	{
    		list[key].head = item;
    		list[key].end = item;
    	}
    	else
    	{
    		list[key].end->next = item;
    		list[key].end = item;
    	}
    }
    
    void showList(List* list)
    {
    	Item* p = NULL;
    	for (int i = 0; i < 10; i++)
    	{
    		printf("%d:", i);
    		p = list[i].head;
    		if (p)
    		{
    			do 
    			{
    				printf("%d(下标:%d)  ", p->val, p->index);
    				if (p->next)
    					p = p->next;
    				else
    					break;
    			} while (1);
    		}
    		printf("\n");
    	}
    }
    
    bool aaa(int* a, int val)
    {
    	for (int i = 0; i < 10; i++)
    	{
    		if (a[i] == val)
    			return true;
    	}
    	return false;
    }
    
    bool serchItem(List* list, int val)
    {
    	int key = (unsigned int)val%HASH_VAL;
    	Item* p = list[key].head;
    
    	while (p)
    	{
    		if (p->val == val)
    			return true;
    		p = p->next;
    	}
    	return false;
    }
    
    int main(int argc, char* argv[])
    {
    	List list[10];
    	Item item[10];
    	memset(list, 0, sizeof(List)* 10);
    	memset(item, 0, sizeof(Item)* 10);
    	int a[10] = {21,11,1,51,5,6,7,8,9,0};
    
    	for (int i = 0; i < 10; i++)
    	{
    		item[i].index = i;
    		item[i].val = a[i];
    		insertItem(list, &item[i]);
    	}
    	showList(list);
    	system("pause");
    	return 0;
    }
    

      小博演示的拉链法是将数组的特点(方便查找,不易删除)以及链表的特点(方便删除,不易查找)取长补短的一种折中方法。

    ----------------------------------------------分界线,又出现了-----------------------------------------------------------------

    文中好像很多废话,希望没有把各位大老爷给绕晕了,新人小白发表,不足之处请见谅,欢迎大牛指导,其他同道也可交流

     

    如果不理解小博的思路,可以参考更详细的原理:http://www.cnblogs.com/tuhooo/p/7092288.html#3934840

    转载于:https://www.cnblogs.com/chen1026/p/8690578.html

    展开全文
  • //哈希表的实现//邱于涵QQ1031893464//2017年5月3日14:43:48#include#include#includetypedef struct node{char * name;//字段名char * desc;//描述struct node * next;//链式表}node;#define HASHSIZE 100//哈希表...

    //哈希表的实现

    //邱于涵QQ1031893464

    //2017年5月3日14:43:48

    #include

    #include

    #include

    typedef struct node{

    char * name;//字段名

    char * desc;//描述

    struct node * next;//链式表

    }node;

    #define HASHSIZE 100//哈希表的长度(#define宏后面不能有;分号)

    static node * hashtable[HASHSIZE];//定义一个hash数组 由于是static所以默认为NULL

    unsigned int hash(char * key)

    {

    //这里必须是unsigned int 因为如果字符串很长的话 这里 int是不够的(重点)

    unsignedint h = 0;

    for (; *key; key++)

    h = *key + h * 31; //特定公式生成整数 用于哈希表上分布均匀(核心)

    return h%HASHSIZE;

    }

    //检索 获取键 所对应的node 指针

    node * lookup(char * key)

    {

    //字符串求哈希

    unsigned int hashvalue = hash(key);

    //获取哈希表

    node * np = hashtable[hashvalue];

    //在链表上查找

    for (; np != NULL; np = np->next)

    {

    if (!strcmp(np->name, key)) //相等返回0

    {

    return np;

    }

    return NULL;

    }

    }

    //搜索键返回值

    char * search(char * key)

    {

    node * np = lookup(key);

    if (np ==NULL) return NULL;

    return np->desc;

    }

    //分配堆内存

    node * malloc_node(char * key, char * value)

    {

    //分配堆内存

    node * np = (node*)malloc(sizeof(node));

    //分配失败

    if (np == NULL)return NULL;

    //设置键值

    np->name = key;

    np->desc = value;

    np->next = NULL;

    return np;

    }

    //插入哈希表(键,值)

    int insert(char * key, char * value)

    {

    //这里必须是unsigned int 因为字符串太长的话 int是不够储存的

    unsigned int hashvalue = hash(key);

    //分配堆内存

    node * np = malloc_node(key, value);

    //分配失败就返回0

    if (np == NULL) return 0;

    //设置下一结点为 (每次插入在 链表头上,节约很多时间 )

    np->next = hashtable[hashvalue];

    hashtable[hashvalue] = np;

    return 1;

    }

    //遍历显示哈希表

    void displayHashTable()

    {

    //显示的结点指针

    node *np;

    //哈希值

    int hashvalue;

    //遍历表

    for (int i = 0; i < HASHSIZE; i++)

    {

    if (hashtable[i] != NULL)

    {

    np = hashtable[i];

    //链式表 遍历输出

    for (; np != NULL; np=np->next)

    {

    printf("(%s,%s)", np->name, np->desc);

    }

    printf("\n");

    }

    }

    }

    //清除哈希表

    void clearHashTable()

    {

    node * np; //马上释放的结点

    node *tmp;//下一个结点

    //遍历表

    for (int i = 0; i < HASHSIZE; i++)

    {

    //获取其中一个元素

    np = hashtable[i];

    if (np != NULL)

    {

    //赋值为空

    hashtable[i] = NULL;

    //tmp

    tmp = np;

    tmp = tmp->next;

    //释放内存

    free(np);

    // 链表 释放

    while (tmp!=NULL)

    {

    np = tmp;

    free(np);

    tmp = tmp->next;

    }

    }

    }

    }

    int main(){

    char* names[] = { "last Name","First Name", "address", "QQ_number", "sex", "job" };

    char* descs[] = { "邱","于涵", "成都", "1031893464", "男", "学生" };

    for (int i = 0; i < 6; ++i)

    insert(names[i], descs[i]);

    printf("job %s\n", search("job"));

    displayHashTable();

    clearHashTable();

    displayHashTable();

    while (1){};

    return 0;

    }

    0818b9ca8b590ca3270a3433284dd417.png

    展开全文
  • 哈希表拉链法,简单,直接看代码:#include using namespace std;struct Node{int iData;Node* pNext;};#define N 10typedef Node* HashTable[N]; // 指针数组HashTable hTable;void createHashTable(int a[], int n...
  • 拉链法—构建哈希表

    2022-03-29 22:46:24
    输入一个序列,按照序列中的元素顺序,利用拉链法构造哈希表,输出哈希表的查询结果。哈希表的插入(插入同一线性链表时采用头插法) 输入 第一行数据分别表示序列的长度n,哈希表的长度m,以及用计算哈希函数...
  • 2.哈希表拉链法实现 2.1完全由本人思路实现,如有错误,欢迎批评指正 哈希声明文件hash.h /* 哈希表 * by : I'M渣渣 * date: 2021.5.11 */ #ifndef __HASH_H_ #define __HASH_H_ #define size 100 //哈希数组大小...
  • 哈希表(拉链法)

    2020-01-04 16:02:31
    文章目录哈希表(拉链法)单链表的插入操作单链表练习 哈希表(拉链法) #include <stdio.h> #include <vector> struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {...
  • 哈希——拉链法

    千次阅读 2018-03-01 15:25:06
    首先写哈希——拉链法要知道哈希冲突。 哈希冲突: 对于两个数据元素的关键字 Ki 和 Kj (i != j),有 Ki != J ,但有: HashFun(Ki) == HashFun(Kj) 即不同关键字通过相同哈希哈数计算出相同的哈希地址,该种...
  • 哈希表拉链法解决冲突)

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

    2021-01-11 19:37:44
    拉链法 Hash(KEY) = Positon; 在Postion下面形成一个单链表,存储所有以该Positon为存储地址的数据。 找一个比数据范围略大的大质数 例如数据范围是10W for(int i = 100000; ; i++) { bool bFlag = true; ...
  • 哈希表的开散列法(拉链法

    千次阅读 2018-03-01 21:56:28
    开散列:首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。 设元素的关键码为37, ...
  • 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • #include <stdlib.h> #include <stdio.h> /* 一如既往的使用注释进行说明吧 建立哈希表 Hash_Table Node节点进行插入(值%n n=4) H(0)->Node->Node... 4 8 12 H(1)->Node->Node... ...
  • 哈希表,是根据关键字值(Key)直接进行访问的数据结构,它通过把关键字映射到表中一个位置(数组下标)来直接访问,以加快查找关键值的速度。这个映射函数叫做哈希函数,存放记录的数组叫做哈希表 给定表M,存在函数f...
  • 易语言源码易语言拉链法哈希表源码.rar 易语言源码易语言拉链法哈希表源码.rar 易语言源码易语言拉链法哈希表源码.rar 易语言源码易语言拉链法哈希表源码.rar 易语言源码易语言拉链法哈希表源码.rar 易语言源码...
  • 哈希表查找--拉链法

    千次阅读 2017-10-30 21:46:50
    1.拉链法解决哈希冲突: 方法:把所有经过一种函数计算后的地址H(k)相同的数据用链表连接起来。 H(k)=k%p; 理论研究证明,p取小于哈希表长度的素数时效果最好。 代码实现建表与查找: //节点数据结构定义 ...
  • //创建哈希表 int HashTableInsert(HashTable* ht, KeyType key, ValueType value); //插入 HashNode* HashTableFind(HashTable* ht, KeyType key); //查找 int HashTableRemove(HashTable* ht, KeyType key)...
  • 用java写的拉链法实现哈希表的建立,应用到类似于电话本查询的程序里,课程设计时候做的,所以不是很完美
  • 哈希表 拉链法

    2013-03-28 14:16:47
    哈希表: */ #include #include #include typedef struct node {  char data;  struct node *next; }link_list; int main() {  link_list *p,*p1,*q;  link_list a[10];  int b
  • C语言实现哈希表(链式

    千次阅读 多人点赞 2019-11-23 13:13:03
    笔者最近学习数据结构中的哈希表,并用C语言简单实现了。 当然源代码多有参考,此博客旨在交流心得 哈希表原理 结构体说明如下 源代码如下: #include<stdio.h> #include<stdlib.h> #define ...
  • //哈希表(拉链法) #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]...
  • 哈希表基础知识

    千次阅读 2022-03-13 19:18:56
    哈希表 基础知识 首先什么是 哈希表哈希表(英文名字为Hash table,国内也有一些算法书籍翻译为散列表,大家看到这两个名称知道都是指hash table就可以了)。 哈希表是根据关键码的值而直接进行访问的数据结构。 ...
  • 哈希表拉链法

    2019-09-24 13:35:26
    //2019.9.24 #include<iostream> #include<cstring> using namespace std; const int N=100003; int hashing[N]; int e[N],ne[N],idx; int n; void insert(int x) { int u=(x%N+N)%N;... e...
  • 本文为大家分享了C语言基于哈希表实现通讯录的具体代码,供大家参考,具体内容如下 1.需求分析 本演示程序用C语言编写,完成哈希表的生成,电话号码的插入、以及查找等功能。  (1)按提示输入相应的联系人的相关...
  • Hash的实现——拉链法

    千次阅读 2018-11-21 13:04:22
    一.基础的概念问题 ...但是有时需要对大量数据进行查找以及插入删除操作,这时就需要用到哈希表,是根据关键码值(Key value)而直接进行访问的数据结构。 ·Hash我们百度一下英文意思就是把其弄乱,...
  • 拉链法哈希表(实战)

    2019-12-24 11:55:46
    哈希表 1.代码部分 /*hash_main.cpp文件*/ #include"hasha.cpp" #include"string.h" #include"stdio.h" #include"iostream" #include<string> ![在这里插入图片描述]...
  • 拉链法哈希表

    2021-03-16 00:54:57
    importjava.io.ObjectInputStream;importjava.util.ArrayList;.../*** @ClassName SeparateChainHashST* @Author wangyudi* @Date 2019/7/2 22:25* @Version 1.0* @Description 拉链法散列表(哈希表)*/...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,921
精华内容 5,568
关键字:

哈希表的拉链法