精华内容
下载资源
问答
  • 哈希表的拉链法

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

    拉链法

    Hash(KEY) = Positon;
    在Postion下面形成一个单链表,存储所有以该Positon为存储地址的数据。

    找一个比数据范围略大的大质数

    例如数据范围是10W

    	for(int i = 100000; ; i++)
    	{
    		bool bFlag = true;
    		
    		for(int j = 2; j * j <= i; j++)
    		{
    			if(0 == i % j)
    			{
    				bFlag = false;
    				break;
    			}
    		}
    		
    		if(bFlag)
    		{
    			cout<<i<<endl;
    			break;
    		}
    	}
    

    代码

    #include <bits/stdc++.h>
    using namespace std;
    
    
    const int N = 100003;//大质数 用来求哈希地址
    int Head[N];//用来存储每个哈希地址的首节点地址 
    int Value[N]; //存储值
    int Next[N];//存储链表的下一个地址
    int nPos; //记录存储位置 
    
    void Insert(int nNum)
    {
    	int nKey = ((nNum % N) + N) % N;//是为了防止nNum是负数
    	
    	Value[nPos] = nNum;//记录下数值
    	//链表的头插法 
    	Next[nPos] = Head[nPos];
    	Head[nPos] = nPos;
    	nPos++; 
    }
    
    void Find(int nNum)
    {
    	int nKey = ((nNum % N) + N) % N;
    	int nPos = Head[nKey];
    	
    	while(-1 != nPos)
    	{
    		if(nNum == Value[nPos])
    		{
    			cout<<"查找到了 "<<endl;
    			return;
    		}
    		else
    		{
    			nPos = Next[nPos];
    		}
    	}
    	cout<<"查不到"<<endl;
    }
    
    
    
    int main(int argc, char** argv) 
    {
    	memset(Head,-1,sizeof(Head));
    	Insert(0);
    	Find(0);
    	Insert(1);
    	Find(111);
    	return 0;
    }
    
    展开全文
  • 遇到具体问题时,hash函数取模N为比数据范围大最小质数就行,可以提前打求出。 #include<iostream> #include<cstring> using namespace std; const int N=100003; int n; int h[N],e[N],ne[N]...

    遇到具体问题时,hash函数取模的N为比数据范围大的最小的质数就行,可以提前打表求出。

    #include<iostream>
    #include<cstring>
    
    using namespace std;
    
    const int N=100003;
    int n;
    int h[N],e[N],ne[N],idx;
    
    int hs(int x){
        return ((x%N)+N)%N;
    }
    
    bool insert(int x){
        int t=hs(x);
        e[idx]=x,ne[idx]=h[t],h[t]=idx++;
    }
    
    int find(int x){
        int t=hs(x);
        for(int i=h[t];i!=-1;i=ne[i]){
            if(e[i]==x)return true;
        }
        return false;
    }
    
    int main(){
        cin>>n;
        memset(h,-1,sizeof h);
        char op;
        int x;
        while(n--){
            cin>>op>>x;
            if(op=='I')
                insert(x);
            else{
                if(find(x))cout<<"Yes"<<endl;
                else cout<<"No"<<endl;
            }
        }
    }
    
    展开全文
  • 也就是拉链特别长时候,有什么好办法能够解决吗?主要是为了解决查询效率问题,我想过把拉链变为一棵红黑树,除了这个办法以外还有什么好办法吗?
  • 哈希表(拉链法)

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

    哈希表(拉链法)

    哈希表_拉链法

    
    #include <stdio.h>
    #include <vector>
    
    struct ListNode {
    	int val;
    	ListNode *next;
    	ListNode(int x) : val(x), next(NULL) {}
    };
    
    int hash_func(int key, int table_len){
    	return key % table_len;//整数哈希,直接取余
    }
    
    void insert(ListNode *hash_table[], ListNode *node, int table_len){
    	int hash_key = hash_func(node->val, table_len);
    	node->next = hash_table[hash_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];
    	while(head){
    		if (head->val == value){
    			return true;
    		}
    		head = head->next;
    	}
    	return false;
    }
    
    int main(){
    	const int TABLE_LEN = 11;
    	ListNode *hash_table[TABLE_LEN] = {0};
    	std::vector<ListNode *> hash_node_vec;
    	int test[8] = {1, 1, 4, 9, 20, 30, 150, 500};
    	for (int i = 0; i < 8; i++){
    		hash_node_vec.push_back(new ListNode(test[i]));
    	}	
    	for (int i = 0; i < hash_node_vec.size(); i++){
    		insert(hash_table, hash_node_vec[i], TABLE_LEN);
    	}	
    	printf("Hash table:\n");
    	for (int i = 0; i < TABLE_LEN; i++){
    		printf("[%d]:", i);
    		ListNode *head = hash_table[i];
    		while(head){
    			printf("->%d", head->val);
    			head = head->next;
    		}
    		printf("\n");
    	}
    	printf("\n");	
    	printf("Test search:\n");
    	for (int i = 0; i < 10; i++){
    		if (search(hash_table, i, TABLE_LEN)){
    			printf("%d is in the hash table.\n");
    		}
    		else{
    			printf("%d is not in the hash table.\n");
    		}
    	}
    	return 0;
    }
    
    

    单链表的插入操作

    单链表的插入操作

    x->next = p->next;  // 将x的结点的next指针指向b结点;
    p->next = x;  // 将p的next指针指向x结点;
    

    单链表练习

    • 单链表反转
    • 链表中环的检测
    • 两个有序的链表合并
    • 删除链表倒数第 n 个结点
    • 求链表的中间结点
    展开全文
  • 哈希表拉链法

    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

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

    2018-03-01 17:32:55
    哈希表的建立,初始化,节点的插入,查找,删除及哈希表的销毁的相关代码如下:#include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #include&lt;string.h&gt; #include&lt;assert.h&...
  • Java 标准库 HashMap 基本上就是用 拉链法 实现拉链法 实现比较简单,将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突值加到链表中即可。 实现...
  • 哈希表的主要作用: 把一个较大(0-10^9 )的数据映射到较小(0-N(N一般为10^5 到 10^6))的数据 哈希函数:可以把一个从-10^19 到10^19 的中的一个数映射到0-10^5之间的一个数 1.哈希函数怎么写? 一般情况下,直接取模...
  • 哈希表拉链法

    千次阅读 2018-03-10 20:14:11
    > 开散列又叫链地址(开链... 桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。 设元素的关键码为37, 25, 14, 36, 49, 68, 57, 11, 散列表为HT[12],表的大小为12,散列函数为Hash(x) = x % 11
  • //哈希表的实现//邱于涵QQ1031893464//2017年5月3日14:43:48#include#include#includetypedef struct node{char * name;//字段名char * desc;//描述struct node * next;//链式表}node;#define HASHSIZE 100//哈希表...
  • 哈希表拉链法解决冲突时候怎么根据K进行查找值?假如k1,k2有冲突,现在查找k2值?怎么查找。
  • 前段时间理解了一下所谓的哈希表,一直以来在小博印象中哈希表是深奥,是高大上,但是接触原理以及看了一份demo之后我就觉得哈希表也就那样吧,接下来我把小博自己理解尽量用最直白语句来解释下~~~---------...
  • 9.1 哈希表的定义和特点 散列表(Hash table, 也叫哈希表),是根据关键码 - 值(Key - value)而直接进行访问的数据结构。 也就是说, 它通过把关键码 - 值映射到表中一个位置来访问记录, 以加快查找的速度。这个...
  • 我们都知道,当我们要在一个集合中查找数据时,如果这个集合是顺序且我们能确定要找数据在顺序位置话,我们就能通过下标直接找到元素,这无非是我们要追求最高效查找策略!但是现实总是那么骨感,在...
  • 模拟散列表(手写哈希表) 维护一个集合,支持如下几种操作: “I x”,插入一个数x; “Q x”,询问数x是否在集合中出现过; 现在要进行N次操作,对于每个询问操作输出对应结果。 输入格式 第一行包含整数N,表示...
  • C语言哈希表的简单实现——数组+链表(拉链法) 1.哈希表简介 哈希表详细介绍可以参考这篇文章 2.哈希表拉链法实现 2.1完全由本人思路实现,如有错误,欢迎批评指正 哈希声明文件hash.h /* 哈希表 * by : I'M渣渣 * ...
  • 哈希表查找 — 拉链法

    千次阅读 2015-07-26 17:33:06
    散列表(也叫哈希表),是根据关键字值而直接进行访问数据结构。 本文采用除留余数法构造散列函数。 本文采用拉链法处理冲突。 根据原始数组建立一个哈希表哈希表为一个链表(一定要区分数组和链表),且要求哈希...
  • 哈希表的哈希桶数量设置为10,以员工编号为input来计算哈希后的key,哈希函数使用取余,编码来实现,并且再编写一个单独的函数来打印出来所有存储的数据。 编号 姓名 薪资 198 mark 5000 245 jerry 5600...
  • 开散列:首先对关键码集合用散列函数计算散列地址,具有相同地址关键码归于同一子集合,每一个子集合称为一个桶,各个桶中元素通过一个单链表链接起来,各链表头结点存储在哈希表中。 设元素关键码为37, ...
  • 用java写的拉链法实现哈希表的建立,应用到类似于电话本查询的程序里,课程设计时候做的,所以不是很完美
  • 哈希表是一个用途很广泛数据结构,常用于需要进行大集合搜索地方,比如腾讯QQ。对于上线用户我们需要将其添加到一个集合中,以便对其进行各种处理。那么这个集合该采取哪种数据结构呢?最基本数据结构就两种...
  • 哈希表的开散列法(拉链法

    千次阅读 2018-03-01 21:56:28
    开散列:首先对关键码集合用散列函数计算散列地址,具有相同地址关键码归于同一子集合,每一个子集合称为一个桶,各个桶中元素通过一个单链表链接起来,各链表头结点存储在哈希表中。 设元素关键码为37, ...
  • 哈希冲突之拉链法

    千次阅读 2015-09-10 19:56:17
    解决哈希冲突一种比较直接办法就是,将大小为M数组每一个元素指向一条链表,链表中每一个节点都存储一个哈希值为该索引键,这...使用链接在最坏情况下,也就是将所有key映射到同一个槽中了,这样哈希表
  • HashTable哈希表拉链法实现(C语言)

    千次阅读 2017-05-03 14:45:40
    //哈希表的实现 //邱于涵QQ1031893464 //2017年5月3日14:43:48 #include #include #include typedef struct node{ char * name;//字段名 char * desc;//描述 struct node * next;//链式表 }node; #define ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 718
精华内容 287
关键字:

哈希表的拉链法